文章
2049

有人对xkcd的谜题感兴趣吗?

爱狗却养猫 饭丝

原链接https://wiki.xkcd.com/irc/Puzzles 因为安全问题无法访问,好在我存有一些备份。

先随便贴几个我觉得很有意思的:

  1. Ants: 100 ants (zero-length points) walk on a meter stick (a line) at 1 cm/second. When two ants collide, they both reverse direction. If an ant reaches the end of the stick, it falls off. What arrangement of ants maximizes the time before all ants have fallen off? How long can they last? 蚂蚁:有100只蚂蚁(假设长度为0)在一个一米长的棍子上以1厘米每秒的速度行走。如果两只蚂蚁相撞,它们会各自调头向反方向走。如果有一只蚂蚁碰到了棍子的一端,它会掉下去。怎样安排蚂蚁的初始位置,使所有蚂蚁掉落前的时间最大化?它们最长能在棍子上待多久?

  2. Smurfs and Gargamel:Gargamel has captured 100 Smurfs. Feeling confident he proposes the following game: He will exchange the white hats of an undefined number of smurfs with red hats. No smurf knows his own color. All smurfs can see each other, but they have no other means of communication. Then, each Smurf (order selected by Gargamel) should say the color of his hat (loudly so that everyone can hear it). If it is correct, then he lives, otherwise he dies. After a short discussion the smurfs accept. They know that the first Smurf to be chosen might die, but all 99 other smurfs will survive. How? Note: as usual no trick. Nothing time-related... 蓝精灵和格格巫:格格巫抓住了100个蓝精灵。出于自信,他建议了如下游戏:他会将一部分蓝精灵的白帽子换成红帽子。没有蓝精灵知道自己帽子的颜色。蓝精灵可以看到其他蓝精灵,但(在戴上帽子之后)他们没有其他沟通的办法。然后,蓝精灵按照格格巫选择的顺序,一个接一个说出自己帽子的颜色(说得足够响,让所有人可以听到)。如果正确,他就能活下来,否则他就要死去。 在短暂的讨论后,蓝精灵们接受了提议。他们知道,第一个被选中说话的蓝精灵可能死去,但是其他的99个蓝精灵会活下来。他们的计划是什么呢?

  3. Smurfs and Gargamel Alternative 1: Suppose that instead of just red and white hats, Gargamel randomly distributes n different hat colors (including white) among the smurfs, where the number of colors n is less than 100, the number of smurfs. Assume the smurfs know all the possible hat colors. How many smurfs must be put at risk of death before the rest are guaranteed to survive? 蓝精灵和格格巫版本2:假设格格巫不仅仅分配红色和白色帽子,而是在蓝精灵中随机分配n种不同颜色的帽子(包括白色),n小于100(即蓝精灵的数量)。假如蓝精灵们知道所有可能的帽子的颜色。在余下的蓝精灵保证存活前,有几个蓝精灵要冒可能送命的危险?

  4. Smurfs and Gargamel Alternative 2: what if the Smurfs are positioned in a long queue such that each Smurf can only see the hats of the Smurfs in front of him? Assume Gargamel always starts at the back of the queue and works forward. 蓝精灵和格格巫版本2:(依然是红、白帽子)假设蓝精灵站在一个长长的队伍里,每个蓝精灵只能看到他前面的帽子颜色。会怎么样呢?这里假设,格格巫总是让队伍最后的蓝精灵先发言,然后一个个从后往前。

  5. Smurfs and Gargamel Alternative 3: Suppose there are infinitely many Smurfs (perhaps uncountably many) and all at once each must say the color of his own hat. Again, the Smurfs formulate a plan (perhaps using a bit of Smurf magic) and accept, knowing that a finite number may die but the rest will live. How? 蓝精灵和格格巫版本3:(依然是红、白帽子)假设现在有无限数量的蓝精灵(数不清的数量),所有蓝精灵必须同时说出自己帽子的颜色。蓝精灵们(也许是通过魔法)再一次形成了一个计划,接受了提议。他们知道有限数量的蓝精灵可能死去,但余下的都会存活。如何达到呢?

菜单
  1. 梅菲斯特  

    第二题好像看过解释,但是有点复杂……

  2. 梅菲斯特  

    懒得算了,瞎猜一下。每个精灵已知的条件就是“自己是第几个发言”和“看到了多少红/白帽子”,猜测计划会将二者关联起来。

  3. 爱狗却养猫 饭丝
    爱狗却养猫  

    @梅菲斯特 #1 我自己当时是跳过蓝精灵系列的,现在在翻出来看看,或许有新灵感。

  4. 爱狗却养猫 饭丝
    爱狗却养猫  
    1. 想到了,自问自答下。关键应该是奇数偶数。由于只有两种颜色的帽子,只要约好第一个蓝精灵说的颜色对应着他看到的红帽子(或者白帽子)的奇偶状态就可以了。其他蓝精灵可以根据看到的帽子颜色分布轻易算出自己的帽子颜色。 也就是说,在两种颜色、可以看到其他人帽子的情况下,只要一个“二元”的有效信息就可以知道自己的颜色。
  5. 梅菲斯特  

    @爱狗却养猫 #5 我也想到了奇偶数…… 这么看解题思路好像并不是很困难?

  6. 爱狗却养猫 饭丝
    爱狗却养猫  

    @梅菲斯特 #4 【谜题2】我的理解是这样的:格格巫安排的顺序,蓝精灵商量的时候应该是不知道的;红帽子理论上可以为0~100中任何一个数。 “看到了多少红/白帽子”确实是已知信息。

  7. 梅菲斯特  

    @爱狗却养猫 #2

    感觉有的条件还不够明确……

    1. 红帽子是一定有,还是可以为0?白帽子呢?

    2. 格格巫安排的发言顺序,蓝精灵们商量的时候知道吗?

  8. 爱狗却养猫 饭丝
    爱狗却养猫  

    【谜题3】如果用懒人无逻辑顺推法,两种颜色(n=2)要牺牲一个蓝精灵,那n种颜色就是牺牲n-1个蓝精灵了。嗯,很有道理。:P

  9. 梅菲斯特  

    每隔一人牺牲一个去告知前面那人的帽子颜色 (话说这些题有没有标准答案

  10. 梅菲斯特  

    @爱狗却养猫 #6

    第三题如果约定前几个人每个暗示一种颜色的话,大概答案就是n人吧,不知道有没有更好的方法

  11. 爱狗却养猫 饭丝
    爱狗却养猫  

    @梅菲斯特 #7 是啊,好像比我原先想的要简单!有些题看着很复杂,想明白了就是一句话的恍然大悟;有些题才几句话,解释要一篇论文,哈哈。

  12. 梅菲斯特  

    第五题我感觉无限这个条件好微妙,虽然可以划分成有限数量的群体(比如10000000000000个蓝精灵为一组然后照第一题办理),但是数学告诉我们,这样划分也是划分出无限个集合……

  13. 梅菲斯特  

    hmmm而且这样就不算同时说出了?

  14. 梅菲斯特  

    第四题的意思难道是有一半人冒生命危险?

  15. 爱狗却养猫 饭丝
    爱狗却养猫  

    @梅菲斯特 #13 没有标准答案。原来的xkcd的页面上也只有讨论。不过也就是因为这样才有趣。:)

  16. 爱狗却养猫 饭丝
    爱狗却养猫  

    @梅菲斯特 #11 是的,最直接的方法就是这种了。不知道能不能将信息进一步压缩。

  17. 爱狗却养猫 饭丝
    爱狗却养猫  

    @梅菲斯特 #12 或许可以说,至多一半人冒险。我又把原题读了一遍,排在最后的蓝精灵应该可以看到所有前面的(99个)蓝精灵的帽子颜色。

  18. 爱狗却养猫 饭丝
    爱狗却养猫  

    1-4都不难,5想不出来。

  19. 梅菲斯特  

    @爱狗却养猫 #19 是啊,无限这个条件让前面的可能性都失效了

  20. 梅菲斯特  

    第一题我算了一下,似乎总的时间是一致的?

  21. 爱狗却养猫 饭丝
    爱狗却养猫  
  22. 爱狗却养猫 饭丝
    爱狗却养猫  

    @梅菲斯特 #20 【谜题5】我想到一个思路,不过可能需要数学证明(或推翻)。每个人在无限的同伴中随机选择有限的n个人(n为奇数)的帽子颜色进行观察,然后说自己的帽子是多数的那个颜色。

  23. 梅菲斯特  

    @爱狗却养猫 #23 难点就在这里,n是个可数的数……

    如何实现“有限的人可能死去”呢?

    不管怎么分,这些集合的总合的基数和自然数集合基数应该是一样的…

    换句话说就是满足不了这个条件

  24. 星宿老仙  

    第一题,相遇时各自掉头往回走,和各自继续往前走是一样的,因为无须区分两只蚂蚁的身份。所以只要初始条件是所有蚂蚁都从棍子一端走向另一端,就能得到最大时间,每只都是 100 秒。

  25. 爱狗却养猫 饭丝
  26. 饱读书名  

    4 和 2 不是一样的么?

    最后一个蓝精灵的回答表明前面红帽子的数量是奇是偶;前一个蓝如果所见与后一人不同,自己就是红;再前面的蓝根据最后一个报出的奇偶数,和此后其他蓝报出红的数目计算自己是什么颜色。

  27. 饱读书名  

    5、大家都说是白色。

    在第二题的描述中隐含的意思是格格巫把有限个蓝精灵的帽子由白变成红,之后白的是无限个,红的是有限个。嘿嘿嘿嘿。

  28. 爱狗却养猫 饭丝
    爱狗却养猫  

    @饱读书名 #28 是这样的。赞👍。#27 嗯,如果红帽子是有限个就是这样;如果红帽子是无限个有解吗?