作者KasimR (我要考上啦～)
看板puzzle
標題[請問] 邏輯推理問題
時間Sun Sep 19 12:31:17 2010
※ [本文轉錄自 ask 看板 #1CbOEgXw ]
作者: KasimR (我要考上啦～) 看板: ask
標題: [請問] 邏輯推理問題
時間: Sun Sep 19 11:29:43 2010
假設有n個人各知道一件不同的八卦（所以共有n件八卦）
他們可以互相打電話交換他們已知的所有八卦
所以任何兩個人通完電話後，該兩個人所知道的八卦就一樣多
請問若要所有的人通通知道所有的八卦，最少需要幾通電話？
P.S. 假設每通電話只有兩方通話，沒有電話會議（三方以上 teleconference）
第二題：
前提：五位小姐排成一列，所有小姐的衣服顏色都不一樣，姓氏也不同，
養不同的寵物，喝不同的飲料，吃不同的水果。請問哪一個小姐養蛇？
線索：
A、林小姐穿紅色的衣服，翁小姐的寵物是狗，王小姐喝茶。
B、穿綠色衣服的小姐站在穿白色衣服小姐的左邊。
C、穿綠色衣服的小姐喝咖啡，吃西瓜的小姐養鳥。
D、穿黃色衣服的小姐吃柳丁，站在最中間的小姐喝牛奶，趙小姐站在最左邊。
E、吃橘子的小姐站在養貓小姐的隔壁，養魚的小姐隔壁是吃柳丁的小姐。
F、吃蘋果的小姐喝香檳，江小姐吃香蕉，趙小姐站在穿藍色衣服的小姐隔壁。
G、只喝開水的小姐站在吃橘子的小姐隔壁。
問題：請問哪一個小姐養蛇？
有人知道答案嗎？ 謝謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 124.8.157.25
1F：推 XA:樓下鴨皇 09/19 11:31
2F：→ fallheart:江小姐嗎?? 09/19 12:01
3F：→ benhut:puzzle 益智 ◎[益智] 拼圖‧解謎‧打北七 09/19 12:11
4F：→ KasimR:請問二樓是怎麼推的呢？ 09/19 12:30
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 124.8.157.25
5F：推 chyrliin:趙 王 林 江 翁 09/19 13:02
6F：推 chyrliin:黃 藍 紅 綠 白 09/19 13:02
7F：推 chyrliin:水 茶 奶 咖 檳 09/19 13:02
8F：推 chyrliin:柳 橘 西 蕉 蘋 09/19 13:03
9F：推 chyrliin:貓 魚 鳥 狗 09/19 13:03
10F：→ jurian0101:第一題我想是2N-3，有更優的解答嗎？ 09/19 13:40
11F：推 babufong:四個人好像四通電話就能解決？ 09/19 13:46
12F：推 joeyeh:請問第一題的n有下限嗎? 09/19 13:46
13F：推 joeyeh:是不是有篇論文叫"論隨機圖形的演化"在探討此類問題? 09/19 13:49
14F：推 jurian0101:樓上論文的作者... 09/19 14:03
15F：推 puzzlez:2個人1次 3個人3次 4個人4次 5個人7次 6個人9次...？ 09/19 16:30
16F：推 babufong:五個人好像六次就通了 09/19 17:10
17F：推 puzzlez:沒有哦 你忽略了3個人至少要3次.... 09/19 17:30
18F：→ puzzlez:哦 等等...是6次沒錯.... 09/19 17:32
19F：推 jurian0101:OMG, 類似加法鍊的東西出現了嗎 09/19 18:22
20F：推 joeyeh:一開始大家都知道一件八掛沒錯 但隨分散式傳播法則 09/19 18:47
21F：→ joeyeh:每個人從其他人身上得到的資訊量會以目前已散佈量呈指數 09/19 18:49
22F：→ joeyeh:請參考離散雜湊原理就會知道了 離主點越近倍增量越快 09/19 18:52
23F：→ joeyeh:但這個量在N點數小時探討沒辦法看出效果 09/19 18:54
24F：推 jurian0101:無量綱網路是這樣沒錯，那原題目的解法怎麼辦？ 09/19 22:26
25F：推 kuoll:第一題關鍵字gossip problem 最佳解2n-4(when n>4) 09/20 00:04
26F：→ kuoll:n人中挑選4個 其他人告訴4人任一 4人交換八卦後再告訴剩下人 09/20 00:06
27F：推 puzzlez:6人8次要怎麼做...真的有點難想耶...目前還想不出:-( 09/20 00:12
28F：推 jurian0101:把前8項0,1,3,4,6,8,10,12 丟到OEIS 得到上面關鍵字 ^^ 09/20 00:17
29F：推 andan:15 16 12 34 13 24 15 16...8次...kuoll的解法 09/20 00:17
30F：→ jurian0101:6人8次例如 1-2/2-3/4-5/5-6/2-5/3-6/6-1/6-4 09/20 00:19
31F：→ jurian0101:反正就是分兩組，每組至少2人，組裡每個人打給下一個 09/20 00:22
32F：→ jurian0101:接著兩組知道最多八卦的四人用兩通電話即可集全，再告 09/20 00:23
33F：→ jurian0101:訴剩下n-4人。因此總共需要2n-4通。 09/20 00:24
34F：推 puzzlez:ic 3q~~ 09/20 00:24
36F：→ squirrel1085:kuoll這解法好棒 2n-4簡單明瞭 09/20 00:29
37F：推 eistain:kuoll的方法我想問為什麼是4人..為什麼不能是一個人? 09/23 07:57
38F：推 eistain:喔喔 看出來了 09/23 07:59
39F：→ squirrel1085:你要把4人換成5人以上也沒關係 只是n>4適用範圍較廣 09/24 01:04