歌舞升平 (续)

来客止步！

请先读前传

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为奇数时，除选手座次调换或所有胜负同时颠倒，上述构造是否唯一？