推 FocusE :好厲害 馬上來研究 07/21 07:51
※ 引述《FocusE (專注)》之銘言：
: 假設 55 位同學每人各得知一條消息，
: 且任意兩人所得的消息都不相同。
: 他們用電話兩兩互相告訴對方所得知的全部消息。
: 若每次通話都使用 1 分鐘，
: 則至少需要幾分鐘才能使每個人都知道全部的消息?
: 答案是7分鐘
: -------------------------------------------------
: 想法
: 如果是32人 則能在5分鐘完成
: 如果剩下23人也能在5分鐘完成
: 就能在7分鐘讓55人知道全部的消息
: 但23人我只找得到6分鐘完成的方法
: 想問問高手們這題需要怎樣的想法才能解決
1 min
1,2、.......、53,54 ...( 2人一組)(共54人)
55 :55 本次閒置
2 min
1,2,3,4、...、49,50,51,52 ...( 4人一組)(共52人)
53,54,55 :53,55交換
53,54 :54前次持有本次閒置
3 min
1,...,8、...、41,42,..,48 ...( 8人一組)(共48人)
49,...,55 :49,53交換、50,55交換
49,...,54 :51,54交換
49,...,52 :52前次持有本次閒置
4 min
1,..,16、...、33,34,..,48 ...(16人一組)(共48人)
49,50,51,...,55 :49,51交換、50,52交換、53,54交換( 3組共 6人)
49,50,51,...,55 :55前次持有本次閒置
5 min
1,2,3,4,..............,32 ...(32人一組)(共32人)
33,34,35,...,55 :33,49交換、34,50交換、...、39,55交換( 7組共14人)
33,34,35,...,48 :40,41,42,43,44,45,46,47,48前次持有本次閒置
6 min
全部持有 :1～14與第 5 min的14人兩兩交換(14組共28人)
其餘不論 :本次閒置(共27人)
7 min
全部持有 :前次未全部持有者與全部持有者兩兩交換(27組共54人)
全部持有 :55前次持有本次閒置
---------------------------------------------------------------------------
01~32，共32人，在5min內完成交換
得到 32 人取得01~32的訊息
***************************************************************************
33~48，共16人，在4min內完成交換
得到 16 人取得33~48的訊息
***************************************************************************
49~55，共 7人，在4min內完成交換，換法如下：
1min : 49,50、51,52、53,54，55閒置
2min : 49,51、50,52、54,55，53閒置( 4人取得49~52， 2人取得53~55)
3min : 49,54、50,55， 51,52,53閒置( 4人取得49~55)
4min : 49,51、50,52、53,54，55閒置( 7人取得49~55)
得到 7 人取得49~55的訊息
///////////////////////////////////////////////////////////////////////////
5min : 33~39 與 49~55 兩兩一組交換( 7組共14人)
得到 14 人取得33~55的訊息
6min : 01~14 與 (33~39 & 49~55 ) 兩兩一組交換(14組共28人)
得到 28 人取得01~55的訊息
7min : 剩餘者與 (01~14 & 33~39 & 49~55) 兩兩一組交換(27組共54人)
得到 55 人取得01~55的訊息，其中有一人已於第6min取得
---------------------------------------------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.226.147.74
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1405875062.A.162.html
※ 編輯: csihcs (36.226.147.74), 07/21/2014 02:03:20