[問題] 最強最弱的比賽場數
看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者Arton0306 (Ar藤)時間12年前 (2013/05/26 01:03)推噓2(2推 0噓 3→)留言5則, 2人參與討論串1/3 (看更多)
現在有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
討論串 (同標題文章)
puzzle 近期熱門文章
5
21
PTT遊戲區 即時熱門文章
22
24
11
19
33
48