Math concept(s) : simple yet subtle

Most math concepts are intuitive, simple, yet subtle. A similar opinion is expressed by Prof. Michael Spivak in his magnum opus, Differential Geometry (preface). It also reminds me — a famous quote of the ever-quotable Albert Einstein: “everything should be as simple as possible, and not simpler.”

I have an illustrative example of this opinion(s) here:

Consider the principle of mathematical induction:

Most students use the first version of it quite mechanically. But, is it really so? You can think about the following simple intuitive argument which when formalized becomes the principle of mathematical induction:

Theorem: First Principle of Finite Induction:

Let S be a set of positive integers with the following properties:

  1. The integer 1 belongs to S.
  2. Whenever the integer k is in S, the next integer k+1 must also be in S.

Then, S is the set of all positive integers.

The proof of condition 1 is called basis step for the induction. The proof of 2 is called the induction step. The assumptions made in carrying out the induction step are known as induction hypotheses. The induction situation has been likened to an infinite row of dominoes all standing on edge and arranged in such a way that when one falls it knocks down the next in line. If either no domino is pushed over (that is, there is no basis for the induction), or if the spacing is too large (that is, the induction step fails), then the complete line will not fall. 

So, also remember that the validity of the induction step does not necessarily depend on the truth of the statement that one is endeavouring to prove.

More later,

Nalin Pithwa.

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.

Logic Problems for Pre-RMO and RMO practice

Problem 1:

Peter’s mom said: “All champions are good at math.” Peter says: “I am good at math. Therefore, I am champion!” Is his implication right or wrong?

Problem 2:

There are four cards on the table with the symbols A, B, 4, and 5 written on their visible sides. What is the minimum number of cards we must turn over to find out whether the following statement is true: “If an even number is written on one side of a card, then a vowel is written on the other side?”

Problem 3:

A sum of 15 cents was paid by two coins, and one of these coins was not a nickel. Find the values of the coins.

Problem 4:

Assume that the following statements are true:

(a) among people having TV sets there are some who are not mathematicians.

(b) non-mathematicians who swim in swimming pools every day do not have TV sets.

Can we claim that not all people having TV sets swim every day?

Problem 5:

During a trial in Wonderland the March Hare claimed that the cookies were stolen by Mad Hatter. Then, the Mad Hatter and the Dormouse gave testimonies which, for some reason, were not recorded. Later on in the trial, it was found out that the cookies were stolen by only one of these three defendants, and, moreover, only the guilty one gave true testimony. Who stole the cookies?

*****************************************************

More later,

Nalin Pithwa