We have a feel for induction now. We’ve seen how it works, we’ve seen it in action, and we’ve seen how easy it can be to make a mistake in applying it. We will now make use of it—carefully—to solve three puzzles. Each solution is, at best, surprising, and at worst, counter-intuitive. Induction will be the means by which we extend our intuitions from simple situations, where they are strong, to the apparently complex, where they often falter. The chains of reasoning involved are made up of very simple, repetitive pieces, but they can extend so long as to be completely unintelligible without some systematic method of analysis. Induction plays precisely this role.

Puzzle 1

The first puzzle I want to consider comes from [2]. It is about a game.
Two people sit facing each other, call them Alexander and Kathleen; these are the players. A third person secretly writes two consecutive natural numbers on two slips of paper, and tapes each piece on the two players’ foreheads (one on each). The third person then leaves the room (or sits quietly); his role in the game is finished.

Alexander can see the number taped to Kathleen’s forehead, and likewise she can see the number taped to his forehead. So they both know the number that’s not their own. They also both know that the two numbers are consecutive.

One player, say Alexander, begins the game by asking Kathleen if she knows what her number is. If she does, she says so and the game ends. If not, Alexander’s turn ends and Kathleen gets her chance to ask him if he knows his number. As before, if he does then he says so and the game ends. Otherwise, it becomes his turn again, and he repeats his original question to Kathleen. This back and forth questioning continues until someone finally says “Yes”, if ever. The question is:

Does this game ever end?

Sometimes? Never? Always?
One caveat: we must assume that the two players are ‘perfect reasoners’, so that if there was some way for either of them at any point to deduce their own number then they would do it. Without this assumption, whether or not the game ever ends might depend on whether or not one of the players is clever enough, and this kind of question doesn’t lend itself to a mathematical answer.

Intuitively, we might imagine the game running as follows. Say Alexander’s number is 12. Kathleen can see this, so she knows that her number is either 11 or 13. But there’s no way to figure out which, so when Alexander asks her if she knows what her number is, she is forced to respond in the negative. Alexander is in the same position: he can see Kathleen’s number and so he can narrow the possibilities for his own number down to two, but he can’t decide between them. And since asking the same person the same question over and over again doesn’t tend to generate any new answers (barring annoyed quips), it seems that this game is doomed to never end.

But this isn’t quite true, as you may have already realized. What if one of the players, say Kathleen, has the number 1 taped to her forehead? Then when Alexander sees it, he can reason that his number is either 0 or 2—but wait! The number 1 is the lowest of the natural numbers*, so that rules 0 out. Thus Alexander knows that his number must be 2, so the game will end as soon as he is asked, which will be either on the first or the second turn, depending on who goes first.

In fact, the game always ends. This is especially surprising because it seems reasonable to expect that if the game doesn’t end on the first two turns, then it will never end, since thereafter the players are just repeating the same question over and over. But in fact each response of “No” by one of the players adds a little piece of genuinely new information into the mix. Imagine that Alexander sees the number 2 instead of 1 on Kathleen’s forehead. Then he is unable figure out whether his own number is 1 or 3. However, when he asks Kathleen whether or not she knows her own number, if she says no then this tells him that she can’t be seeing the number 1 on his forehead! If she were, then she would know that her number is 2, as we reasoned before. This then allows Alexander to deduce that his number is in fact 3.

The reasoning above can be generalized to produce an inductive argument: we will prove that the game always ends in a number of turns no more than twice the lower of the two numbers written on the slips of paper. More formally, let n denote the lower of these two numbers; we will prove by induction on n that the game will end in no more than 2n turns.

The ‘base case’ n = 1 corresponds to the setup where one of the numbers is 1 and the other is 2, which we have already seen leads to a game which ends in no more than 2 turns.

Now the inductive step: assume that if the lower of the two numbers is less than or equal to n, then the game ends in at most 2n turns. We need to show that if the lower of the two numbers is n + 1, then the game ends in no more than 2(n + 1) turns.

So suppose that the two numbers are n + 1 and n + 2. Suppose also that turn 2n has passed and the game has not ended. It is now turn 2n + 1. By the inductive hypothesis, this means that the lower of the two numbers must be at least n + 1, since otherwise the game would have already ended by turn 2n. Therefore the player whose turn it is to answer the question, say Kathleen, can deduce that the lowest possible number written on either of the slips of paper is n + 1. There are two cases to consider.

First, if Kathleen sees the number n + 1 on Alexander’s head, then she can figure out that her own number must be n + 2, since n was already ruled out as a possibility.

On the other hand, if she sees the number n + 2 on Alexander’s head, then perhaps she can’t tell whether her own number is n + 1 or n + 3. The turn might pass to Alexander, making it turn number 2n + 2. Alexander looks out and sees the number n + 1 on Kathleen’s head, which allows him to deduce that his own number must be n + 2, for the same reasons given above. Thus the game ends in at most 2n + 2 = 2(n + 1) turns. This completes the induction.



These exercises are challenging.

Puzzle 2

The second puzzle I want to discuss is a popular one that has appeared in many forms. One particularly nice formulation of it can be found as an exercise in [3], pages 34-35. I reproduce it here:

University B. once boasted 17 tenured professors of mathematics. Tradition prescribed that at their weekly luncheon meeting, faithfully attended by all 17, any members who had discovered an error in their published work should make an announcement of this fact, and promptly resign. Such an announcement had never actually been made, because no professor was aware of any errors in her or his work. This is not to say that no errors existed, however. In fact, over the years, in the work of every member of the department at least one error had been found, by some other member of the department. This error had been mentioned to all other members of the department, but the actual author of the error had been kept ignorant of the fact, to forestall any resignations.

One fateful year, the department was augmented by a visitor from another university, one Prof. X, who had come with hopes of being offered a permanent position at the end of the academic year. Naturally, he was apprised, by various members of the department, of the published errors which had been discovered. When the hoped-for appointment failed to materialize, Prof. X obtained his revenge at the last luncheon of the year. “I have enjoyed my visit here very much,” he said, “but I feel that there is one thing that I have to tell you. At least one of you has published an incorrect result, which has been discovered by others in the department.” What happened the next year?

Like the previous puzzle, we can use induction to break this problem up into more manageable chunks. We can start to get a feel for how induction might apply by examining some simpler versions of the same question; specifically, we can change the total number of professors from 17 to any other number n and see what happens.

The case n = 1 is a silly one, since in this situation there would be no one to apprise Prof. X of the single tenured professor’s mistake to begin with. So let’s move on.

Consider the case n = 2. Here we have two tenured professors, each with a published error that they don’t themselves know about, but each knows about the error that the other has published. When Prof. X leaves in a huff, he informs the two that at least one of them knows of an error published by the other one. Then what? At the next luncheon meeting, the two professors stare at one another. Both can reason along the following lines:

“If my colleague over there didn’t know of any errors I have published, then she would know that Prof. X was referring to me when he said that one of us did know of an error. That would lead her to deduce that she has, in fact, published an error. But she hasn’t deduced that! She’s just staring at me. That means that she must know of an error that I’ve published. Which means that I’ve published an error, so I have to resign.”

Since both professors can reason in this way, both can deduce that they have published an error, and so both will end up resigning.

Now consider the case n = 3. Prof. X obtains his revenge by informing them that at least one of them has published an error that others are aware of. Each of the three can now reason as follows:

“If my colleagues didn’t know of any errors I had published, then they would know that Prof. X was referring to an error published by one of them. But in that case they could reason along exactly the same lines as outlined above, for the case n = 2, between the two of them. This would cause both of them to resign. But they’re not resigning, we’re all just staring at each other! That means that they must know of an error that I’ve published, so I have to resign.”

Once again, since each of the three can reason like this, all three will end up resigning.

At this point, you may be a bit confused. It can take some time to wrap one’s head around even simpler cases like n = 2 or n = 3, let alone n = 17. The key is to forget about trying to understand the case n = 17 directly, and instead focus on just two things. First, how does it work in the base case (n = 2)? And second, how can knowledge of a simpler case lead to knowledge of a more complicated case (such as reasoning from a solution for n = 2 to a solution for n = 3)?



As noted, this question appears as an exercise in [3]. The very next exercise, marked as one of the hardest in the book, reads as follows:

Each member of the department already knew what Prof. X asserted, so how could his saying it change anything?

This question points to an apparent paradox; namely, although we have an inductive proof that Prof. X caused all the tenured professors to resign, we also have common sense and basic reasoning telling us that Prof. X couldn’t have changed anything. The spectre of a disconnect between mathematics and logic looms ominously. I invite you to put it to rest.

Puzzle 3

The last of the three puzzles I would like to examine picks up where the previous one left off. As it turns out, Prof. X visited many universities, and as a result scores of mathematicians found themselves unemployed. A group of the less scrupulous ones aligned themselves and formed an international network of math-thieves (people who use math somehow to steal stuff—it’s a booming industry). After a particularly successful heist, the group found themselves in possession of 1 million dollars. A meeting was called to distribute the money to the members. Exactly how many members there are is not known outside of the group itself, so we’ll just have to say that there are n members and leave it at that. What is known is that each member has a unique rank in the organization, from 1st ranked (the leader) all the way down to nth ranked (the last-in-command).

As it turns out, a very precise Code is in place that governs how surplus income is to be distributed. To begin with, the 1st ranked member decides on a potential distribution of the wealth. Each member must be assigned a whole dollar amount (no cents), with 0 dollars of course being allowed. This potential distribution is then put to a secret vote, wherein each member, including the leader, gets to cast exactly one ballot: Yes or No. The members cannot communicate or strategize amongst themselves; it is every ex-mathematician for themselves.

If the vote passes or is a tie, then the money is distributed according to the proposed distribution. The catch is this: if the vote fails, then the 1st ranked member is ousted from the organization forever. Every other member is promoted by exactly one rank to fill the power vacuum, and the new 1st ranked member (who used to be 2nd ranked) repeats the process by indicating a new potential distribution and putting it to a vote. This continues until one of the distributions is passed, at which point the members take whatever money was allotted to them by that distribution.

Each member is very invested in this international network, and would rather get no share of the money at all than be ousted from the organization. Each member would also prefer not to oust too many people, if possible, so if all else is equal (i.e. if they would get the same payoff either way), then a member will vote Yes rather than No on a given distribution. Of course, if they figure that they can get even a single extra dollar by voting No on the current plan, they will do it. That’s the way the world works, at least among secret math thieves.
Now for the question:

How much cash can the leader pocket?

The answer, surprising as it may be, is all of it. The proof of this, much less surprising at this point, is by induction on n, the number of members.

As usual, we can get a feel for how the induction will work by examining simpler cases. If n = 1 then there is only one member and she is the leader! She votes to give all the money to himself (being a stickler for the rules), and the vote passes.

If n = 2, the leader can still propose a distribution that apportions all the money to herself. The second in command won’t like it, since he could get a lot more if the current leader were ousted and he took command, but there’s not much he can do about it. His vote of No versus the leader’s vote of Yes results in a tie, which means a pass.

If n = 3, the leader can still get away with giving herself all the money. As before, the 2nd ranked member won’t like it one bit, and will vote No. But the 3rd ranked member will realize that if she votes No and the current leader is ousted, then the situation will revert to the n = 2 case, with her playing the role now of 2nd ranked. In this case, she still gets 0 dollars, and so she will vote Yes to the original proposed distribution, since she gets the same amount (0 dollars) either way.

Now it should be clear how to proceed with the induction. The base case is done and then some. Next is the inductive step: suppose that if there are exactly n members, then the 1st ranked can take all the cash. We need to show that this holds true if there are n + 1 members, too. So suppose there are n + 1 members. If the leader apportions all the cash to himself, then the 2nd ranked will vote No, but everyone else will vote Yes because they get the same payoff (i.e. nothing) either way. It’s as simple as that; this completes the induction.
There are several variants on this puzzle that can make it more challenging.


* Be careful: according to some conventions, 0 is counted as the lowest natural number. Both conventions are popular so you’re likely to run into each of them depending on what you read and whom you talk to. Notational disagreements like this one are a hilarious source of confusion in mathematics, so get used to them!