Solve The Mystery Of The Mathematical Mistakes

A university has ten mathematicians, each so proud that the moment she learns she has made a mistake in a paper, she resigns the following Friday. To spare each other, whenever one spots an error in another’s work she tells everyone except the author. Every mathematician has in fact erred, so each believes herself the only flawless one. One Wednesday a visiting super-mathematician, universally trusted, examines all the papers and announces: “Someone here has made a mistake.” What happens, and why?

The Riddler, FiveThirtyEight (Larry Denenberg)(original post)

Solution

All ten resign at once, on the tenth Friday: $$\boxed{\text{all ten resign on the 10th Friday}}.$$ The puzzle’s sting is that the visitor announces nothing new. Every mathematician already knew that someone had erred, since each can see the other nine. What she lacked was common knowledge: not just that everyone knows it, but that everyone knows that everyone knows it, without end. The announcement supplies exactly that, and the silent Fridays then convert it into self-knowledge, one week per mathematician.

Climb the ladder. If there were just one mathematician, the visitor’s “someone” could only be her, so she resigns the first Friday. If there were two, each reasons: “If I am flawless, my colleague is the lone culprit and resigns this Friday.” When the first Friday passes in silence, each learns her premise was wrong, so both resign on the second Friday. With three, each waits to see whether the other two settle it by the second Friday as a pair, and when they do not, all three resign on the third. The argument propagates undimmed: with $k$ guilty mathematicians, each holds off until the $(k-1)$ others fail to resign on Friday $k-1$, and then all $k$ resign together on Friday $k$. Here every one of the ten is guilty, so the deduction completes on the tenth Friday and the whole department leaves in a single stroke.

The computation

Encode the epistemics directly. Start from every guilt-configuration consistent with “at least one mistake.” Each mathematician sees her colleagues’ guilt but not her own, so she resigns once that observation forces her into the guilty set in every world still possible. Each silent Friday deletes the worlds in which someone would have resigned, and the simulation reports the Friday on which the real configuration cracks.

from itertools import combinations

N = 10
guilty = frozenset(range(N))                                  # everyone has erred
worlds = {frozenset(c) for r in range(1, N + 1)              # "at least one mistake"
          for c in combinations(range(N), r)}

def knows(i, W, actual):                       # i sees all guilt but her own
    possible = [w for w in W if (w - {i}) == (actual - {i})]
    return bool(possible) and all(i in w for w in possible)

friday = 0
while True:
    friday += 1
    resign = [i for i in range(N) if knows(i, worlds, guilty)]
    if resign:
        print("Friday", friday, "resign:", resign)
        break
    worlds = {w for w in worlds                # a silent Friday prunes worlds
              if not any(knows(i, worlds, w) for i in range(N))}
# Friday 10 resign: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]