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