[請問] 邏輯推理問題

[KasimR (我要考上啦～)]

※ [本文轉錄自 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
推 XA:樓下鴨皇
→ fallheart:江小姐嗎??
→ benhut:puzzle       益智 ◎[益智] 拼圖‧解謎‧打北七
→ KasimR:請問二樓是怎麼推的呢？
--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 124.8.157.25
推 chyrliin:趙　王　林　江　翁
推 chyrliin:黃　藍　紅　綠　白
推 chyrliin:水　茶　奶　咖　檳
推 chyrliin:柳　橘　西　蕉　蘋
推 chyrliin:貓　魚　鳥　　　狗
→ jurian0101:第一題我想是2N-3，有更優的解答嗎？
推 babufong:四個人好像四通電話就能解決？
推 joeyeh:請問第一題的n有下限嗎?
推 joeyeh:是不是有篇論文叫"論隨機圖形的演化"在探討此類問題?
推 jurian0101:樓上論文的作者...
推 puzzlez:2個人1次 3個人3次 4個人4次 5個人7次  6個人9次...？
推 babufong:五個人好像六次就通了
推 puzzlez:沒有哦 你忽略了3個人至少要3次....
→ puzzlez:哦  等等...是6次沒錯....
推 jurian0101:OMG, 類似加法鍊的東西出現了嗎
推 joeyeh:一開始大家都知道一件八掛沒錯 但隨分散式傳播法則
→ joeyeh:每個人從其他人身上得到的資訊量會以目前已散佈量呈指數
→ joeyeh:請參考離散雜湊原理就會知道了 離主點越近倍增量越快
→ joeyeh:但這個量在N點數小時探討沒辦法看出效果
推 jurian0101:無量綱網路是這樣沒錯，那原題目的解法怎麼辦？
推 kuoll:第一題關鍵字gossip problem  最佳解2n-4(when n>4)
→ kuoll:n人中挑選4個 其他人告訴4人任一 4人交換八卦後再告訴剩下人
推 puzzlez:6人8次要怎麼做...真的有點難想耶...目前還想不出:-(
推 jurian0101:把前8項0,1,3,4,6,8,10,12 丟到OEIS 得到上面關鍵字 ^^
推 andan:15 16 12 34 13 24 15 16...8次...kuoll的解法
→ jurian0101:6人8次例如 1-2/2-3/4-5/5-6/2-5/3-6/6-1/6-4
→ jurian0101:反正就是分兩組，每組至少2人，組裡每個人打給下一個
→ jurian0101:接著兩組知道最多八卦的四人用兩通電話即可集全，再告
→ jurian0101:訴剩下n-4人。因此總共需要2n-4通。
推 puzzlez:ic   3q~~
→ jurian0101:http://0rz.com/u3KSQQ :連作者自己都覺得很無謂XD
→ squirrel1085:kuoll這解法好棒 2n-4簡單明瞭
推 eistain:kuoll的方法我想問為什麼是4人..為什麼不能是一個人?
推 eistain:喔喔 看出來了
→ squirrel1085:你要把4人換成5人以上也沒關係 只是n>4適用範圍較廣