过河 (River crossing)、猜生日（Birthday problem）

---

[BACK to BLOG] [BACK to HOME]

River crossing

Q：黑夜，ABCD四个人要过桥，桥同时只能上2人，手电只有一个，没有手电不能动，因此为了打手电走得快的和走得慢的要同速。单程过桥，A需10分钟，B需5分钟，C需2分钟，D需1分钟。最快多长时间全员过桥？

思路是：

1. 需要尽可能减少过桥时间：组队过桥时，AB、AC、AD要10min，BC、BD要5min，CD要2min。
2. 黑夜时，对岸要派最快的人送手电回出发点：因为对岸的人需要折返才能再回对岸。

因为要让四个人都过桥至少要去两趟，因此黑夜时至少有一个人从对岸回来送手电。因为多回来一个人，所以多了一趟必须的去程，因此又需要多送一次手电。送两次手电需要两个不同的人从对岸回来。根据2，这两个人需要是最快的CD，两个人分别用2min和1min送手电，再用2min结伴回对岸。因此要送回手电并再让送手电的人都回对岸，总共需要至少5min。

根据1，不需要手电时，用时最少的选择是：AB+CD=12min（其余可能AC+BD=15，AD+BC=15，均大于12min）。此时只需让CD先去对岸，即可满足上述让CD送手电的情况。总共花掉17分钟。

Birthday problem

Q：我老板是A，我是B，我同事是C。已知A的生日是如下10天之一：

Mar 4, Mar 5, Mar 8

Jun 4, Jun 7

Sep 1, Sep 5

Dec 1, Dec 2, Dec 8

A只告诉了我月份，A只告诉了C天数。于是我先说：“我和C都不知道A的生日。”C听完说到：“我本来不知道，但我现在知道了。”我回答：“那我也知道了。”助理听完把老板的生日记录了下来。问：助理记了什么？

要点：不要自我代入是B，因为B有额外信息（月份），而我们解题人没有，只需要记住每个人在每个时间点掌握了什么信息。

思路是：

1. B确定C不知道生日，则排除天数唯一的Jun 7和Dec 2，因为是仅知道月份信息的B能得出这个信息，因此排除全部Jun和Dec，现在只剩Mar和Sep的5天。
2. C在知道1的情况下突然知道生日了，说明不是5号，只剩Mar4，Mar8，Sep1三天候选。
3. B说那我也知道了，证明不是Mar，则A生日是Sep 1。

设A的生日是x月y日，B知道x，C知道y。目前B视角生日是：x月{?}日，C视角是：{?}月y日。B说C不知道生日，证明x={3,9}，B视角不变，C视角变为{3,9}月y日。此时C说知道了生日，因此y={1,4,8}，此时B视角变为x月{1,4,8}日。因为此时B表示已经能知道具体生日 ，所以x=9，y=1.

[BACK to BLOG] [BACK to HOME]