作者walkwall (会走路的墙)
看板puzzle
标题Re: [问题] 最强最弱的比赛场数
时间Sun May 26 08:29:13 2013
※ 引述《Arton0306 (Ar藤)》之铭言：
: 现在有16个队伍 要参加比赛
: 这比赛是强弱分明的 强者必胜(有递移律)
: 现在16队强弱都不一样
: 那麽最少要比几场才能「找出最强队和最弱队」
: 先列个比法
: 1.先两两分组比，赢的为胜部，输的败部，需8场
: 2.胜部有8队找出最强的，需7场
: 3.败部有8队找出最弱的，需7场
: 共22场，
: 请问有没有办法以更少的场数找出来？
: 没有的话可否证明？
首先, 定义队伍状态四种 : N-未比较 W-胜候选 L-败候选 X-非第一也非最後
一开始当然所有队伍都是处於N状态, 而结束状态则必须只有一W一L且其他为X
然而N状态的队伍经过一次比较後, 只可能转换成W或L,
W或L至少也要比一次後才可能转为X
因此我们可以把四状态的资讯量分别定义为 N:0 W:1 L:1 X:2
从开始的状态(N*16,资讯量0), 到结束的状态(W*1+L*1+X*14, 资讯量30)
要求出解共需30资讯量
接下来, 不管是什麽演算法, 如果资讯量无法到30, 就无法确定只剩一解
反过来说, 如果资讯量到30, 由於比较一次以後必然至少有一W, 所以就能确定只剩一解
所以现在的问题转换成 "最少需几次比较, 资讯量能到30?"
假定有个最佳的演算法, 考虑每次比较能获得的资讯量,
演算法能控制的是选用哪两个队伍对战, 但选定後用该组合的最低的资讯量考虑
这是因为所有演算法都应考虑其最差表现, 才知道最少可以几次判断出来
以你推文为例, 一次(W,N)的对战组合, 有可能获得1or2的资讯量, 最低为1
考量N,W,L,X四种状态的对战组合, 我们知道只有(N,N)的最低资讯量为2,
(W,L) (W,X) (L,X) (X,X)的最低资讯量为0, 其他最低为1
因此要达到最小次数, 就要尽量选(N,N),
但是(N,N)每次配完後会少掉两个N (一定一个变W一个变L), 所以(N,N)只能用8次
这样资讯量达到16, 剩下的不管什麽猜法资讯量最多为1, 所以至少要14次
故8+14=22为最少对战次数得证
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.117.168.77
1F：推 isnoneval:非常好的证明架构 05/26 11:34
2F：推 isnoneval:帮忙补充说明：(W,N) 的对战结果里得到 1 的资讯量 05/26 11:40
3F：→ isnoneval:「在任何方法中的任一步骤都必然有可能发生」 05/26 11:41
4F：→ isnoneval:因为 N 状态必然是尚未进行过任何对战 05/26 11:41
5F：→ isnoneval:所以在那个当下 N 必然有可能是实质冠军 05/26 11:41
6F：→ jurian0101:我想问 考古题"比赛赛马"[puzzle] 能否用资讯量方式解? 05/26 21:53
7F：→ walkwall:这个证明的原始出处是针对这个题目本身 用来证明赛马问 05/26 23:55
8F：→ walkwall:题可能要仔细想想能不能设计出来 不过是很有趣的方向 05/26 23:56