Mathematical induction can often be used in unexpected ways. We will illustrate a particularly clever use of mathematical induction here. The first problem is related to survivors in a pie-fight!
Odd Pie Fights:
An odd number of people stand in a yard at mutually distinct distances. At the same time, each person throws a pie at their nearest neighbour, hitting this person. Use mathematical induction to show that there is at least one survivor, that is, at least one person who is not hit by a pie. (This problem was introduced by Carmany. Note that this result is false when there are an even number of people.)
Let be the statement that there is a survivor whenever people stand in a yard at distinct mutual distances and each person throws a pie at their nearest neighbour. To prove this result, we will show that is true for all positive integers n. That follows because as n runs through all positive integers rnns through all odd integers greater than or equal to 1. Note that one person cannot engage in a pie-fight because there is no else to throw the pie at.
When , there are 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 pie at each other, while C throws a pie at either A or B, which ever 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.
For the inductive step, assume that is true. That is, assume that there is at least one survivor whenever people stand in a yard at distinct mutual distances and each throws a pie at their nearest neighbour. We must show that if the inductive hypothesis is true, then , the statement that there is at least one survivor whenever people stand in a yard at distinct mutual distances and each throws a pie at their nearest neighbour, is also true.
So, suppose that we have people in a yard with distinct distance between pairs of people. Let A and B be the closest pair of people in this group of people. When each person throws a pie at the nearest person, A and B throw pies at each other. If someone else throws a pie either at A or B, then altogether at lesat three pies are thrown at A and B, and at most pies are thrown at the remaining people. This guarantees that at least one person is a survivor, for if each of these people was hit by at least one pie, a total of pies would have to be thrown at them. (The reasoning used in this last step is an example of pigeonhole principle).
To complete the inductive step, suppose no else throws a pie at either A or B. Besides A and B, there are people. Because the distances between pairs of these people are all different, we can use the inductive hypothesis to conclude there is at least one survivor S when these people each throw pies at their nearest neighbour. 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 people. This completes the inductive step and proves that is true for all positive integers n.
We have completed both the steps and the inductive step. So, by mathematical induction it follows that 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 throw a pie at their nearest neighbour, there is at least one survivor.
With thanks and regards to Prof. Kenneth H. Rosen,
Reference: Discrete Mathematics and its Applications, Seventh Edition, Kenneth H. Rosen.