歌舞升平 (續)

來客止步！

請先讀前傳

http://blog.wenxuecity.com/blogview.php?date=201110&postID=5933


。。。。。

其實上篇源自下麵的益智題。才知道有個女子的數學奧林匹克。是中國創辦並在中國舉辦，也邀請包括美國在內的其他幾個國家的中學生參加。

看了一下今年(2011年)的題目。第四題還有點意思。


題目:  有 n (n>=3) 名乒乓球選手參加循環賽 , 每兩名選手之間恰比賽一次(比賽無平局) . 賽後發現 , 可以將這些選手排成一圈 , 使得對於任意三名選手A、B、C , 若A,B在圈上相鄰 , 則A,B中至少有一人戰勝了C , 求n的所有值。


解答: n可以為任何大於等於3的奇數，但不能為偶數。

略證:  若n為可能值，則

(1)  任何人與圈上相鄰兩位選手的成績必須是一勝一負。

證: 隻考慮相鄰選手比賽之間的成績，勝者積一分，負者積負一分。 每名選手跟左右兩位鄰居的比賽成績之和為+2, 0, 或 -2. 假設A積分為-2. 即 B,A,C依次相鄰而坐，而A同時輸給了B,C.若B勝C,則A,C相鄰而都不勝A，矛盾。反之，A,B相鄰，都不勝C,矛盾。所以每個人的積分隻能為0或者2. 但所有選手積分和為0 (因為每場比賽貢獻積分為0)， 故也不能有人積分為2. 所以每個人積分都是0，即與相鄰選手成績為一勝一負。

(2)  若 n  為偶數， 則獲勝場次最多的選手必須都贏相鄰的兩位選手。

證: 若A獲勝場次最多，則其至少贏n/2場，否則，所有人勝場之和最多為n (n/2 - 1) < n(n-1)/2，即所有比賽場次之和。除A外的n-1位選手中至少有n/2個被A擊敗，且由題意知任何兩個被A擊敗的選手都不能相鄰，所以A左右兩邊的鄰居必須都被A擊敗。

綜合 (1), (2), n 不能為偶數。

如 n 為奇數， 可構造比賽結果如下. 請所有選手在圓圈上落座。對圈上任兩位選手A, B, 定義A,B之間的距離為
         d(A,B) =從A逆時針到B要移動的座位數。

比如， 若B坐A右手鄰座，則 d(A,B) = 1， d(B,A) = n-1.

定義A, B之間的勝負如下:
    如d(A,B) 為奇數，則A勝； 反之則B勝。

顯見每兩個選手的比賽勝負唯一確定。

在圓桌上任取三名選手A, B, C，使得從A逆時針沿圓圈行走先經過B，再經過C. 易見
     d(A,B) + d(B,C) + d(C, A) = n

假定 d(A,B) = 1, 即B為A右鄰。則 d(B,C) + d(C, A) = n-1 為偶數。

若d(B,C) 和 d(C,A)都為奇數，則B勝C.
若d(B,C) 和 d(C,A)都為偶數，則A勝C.

構造符合題目條件。

證畢。

後記: 當n為奇數時，除選手座次調換或所有勝負同時顛倒，上述構造是否唯一？