n个人要决出正确的名次，至少需要多少轮比赛？

wayne

要做到确保正确的名次，一对一的比赛场次必须至少是 p = C(n,2) =n*(n-1)/2
于是问题就是要将这个p分配到各轮比赛，使得总轮次m最小

于是答案就是 m= ceiling(C(n,2)/ceiling(n,2) )
但由于人是临界资源，所以正确的表达式应该是m= ceiling(C(n,2)/floor(n,2) )
化简一下：
m=n-1 (n是偶数)
m=n     (n是奇数)
跟10楼答案一样。


发觉这题突然间变得很水了

dianyancao

如何证明n为偶数时，C(n,2)恰能分解成(n-1)轮比赛，并且每轮比赛合中的每个人有且只比赛一次
n为奇数时，C(n,2)恰能分解成n轮比赛，并且每轮比赛中除一人外的其余每人有且只比赛一次

hujunhua

要做到确保正确的名次，一对一的比赛场次必须至少是 p = C(n,2) =n*(n-1)/2
wayne 发表于 2013-6-14 13:04

C(n,2)是全部场次了，不必要吧。如果已经决出A胜B，B胜C，A与C之间就没有必要安排比赛了。

dianyancao

考虑最坏情况，假设x,y之间没有比较过，那么当x,y的排名相邻时，不能确定x,y的排名顺序

wayne

13# hujunhua
fans说过，要保证一定能排出名次的~~
========
按住CTRL+F,就会惊奇的发现 fans用到了5次“保证”

wayne

13# hujunhua
估计fans 还有后文， 要我们给出 安排选手比赛的策略，使得 轮次m的平均期望最小，

KeyTo9_Fans

根据$13#$的提示，

尝试用$4$轮比赛为$5$个人决出正确的名次，

未果……

hujunhua版主可有高招？

hujunhua

图G:={V,E}.
定义1【顶点与边的覆盖】如果G的一个顶点v1与一个边e1关联，就称为覆盖彼此。
注：覆盖的概念可以扩展到顶点子集vs边子集。
定义2【边覆盖】L是E的子集，若L能覆盖V，则称L是图G的一个边覆盖。
定义3【极小边覆盖】L是图G的一个边覆盖，若L的任一真子集都不是G的边覆盖，则L称为图G的极小边覆盖。
定义4【最小边覆盖】边数达到最少的边覆盖。

关于12#的问题，显然我们只需要证明n为偶数的情况。对于n为奇数的情况，可以增加一个机器人棋手变成n+1人（偶数），规定机器人对谁都输（相当于规定轮空计胜1场）。

把人看作图的点，若两人之间进行一场比赛，就在两点之间连一条边。如果全部C(n,2)场比赛都进行的话，就对应于一个n阶完全图。于是12#的问题用图论的语言说，就是：
n（偶数）阶完全图的所有C(n,2)条边是否可以划分为n-1 个最小边覆盖L1, L2, ..., L(n-1)？（注：集合的划分，就是分成若干个两两不相交的子集）。
答案是肯定的，并且很容易证明。所以，如果m(n)=n-1, 那就不需要策略，怎么安排比赛都可以，只要符合最小边覆盖划分就行。

hujunhua

17# KeyTo9_Fans
比赛场次是可以减少的，但是不一定对减少比赛轮次有促进。
以n=6为例。本来每轮可以安排3场比赛，按13#的规则减少场次的结果，可能导致较晚的一些轮次只需要安排2场甚至1场的比赛，并没有充分发挥每轮的场数容量。

dianyancao

用二分插入排序的模型做，得到如下n=5时的策略：

对于更大的n用C(n,2)的方法应该是比赛轮次最少的了，
因为按快速排序做的话，第一步选择一个Pivot,
做Partition就需要n-1次对相同Pivot的比较，即至少需要n-1轮比赛