[問題] 最強最弱的比賽場數
現在有16個隊伍 要參加比賽
這比賽是強弱分明的 強者必勝(有遞移律)
現在16隊強弱都不一樣
那麼最少要比幾場才能「找出最強隊和最弱隊」
先列個比法
1.先兩兩分組比,贏的為勝部,輸的敗部,需8場
2.勝部有8隊找出最強的,需7場
3.敗部有8隊找出最弱的,需7場
共22場,
請問有沒有辦法以更少的場數找出來?
沒有的話可否證明?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.36.36.150
推
05/26 01:56, , 1F
05/26 01:56, 1F
請問有更嚴謹的證明嗎?
那篇是比10個球
在找出最重的那個球時
假設我採取的策略是先任挑2個比,其它8個先等待
輸的進敗部
贏的那個繼續和剩下的其中一個比…
之後輸掉的那個如果是第一次比就輸也進敗部
最後從敗部中選出一個最輕球 而敗部中的最多可以到9個
這樣就要用8次了 加上找最重球的9次共17次
有沒有方式解釋不管任何一種策略
(ex 也許有某種比較策略 在最後一次比較時 同時得到最強最弱)
在我的例子中至少比22次?
※ 編輯: Arton0306 來自: 114.36.36.150 (05/26 03:06)
推
05/26 06:08, , 2F
05/26 06:08, 2F
→
05/26 06:10, , 3F
05/26 06:10, 3F
→
05/26 06:12, , 4F
05/26 06:12, 4F
→
05/26 06:14, , 5F
05/26 06:14, 5F
討論串 (同標題文章)