Today’s Riddler problem is another classic. The current incarnation of the puzzle is about error-prone mathematicians, while the classic version is about blue-eyed islanders.
A university has 10 mathematicians, each one so proud that, if she learns that she made a mistake in a paper, no matter how long ago the mistake was made, she resigns the next Friday. To avoid resignations, when one of them detects a mistake in the work of another, she tells everyone else but doesn’t inform the mistake-maker. All of them have made mistakes, so each one thinks only she is perfect. One Wednesday, a super-mathematician, whom all respect and believe, comes to visit. She looks at all the papers and says: “Someone here has made a mistake.”
What happens then? Why?
Here is the solution:
[Show Solution]
On the tenth Friday, all mathematicians will resign. To understand why this happens, we’ll use a recursive approach similar to what we did for the puzzle of the pirate booty.
For simplicity, we’ll say a mathematician is flawed if they made a mistake, and perfect otherwise. Let’s look at the world through the eyes of Alice, one of the ten mathematicians. Alice doesn’t know whether she is flawed or not. She does, however, know how many of her colleagues are flawed.
According to the problem statement, all the mathematicians are flawed. So Alice sees that all nine of her colleagues are flawed. Let’s solve a simpler version of the problem first. What if none of Alice’s colleagues were flawed? In this case, the news that “someone here has made a mistake” can only mean one thing: that “someone” must be Alice! So Alice will resign on Friday.
What if exactly one of Alice’s colleagues is flawed? Two possibilities:
- If Alice is perfect, then the flawed mathematician will see that everyone else is perfect and resign on Friday, just as Alice would have done in the previous case when she saw her colleagues were all perfect.
- If Alice is flawed, then nothing happens on Friday. Alice then deduces that she must be flawed and resigns on the next Friday.
What if exactly two of Alice’s colleagues are flawed? Two possibilities:
- If Alice is perfect, then each flawed mathematician sees one other flawed mathematician. As in the previous case, we expect them to both resign on the second Friday.
- If Alice is flawed, then nothing happens on the second Friday. In that case, Alice will know of her flaw and resign on the third Friday.
The pattern is clear: if Alice has $k$ flawed colleagues but Alice is perfect, then the flawed mathematicians all resign on the $k^\text{th}$ Friday. If Alice is flawed, then nothing happens on the $k^\text{th}$ Friday, and Alice resigns on the $(k+1)^\text{st}$ Friday (along with all the other flawed mathematicians). In particular, if all ten mathematicians are flawed as in the problem statement, they all resign on the tenth Friday.
But but but…
It seems that we have a paradox — we aren’t telling the mathematicians anything they don’t already know! Each mathematician can clearly see that they have flawed colleagues, so why should explicitly announcing this fact make any difference? The answer lies in the distinction between mutual knowledge and common knowledge.
If everybody knows some proposition $P$ to be true, then $P$ is mutual knowledge. However, if everybody knows $P$, and everybody knows that everybody knows $P$, and everybody knows that everybody knows that everybody knows $P$, and so on, then $P$ is common knowledge. Although the fact that there is at least one flawed mathematician is mutual knowledge, it is not common knowledge. When the super-mathematician makes her announcement that there is at least one flawed mathematician, it becomes common knowledge, and this makes all the difference.
Rather than giving a detailed solution, I will defer to some other existing solutions online that are already well-explained. No need to reinvent the wheel! Here are some pointers.
In order for the deeply nested meta-knowledge reasoning to happen it must be common knowledge that they all have perfect and deep reasoning skills. But clearly all of them have considerable doubts this is the case given all the paper mistakes they all know everyone else has made (I think it’s safe to say these aren’t spelling mistakes or typos but math related, or they wouldn’t feel so ashamed of it to the point of resigning).
Since they all know at least the other 9 are flawed then none can be assured all the others will reason through to the bitter end because, even if none of them were to make a mistake in their own reaoning, they can’t be sure that the others would be sure of this. Even worse, since the visiting super-mathematician made it common knowledge that at least one is flawed, that means they all now know it’s guaranteed that none would be able to get past this uncertainty about the others.
But this common knowledge isn’t even needed, just having mutual knowledge that a single one is flawed would be enough to guarantee that everyone’s nested logical chain of deductions will break at some point (they might believe perhaps just one does reason through it and just one might resign on the 10th Friday, they might think that but it wouldn’t happen, since all actually know 9 are flawed).
I think all would realize that the induction would most likely break down on the 3rd or at most the 4th nested meta-knowledge level. They all know there’s at least 9 flawed, so they can’t be sure none will make a single mistake when trying to reach that minimum required 9th level of “I (mathematician A) know at least 9 flawed, and I know that B knows at least 8 flawed, and I know she knows that C knows at least 7 flawed, and those know D knows 6… [etc repeated for all 9] and furthermore all know that all will reason as such and know that they all know that… [etc] that all will reason through this correctly”. So, none resigns on any Friday. 🙂
I know this is not in the spirit of the original blue-eyed islanders puzzle. But why would Oliver introduce precisely this type of uncertainty about their math/logic competency in this particular variation with far from perfect mathematicians, if it’s not precisely to call attention to this missing premise, that in order for the chain in meta-knowledge reasoning to occur, it must necessarily be also common knowledge that they’re all perfectly rational and flawless logicians? Indeed, the problem as stated everywhere else I’ve seen it includes such a statement “they all know they’re highly logical, and they know they all know this, and they know they know they know this, and so on”.
But Oliver or the puzzle creator didn’t say any of it, and instead added language that introduces significant doubt about the reasoning skills of not just one (which would’ve been enough) but of all of these agents. Perhaps the omision was a lapse, but I’d prefer to think it was intentional (particularly given this one’s such a well known classic it might require a tricksy twist like this to keep puzzlers on their toes and not just answer out of memory, or worse, googling for the answer which would be quite silly).
Or, if we do take for granted that it’s common knowledge for all of them that they’re all highly logical, I can think of another twist that prevents any and all resignations.
If they actually care for each other’s well being (or at least their faculty’s since they in fact have a scheme to avoid resignations), then all one of them has to do is, right after the unfortunate announcement by their esteemed super-mathematician, just take out their phone and pretend to have been on a call which prevented them from hearing the announcement. Or pretend they were in the bathroom: “Oh, did I miss anything important?”
The mathematician doing this knows it would then guarantee that none of the others can continue with the nested meta-knowledge induction all the way through, and all would know no other can either, so none would deduce their paper mistakes and once again none would resign on any Friday.
Ah, but then each of them would arrive at this same ruse as the best solution to avoid resignations, and thus an awkward but quite funny situation would ensue in which several (all?) tried to claim they missed the announcement. Of course none would tell any of it to the ones who claimed not to have heard it, knowing that this would reinstate the fateful chain of reasoning that they each privately know would end in 9 or all resigning.