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

hujunhua

我试了一下n=6 的情况。
1、6阶完全图的共有15个最小边覆盖（每个最小边覆盖包含3条两两不相连的边），
2、6阶完全图的15条边划分为5个最小边覆盖，共有6种划分。并且，这6种划分是彼此同构的。

这就是说，如果不按前一轮比赛的结果安排下轮比赛，而是事先就安排好全部轮次的对阵表，那就不存在最优安排，因为所有的安排（只有6种）都是同构的。

如果存在可减少轮次的方案，必定是一种积分编排方案。

wayne

换句话说，是一种动态方案，m都不能确保是固定的值
m可以取 【1， C(n,2)/floor(n/2)】区间 所有可能的值

wayne

于是，按照fans的无视比赛历史战况的方案，
我们需要算 m 取1,2,3，...各种值 的概率 ，然后 给一个期望值？

streeling

对于n=5
若只通过4轮比赛就能保证对所有情况都能做出正确排名
那么，由于每轮比赛有一个人轮空，必有一个选手没轮空过
不妨设1号与其他4个选手都比赛过
当1号选手的实力值最大（或最小）时，通过这4场比赛没办法得出其他4个选手之间的任何序关系
而通过余下的4场比赛没办法保证对所有情况都能做出这4个选手的正确排名
（可分为某个选手比了3场和4个选手都比了2场两种情况，都易得出反例）
所以只通过4轮比赛不能保证对所有情况都能做出正确排名
而通过5轮比赛能保证对所有情况都能做出正确排名（每两个选手之间都比赛过）
所以m(5)=5

056254628

楼上的证明还是有漏洞。前三轮如果出现某人都胜或都负，第四轮就安排他轮空。所以就不会出现四轮都参加的人全胜或全负的情况。如果前三轮出现某人全胜且另一人全负，第四轮就只能安排其中一人轮空，这种情况出现只能说明你的安排有问题。在第三轮就安排前两轮全胜或全负的人轮空，就不会出现这种情况。

streeling

25# 056254628
确实有漏洞，这似乎让4轮的方案有可能成功。

streeling

不对，至少要5轮，有空补上这个漏洞

风云剑

看来和现在棋类比赛中常用的瑞士制和大循环差不多
人数为奇数时增加一个弱智机器人即可（即轮空者获胜）
大循环n-1轮搞定排名，每人都是n-1场，对阵安排在比赛前就安排好了
瑞士制比赛轮次不定，对阵安排也不确定，第一轮抽签决定，从第二轮开始依据比赛历史安排下一轮的对阵表，安排原则1）选择历史上没有和自己对阵过的选手，2）选择和自己排名最接近的选手，3）从排名第一的开始选择
实力在两端的选手可以很快出来个大概，但要完全排名，貌似也还是n-1场才行。

streeling

把n=5的证明贴上来
设五个人的是1,2,3,4,5
对只安排四轮的情况
不妨设第一轮的安排和结果为
1>2,3>4,5
如果第二轮5继续轮空，那么剩下两轮比赛5的两场不能保证确定5的排名
(不妨设1>2>3>4,那么5和1,2比时均负，和2,3比时均负，和3,4比时均胜，和1,3或2,4,或1,4比时介于中间，这时就不能确定5的排名)
所以第二轮轮空的不是5，不妨设安排1轮空，那么第二轮安排有且仅有三种可能：
安排一：5-2,3-4,1
安排二：5-3,2-4,1
安排三：5-4,2-3,1
对于安排一，当1,3,5实力值为前三时，前两轮未测出他们三人两两间的关系，也无法通过与2,4的关系链推出，为保证确定三人的排名，剩下两轮必要安排他们两两进行比赛，但这是不可能的
同样，对于安排三，当1,3,5实力值为前三时也不可能保证确定三人的排名。
对于安排二，当3实力值最大，2实力值最小时，第二轮结果是5<3,2<4,1，这时，1,4,5两两间的关系不确定，也无法通过与2,3的关系链推出，为保证确定三人的排名，剩下两轮必要安排他们两两进行比赛，但这是不可能的
所以四轮比赛无法保证能确定排名，$m(5)=5$

streeling

当n为奇数时，轮空可视为胜了一实力值为负无穷的0号选手，所以可以用m(n+1)轮比赛来保证能确定排名，所以$m(n)<=m(n+1)$
当n-1为偶数时，加上一实力值为负无穷的0号选手，这时就可以用m(n)轮比赛来保证能确定排名，所以$m(n-1)<=m(n)$
所以m(n)是单调不减函数。
我们由$m(6)>=m(5)=5$可以得出$m(6)=5$