作者Arton0306 (Ar藤)
看板puzzle
标题[问题] 最强最弱的比赛场数
时间Sun May 26 01:03:34 2013
现在有16个队伍 要参加比赛
这比赛是强弱分明的 强者必胜(有递移律)
现在16队强弱都不一样
那麽最少要比几场才能「找出最强队和最弱队」
先列个比法
1.先两两分组比，赢的为胜部，输的败部，需8场
2.胜部有8队找出最强的，需7场
3.败部有8队找出最弱的，需7场
共22场，
请问有没有办法以更少的场数找出来？
没有的话可否证明？
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.36.36.150
1F：推 LPH66:22 场确实最少 证明可参照 #18h2xIyS (那里只有数字不一样) 05/26 01:56
请问有更严谨的证明吗？
那篇是比10个球
在找出最重的那个球时
假设我采取的策略是先任挑2个比，其它8个先等待
输的进败部
赢的那个继续和剩下的其中一个比…
之後输掉的那个如果是第一次比就输也进败部
最後从败部中选出一个最轻球 而败部中的最多可以到9个
这样就要用8次了 加上找最重球的9次共17次
有没有方式解释不管任何一种策略
(ex 也许有某种比较策略 在最後一次比较时 同时得到最强最弱)
在我的例子中至少比22次？
※ 编辑: Arton0306 来自: 114.36.36.150 (05/26 03:06)
2F：推 walkwall:严谨证明我记得在某演算法课程看过 等我今天有空再打吧 05/26 06:08
3F：→ walkwall:不过数字也是不相同 所以22是否能证....我要先想想 05/26 06:10
4F：→ walkwall:想好了 还是现在打一打算了 05/26 06:12
5F：→ walkwall:其实证明精神跟LPH66说的那篇一样就是了 05/26 06:14