作者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