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

KeyTo9_Fans

假设有$n$个人参加围棋比赛，每个人都有$1$个实力值，

该实力值是$1$个$1$到$n$的整数，任何$2$个人的实力值都不相同。

比赛开始之前，我们不知道每个参赛者的实力值是多少，

但我们想通过若干轮比赛来决定这$n$个人的排名，

并且希望排名完全正确：实力值为$i$的人，名次恰好是$n+1-i$。

每轮比赛都是如下进行：
————————————————————
首先将$n$个参赛选手分成$|~n/2~|$组，每组$2$个人（当$n$是奇数时，有$1$组只有$1$个人）。

然后每个$2$人组里的$2$名参赛选手都下$1$盘棋（也就是每轮比赛都有$\lfloor n/2\rfloor$盘棋同时在下）。
————————————————————

由于围棋是很考实力的，所以我们假设每盘棋都是实力值较大的选手获胜。

最后我们根据$m$轮比赛的结果，为$n$名参赛选手排名。

问：如果我们要保证$n$名参赛选手的比赛排名都与他们的实力值相符，至少需要多少轮比赛？

对于较小的$n$，答案如下：

当$n=1$时，不需要比赛，所以$m=0$；

当$n=2$时，需要$1$轮比赛，所以$m=1$；

当$n=3$时，为了保证所有的情况都正确，需要$3$轮比赛，所以$m=3$；

当$n=4$时，为了保证所有的情况都正确，也需要$3$轮比赛，具体安排如下：

第$1$轮：$1$号选手对$2$号选手，$3$号选手对$4$号选手；
第$2$轮：$1$号选手对$3$号选手，$2$号选手对$4$号选手；
第$3$轮：$1$号选手对$4$号选手，$2$号选手对$3$号选手；

根据比赛结果，按照下面的方法排名：

赢$3$盘棋的选手为第$1$名；
赢$2$盘棋的选手为第$2$名；
赢$1$盘棋的选手为第$3$名；
没有赢棋的选手为第$4$名。

通过简单的证明可知，这样的排名保证正确，

但如果只进行$2$轮比赛，就无法保证所有可能的比赛结果都能给出正确的排名。

所以当$n=4$时，$m=3$。

对于较大的$n$，答案是多少呢？

056254628

如果轮数结束后，还存在没有比赛过的对手，且他们刚好水平排位中相邻，那么无法确定他们的排位。所以比赛的安排:1.要么所有的对手都相互比赛过2.要么根据比赛的结果安排下一轮，使得尽量安排水平相邻的对手比赛。

056254628

按照第1种安排方法: n=5 两两比赛共有10场比赛，每轮只能安排2场比赛，故需安排5轮。即5轮必能确定选手的排位。

056254628

5个选手abcde,按照水平从低到高为12345. 那么12,23,34,45的比赛必须要安排，且安排了这四场比赛，结果也就出来了。 如果运气好，两轮比赛把这四场比赛都安排了，那么两轮就可确定结果。但因为事先不知道选手水平，所以这种可能非常低。

dianyancao

猜测答案是： 基于比较的排序复杂度下限：\(\D\left\lceil\log_2\sum_{i=1}^{n}{\Big\lceil\log_2 i\Big\rceil}\right\rceil\) (\(\lceil\bullet\rceil\) 为向上取整)

tommywong

先讨论1到6 n:1,2,3,4,5,6 m:0,1,3,3,5,6

dianyancao

我上面的式子是错误的。 修改了一下式子，用程序计算得到的结果为： 不知道是否和Fans的输出结果是否相同 n=1,m=0 n=2,m=1 n=3,m=3 n=4,m=3 n=5,m=5 n=6,m=5 n=7,m=5 n=8,m=5 n=9,m=6 n=10,m=5 n=11,m=9 n=12,m=6 n=13,m=7 n=14,m=7 n=15,m=7 n=16,m=7 n=17,m=7 n=18,m=9 n=19,m=9 n=20,m=10 n=21,m=10 n=22,m=9 n=23,m=9 n=24,m=9 n=25,m=9 n=26,m=9 n=27,m=9 n=28,m=8 n=29,m=10 n=30,m=11 n=31,m=11 n=32,m=9 n=33,m=9 n=34,m=9 n=35,m=9 n=36,m=10 n=37,m=10 n=38,m=9 n=39,m=9 n=40,m=13

hujunhua

m(n)应该是单增函数吧

dianyancao

按#6的思路，得到如下结果： 其中的m(n)是答案的一个上界，是否可以再降低上界呢？ [local]2[/local]

dianyancao

图片发不上来。。 其中的X全部表示小于，当然也可以全部表示大于