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.
The first puzzle I want to consider comes from . 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
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
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
, 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
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.
The inductive proof above not only answered the question of whether or
not the game would always end, but it also gave an upper
bound on how long any particular game would take. Why was this included
in the proof? (Hint:
It was not just to show off.)
We now have an upper bound of2n on the number of turns a game starting
with the numbers n and n + 1
might last. Is this also a lower bound? If not, can you find a more
precise result regarding how long such games will last?
These exercises are challenging.
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 , 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
“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
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)?
Convince yourself that if the base case n = 1 of an
inductive argument is replaced with the base case n = k, for some
natural number k, then the proof still shows that the result in
question holds true of the natural numbers greater than or equal to k.
Provide an inductive proof (starting at n = 2) that answers the original
question: all 17 professors will end up resigning.
As noted, this question appears as an exercise in . 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
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.
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
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
Now for the question:
How much cash can the leader
The answer, surprising as it may be, is all of it
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
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!
How much cash can the leader pocket if tie votes result in oustings?
How much cash can the leader pocket if members vote No rather than Yes
if they get the same payoff either way?