→ XII :應該可從例子中看出證明~ 07/21 18:57
推 firce7772004:推一般解 07/21 20:50
推 coolbetter33:有點神 07/21 21:20
推 FocusE :推... 07/21 22:21
推 t0444564 :先推! 晚點看 07/21 23:13
推 jonathanmeow:數字解就很難了 推一般解 真神... 07/25 21:06
※ 引述《FocusE (專注)》之銘言：
: 假設 55 位同學每人各得知一條消息，
: 且任意兩人所得的消息都不相同。
: 他們用電話兩兩互相告訴對方所得知的全部消息。
: 若每次通話都使用 1 分鐘，
: 則至少需要幾分鐘才能使每個人都知道全部的消息?
: 答案是7分鐘
: -------------------------------------------------
: 想法
: 如果是32人 則能在5分鐘完成
: 如果剩下23人也能在5分鐘完成
: 就能在7分鐘讓55人知道全部的消息
: 但23人我只找得到6分鐘完成的方法
: 想問問高手們這題需要怎樣的想法才能解決
終於算出一般解了...
設有n人,每人有獨家八卦
每次二人通話可告訴對方所得知的全部消息,每次通話1分鐘
=> 最少需ceiling{㏒_2(n)}+{n mod 2}分鐘可使每個人知道全部消息
.............................................................
Proof.
設n人最少需a_n分鐘
① a_n≧ceiling{㏒_2(n)}+{n mod 2}
❶若n為偶數:
∵得知1消息的人數每分鐘至多變2倍∴2^a_n≧n => n≧ceiling{㏒_2(n)}
❷若n為奇數:
設第1次第1人未通話
∵2^{a_n-1}≧n∴n≧ceiling{㏒_2(n)}+1
② a_n≦ceiling{㏒_2(n)}+{n mod 2}
❶若n=2^k(2r+1),k,r為正整數
將n人分成(2r+1)組,每組2^k人
可先用k分鐘使每組人都知道自己組內的所有消息
再將n人分成2^{k-1}群,每群2(2r+1)人,且每群恰含各組的2人
可用ceiling{㏒_2(2r+1)}分鐘使每群的人得知所有消息
eg.
1 2 12 34 1234 5123
3 4 51 23 4512 3451
5 1 => 45 12 => 2345 1234 => ok
2 3 34 51 5123 4512
4 5 23 45 3451 2345
❷若n=2r+1,r為正整數
可利用ceiling{㏒_2(2r+1)}+1分鐘使所有人知道所有消息
eg.
1 2 1~ 2 3~ 4 1~ 4 5~ 8 1~ 8 9~16
3 4 5~ 6 7~ 8 9~12 13~16 17~17~11 10~ 3
5 6 9~10 11~12 17~17~15 14~11 2~ 1~ 6 7~14
7 8 13~14 15~16 10~ 7 6~ 3 15~17~17~13 12~ 5
9 10 => 17~17 16~15 => 2~ 1~2 3~ 6 => 4~ 1~ 1~ 4 5~12 =>
11 12 14~13 12~11 7~10 11~14 13~17~17~15 14~ 7
13 14 10~ 9 8~ 7 15~17~17 16~13 6~ 1~ 1~ 2 3~10
15 16 6~ 5 4~ 3 12~ 9 8~ 5 11~17~17 16~ 9
17 2~1 4~ 1 8~1
1~16 17~17~3
2~ 1~ 1~14 15~17~17~ 5
4~ 1~ 1~12 13~17~17~ 7
6~ 1~ 1~10 11~17~17~ 9
8~ 1~ 1~ 8 9~17~17~11 => 除了一組為1~16其餘為1~17 => ok
10~ 1~ 1~ 6 7~17~17~13
12~ 1~ 1~ 4 5~17~17~15
14~ 1~ 1~ 2 3~17~17
1~16
證明不難~不過懶得打了XD
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.115.31.174
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1405940166.A.0B6.html