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