Cheating Husbands Puzzle

This classic brain teaser describes a closed community with strict rules about marital infidelity and public punishment, triggered only when a spouse can logically deduce a partner's guilt. Each woman has partial information about which husbands are unfaithful, but is blind to the status of her own, and all share the same public announcement that at least one cheating husband exists. The puzzle then focuses on what happens over several days as no expulsions occur, and how that collective silence becomes meaningful. It culminates when, after a specific number of days, a synchronized action finally takes place, revealing how many cheaters there must be.

The question leans heavily on common knowledge, recursive reasoning, and inductive logic on "what others think others know." An interviewer is watching whether the candidate can systematically build the reasoning from the simplest case upward, track others' hypothetical beliefs, and understand how time and the absence of action convey information. Strong answers structure the argument cleanly, avoid handwaving around the key induction step, and articulate why the symmetry and publicly known rules are crucial to making the deduction work.

What it tests

This problem class is governed by the principle of common knowledge and iterative logical deduction. When each agent knows something about others but not themselves, and all agents know the same rules and that everyone else knows the rules, the lack of an expected event (such as an expulsion) becomes informative. The key is that each agent reasons not just about what they see, but about what others see and what others expect to happen. This recursive reasoning allows agents to deduce their own status from the collective inaction over time, even when direct communication is forbidden. The pattern holds because the structure of knowledge is symmetric and the rules are public, so each agent can simulate what others would do in every possible scenario.