Creative use(s) of mathematical induction

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.)

Solution:

Let P(n) be the statement that there is a survivor whenever 2n+1 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 P(n) is true for all positive integers n. That follows because as n runs through all positive integers 2n+1 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.

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 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.

Inductive Step:

For the inductive step, assume that P(k) is true. That is, assume that there is at least one survivor whenever 2n+1 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 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 neighbour, is also true.

So, suppose that we have 2(k+1)+1=2k+3 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 2k+3 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 (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 2k+1 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 2k+1 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 2k+1 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 2k+3 people. This completes the inductive step and proves that P(n) is true for all positive integers n.

We have completed both the steps and the inductive step. 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 throw a pie at their nearest neighbour, there is at least one survivor.

With thanks and regards to Prof. Kenneth H. Rosen,

Nalin Pithwa.

PS:

http://www.amazon.in/Discrete-Mathematics-Its-Applications-SIE/dp/0070681880/ref=sr_1_1?s=books&ie=UTF8&qid=1485906362&sr=1-1&keywords=discrete+mathematics+and+its+applications

Reference: Discrete Mathematics and its Applications, Seventh Edition, Kenneth H. Rosen.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s