Page 347 - Discrete Mathematics and Its Applications

326 5 / Induction and Recursion

to 3. Note that one person cannot engage in a pie fight because there is no one else to throw the
pie at.
BASIS STEP: When n = 1, there are 2n + 1 = 3 people in the pie fight. Of the three people,
suppose that the closest pair are A and B, and C is the third person. Because distances between
pairs of people are different, the distance between A and C and the distance between B and C are
both different from, and greater than, the distance between A and B. It follows that A and B throw
pies at each other, while C throws a pie at either A or B, whichever is closer. Hence, C is not hit by
a pie. This shows that at least one of the three people is not hit by a pie, completing the basis step.

INDUCTIVE STEP: For the inductive step, assume that P(k) is true for an arbitrary odd
integer k with k ≥ 3. That is, assume that there is at least one survivor whenever 2k + 1 people
stand in a yard at distinct mutual distances and each throws a pie at their nearest neighbor. We
must show that if the inductive hypothesis P(k) is true, then P(k + 1), the statement that there is
at least one survivor whenever 2(k + 1) + 1 = 2k + 3 people stand in a yard at distinct mutual
distances and each throws a pie at their nearest neighbor, is also true.
So suppose that we have 2(k + 1) + 1 = 2k + 3 people in a yard with distinct distances
between pairs of people. Let A and B be the closest pair of people in this group of 2k + 3 people.
When each person throws a pie at the nearest person, A and B throw pies at each other. We have
two cases to consider, (i) when someone else throws a pie at either A or B and (ii) when no one
else throws a pie at either A or B.
Case (i): Because A and B throw pies at each other and someone else throws a pie at either A
and B, at least three pies are thrown at A and B, and at most (2k + 3) − 3 = 2k pies are thrown
at the remaining 2k + 1 people. This guarantees that at least one person is a survivor, for if each
of these 2k + 1 people was hit by at least one pie, a total of at least 2k + 1 pies would have to be
thrown at them. (The reasoning used in this last step is an example of the pigeonhole principle
discussed further in Section 6.2.)
Case (ii): No one else throws a pie at either A and B. Besides A and B, there are 2k + 1 people.
Because the distances between pairs of these people are all different, we can use the inductive
hypothesis to conclude that there is at least one survivor S when these 2k + 1 people each
throws a pie at their nearest neighbor. Furthermore, S is also not hit by either the pie thrown
by A or the pie thrown by B because A and B throw their pies at each other, so S is a survivor
because S is not hit by any of the pies thrown by these 2k + 3 people.
We have completed both the basis step and the inductive step, using a proof by cases. So by
mathematical induction it follows that P (n) is true for all positive integers n. We conclude that
whenever an odd number of people located in a yard at distinct mutual distances each throws a
pie at their nearest neighbor, there is at least one survivor. ▲

In Section 1.8 we discussed the tiling of checkerboards by polyominoes. Example 14 illus-
trates how mathematical induction can be used to prove a result about covering checkerboards
with right triominoes, pieces shaped like the letter “L.”

n
n
EXAMPLE 14 Let n be a positive integer. Show that every 2 × 2 checkerboard with one square removed can
be tiled using right triominoes, where these pieces cover three squares at a time, as shown in
Figure 4.
n
n
Solution: Let P(n) be the proposition that every 2 × 2 checkerboard with one square removed
can be tiled using right triominoes. We can use mathematical induction to prove that P(n) is
true for all positive integers n.
FIGURE 4 A BASIS STEP: P(1) is true, because each of the four 2 × 2 checkerboards with one square
Right Triomino. removed can be tiled using one right triomino, as shown in Figure 5.