Cheating husbands - rFronteddu/general_wiki GitHub Wiki

• 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?

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.