出轨丈夫悖论
Cheating Husbands
题目详情
某镇有 100 对夫妻。部分丈夫出轨。每位妻子都知道其他丈夫是否出轨，但不知道自己丈夫是否出轨。若一位妻子能逻辑上确定丈夫出轨，她会在午夜把丈夫赶出去。
镇长公开宣布“至少有一名丈夫出轨”。宣布后大家不再交流。
前 9 夜无人被赶走，第 10 夜有一些丈夫同时被赶出。问共有多少名出轨丈夫？
A certain town comprises of 100 married couples. Some husbands secretly cheat on their wives. All wives know about the nature of every husband except their own. When a wife concludes that her husband cheated, she kicks her husband into the street at midnight. All husbands remain silent about their secret. One day, the mayor of the town announces to the whole town that there is at least 1 cheating husband in the town. After announcement, no one talks, waiting for someone to get kicked. Till 9th night from announcement, no husband was kicked, but on the 10th night, some husbands got kicked out simultaneously. How many are they?
Hint
What happens if only one husband cheated?
解析
答案是 10 人。
归纳思路：
- 若仅 1 人出轨，被出轨妻子在听到“至少 1 人出轨”后立刻确定是自己丈夫，第 1 夜赶走。
- 若有 2 人出轨，这两位妻子都看到“只有 1 人出轨”的表象；若第 1 夜没人被赶，她们在第 2 夜推出自己丈夫也出轨，于是第 2 夜同时赶走。
- 一般地，若有 人出轨，就会在第 夜同时发生。
因此第 10 夜发生，说明恰有 10 人出轨。
Original Explanation
Solution
It must be 10 husbands kicked out. If there was only 1 cheating husband in the town, there will be 99 women who know exactly who the cheater is. The 1 remaining woman, who is being cheated on, would have assumed there are no cheaters. But now that the mayor has confirmed that there is at least one cheater, she realizes that her own husband must be cheating on her. So her husband gets kicked on the day of the announcement.
Now let’s assume there are 2 cheaters in the town. There will be 98 women in the town who know who the 2 cheaters are. The 2 wives, who are being cheated on, would think that there is only 1 cheater in the town. Since neither of these 2 women know that their husbands are cheaters, they both do not report their husbands in on the day of the announcement. The next day, when the 2 women see that no husband was kicked, they realize that there could only be one explanation – both their husbands are cheaters. Thus, on the second day, 2 husbands are kicked.
Through induction, it can be proved that when this logic is applied to n cheating husbands, they are all kicked on the n th day after the mayor’s announcement. Hence it must be 10 husbands kicked in our case.