MATHS FOR ALL

--------------------------------

WANT FREE COACHING IN MATHS IN BANGALORE ?
CALL 9480193388 OR EMAIL freemaths10212@gmail.com

For details see post on 26-Feb-2015 at 6:00 am.

---------------------------

Let us continue our journey. We have seen four methods of problem solving and some techniques that could be used in actual solution of a problem after choosing a particular method .Now we will see further methods of problem solving.

Method No.5 :

PIGEON HOLE PRINCIPLE : - We shall take this up ahead of other familiar methods as this is very simple ,but yet very powerful method and is also not taught as such in a methodical manner in the normal course work. It is very useful in solving several existence problems.

Stated in plain terms , it says that if there are n ( say 5 ) pigeons and they are put in m ( say 4 ) cages , “n” the number of birds being greater than “m” the number of cages , then at least one cage will have more than one pigeon.

It looks so simple to be called by a big name like a PIGEON HOLE PRINCIPLE !! . But look at the following examples and you will realize its wide application. As stated earlier , our imagination can be the only limitation in applying to any relevant case in mathematics or in any general life situation.

Let us start with a simple example. Take the case of any school or college with say about 400 students. If we are asked to prove that there are at least two students with the same birth day , we would have been wondering how to go about it before we came across this simple principle. Now we can easily say that there can be after all only 365 or 366 at best , different birth days or let us call them cages. But there are 400 students or pigeons to which they could be assigned. Hence ,there will be at least two students with the same birth day.

Now let us take a similar but a bizarre problem. This is to prove that in our twin cities there are at least two persons with the same number of hairs on their head!! We know the proof by now , but for this problem we need to make a few estimates .

For a start to our estimate we can assume on the safer side that head is of the shape of a hemi sphere whose diameter could be say maximum 30 cm.

So the total surface area of head is 2 x 3.14 x 15 x 15 = say 1400 square cm.

Next , let us consider the number of hair strands in one square centimeter area. We can safely assume that it will not be more than 10 x 10 or let us take maximum 15 x 15 = 225 hairs per sq. cm. So the maximum number of hairs on any one head can be 1400 x 225 = 315000. This is of course a gross over estimate ,particularly on the surface area of head, and it is normally estimated that the number of hairs to be about 100000. Even if we take our higher estimate ,it is easy to see from the Pigeon hole principle , that there will be at least two people with the same number of hairs as the population of twin cities is far far more than this number of hairs estimate. In fact even now when drawing this conclusion ,we are making another over estimate viz. we are taking that there will be persons with 0 ( A PERFECT BALD HEAD ) ,1,2,3,…..,315000 hairs and so there is no doubt what so ever that there will be more than two persons with the same number of hairs .

Now on to one example from more serious mathematical problems which could be solved using this . Under number theory , now congruence modulo is being taught at intermediate level . We say

7 = 3 ( mod 4 ) read as 7 is congruent to 3 modulo 4.

Since 4 divides 7 – 3 or 7 – 3 is an integral multiple of 4. In general

a = b ( mod m) if a - b is divisible by m or a – b is an integral multiple of m.

Let us take an example from this number theory connecting Polynomials.

F[X] IS A PLOLYNOMIAL WITH INTEGER COEFFICIENTS.

IF F[A]=F[B]=F[C]=2 , WHERE A,B,C ARE ALL DISTINCT NUMBERS SHOW THAT 

F[X] IS NOT EQUAL TO 3 FOR ANY INTEGER VALUE OF X.

PROOF

LET F[X]= D0+D1X+D2X^2+.......+DNX^N

CONSIDER F[P]-F[Q]= D1[P-Q]+D2[P^2-Q^2]+......+DN[P^N-Q^N]..

SINCE EVERY TERM ON RHS IS DIVISIBLE BY [P-Q] , WE CONCLUDE THAT [F(P)-F(Q)] IS DIVISIBLE BY [P-Q]..

NOW LET US USE REDUCTIO-AD-ABSURDUM ....

ASSUME THAT THERE IS AN INTEGER D SUCH THAT FOR X=D , WE HAVE ..F[D]=3

HENCE FROM THE GIVEN DATA ...

F(D)-F(A) =3-2 = 1 IS DIVISIBLE BY [D-A]

F(D)-F(B) =3-2  = 1 IS DIVISIBLE BY [D-B]

F(D)-F(C) =3-2  = 1 IS DIVISIBLE BY [D-C]

BUT 1 HAS ONLY 2 DISTINCT FACTORS NAMELY + 1 & -1 ..SO FROM PIGEON HOLE PRINCIPLE ,IF WE PUT THESE 3 PIGEONS IN 2 DIFFERENT CAGES , AT LEAST ONE CAGE WILL HAVE 2 PIGEONS ..THAT IS ...TWO FACTORS OUT OF D-A , D-B , D-C ARE EQUAL ...

BUT A,B,C ARE ALL DISTINCT AS GIVEN ..SO THERE CAN NOT BE A NUMBER D SATISFYING THE REQUIREMENT ...SO A COMBINATION OF REDUCTIO-AD-ABSURDUM & PIGEON HOLE PRINCIPLES PROVE THE PROPOSITION .

The above example gives us an idea of the reach and power of this simple but very effective method to solve problems. Before we conclude our study on this , let me emphasize here that there are several examples in real life situations where this principle stands out showing the way ,but sadly neglected. The author has personal experience of several cases in major industries where at the highest levels , decisions were not taken immediately , but delayed for my personal intervention , even though the solution is obvious if the PIGEON HOLE PRINCIPLE is used. So it is reiterated here once again that this is THE PRINCIPLE to be looked for first whenever in need in life or in industry or in science or in maths.

Method No.6 :

Mathematical Induction : This is a well taught and useful method at intermediate or even school level to prove certain formulae for sum of a series etc. The method is as follows.

We are given a series with n terms and given a formula to prove that its sum is given by that formula.

The method of proof is , we test the formula for applicability in the case of n=1 . After verifying that it is applicable , we assume that the formula is correct for n = k say , that is for any particular value of “n”. Next we go on to prove that , if it is true for n = k, then , it is also true for n = k + 1 .Now we reason out that since we proved its validity at n = 1 at the beginning ,then it should be true for n = 1 + 1 = 2 as per our later verification that if the formula applies for n = k then , it is also true for n = k + 1. Hence it must be true for n = 2 , 3 , 4 ..etc…that is for all integral values of n .

It is very important to follow both the steps mentioned above in that order , The first step ensures that the given formula is correct by checking at the lowest level of n = 1 .Then we should check its applicability as per the second step to prove its validity at any integral value of n.

This method has certain limitations by its very nature .

1. It can be applied only for an integral value of “n” the number of terms.
2. We should know the formula or answer ahead , to prove that it is applicable., that is we are not deriving a formula here but proving a given formula.

There are several standard examples for this at the school and college levels and hence we shall confine ourselves with a few important points to remember in adopting this method.

We should adopt a good nomenclature for the problem ,defining clearly all the terms. For example when dealing with problems on summation of series, put

sum to ‘n’ terms as s(n) and ‘n’ th. term as t(n) and note that

s(n) = t(1) +t(2) +……..t(n-1) +t(n) and

s(n+1)=s(n) + t(n+1).

After initial verification for n=1,use the given formula to be proved for s(n) in

s(n+1)=s(n)+t(n+1) as we have assumed that the given formula is true for ‘n’. Substitute (n+1) for n in L.H.S. to get at what we have to obtain from R.H.S. Now take L.H.S. and substituting for t(n+1) try to maneuver the right hand side to make it equal to left hand side .

In dealing with problems to prove divisibility , proceed similarly and try to convert the R.H.S. in to multiples of the required divisor by splitting / combining them , using the assumed fact for a value of ‘n’ and other general known factors.

Method No.7 :

RECURRENCE: This method is also used only for integral values of “n” as in the case of mathematical induction ,but , we can derive the formula in this case ,unlike in induction where we need a formula to verify its applicability. This method once again ,though not formally taught as such is a very useful one with many applications as we shall see shortly. In this method we first assume that the answer is some function of “n” say f(n) as is obvious. Then we try to find this function by relating f(n) with f(n+1). Let us illustrate the method with an example of an interesting game .

There are 3 stands with a horizontal circular base and a vertical rod at the center to house few disks. The disks have a central aperture to insert them through the central rod on the stands and keep them in position on the stand. One stand is having some disks on it ( any number ) all of different sizes ,the biggest being at the bottom , the next smaller on top of it ..etc ..till the last disk being the smallest placed on top. The other 2 stands are empty to start with . The task is to transfer these disks to another stand ,such that , they are placed on that stand exactly as they were on the original stand ,that is biggest ring at bottom followed by next smaller …etc… till the smallest is on top. The third stand can be used as a transfer stand while transferring the disks . The rules to be followed are

1. only one disk can be taken at a time
2. a bigger disk should never be placed on top of a smaller disk.

One can play and do the task, but the important point is how many chances it took, counting each disk transfer as one chance. Or what are the minimum number of chances needed to transfer the disks if there are say “n” disks to start with. So we have to derive a formula to find the minimum number of chances to perform the task .Let us use the method of recurrence to do this .

Let f(n) be the minimum number of chances needed to transfer the “n” disks from the original stand to the new stand. Let us try to find f(n+1) , that is , minimum number of chances needed to transfer the “n+1” disks from the original stand to the new stand , using the above function.

For convenience let us number the discs … biggest is no.1,followed by 2,3,…etc the next smaller discs ,the smallest and last disc being no.” n “ disk. To start with, we assumed that f(n) is the minimum number of chances needed to transfer the “n” disks. Now for the next step of connecting this function with f(n+1), let us place the smallest “n+1”th.disk on top of the n th. disk.

Let us try to transfer these as follows. To start let us keep biggest disc no.1 undisturbed on the original stand and transfer the rest n disks on to an intermediate stand. This should take us f(n) chances as there are only n disks to be transferred. Having done that ,let us now take out the biggest disk no.1 at the bottom and place it on the final transfer stand. This needs one chance. Now let us transfer the n disks on the intermediate stand to the final stand ,using the original stand as the new intermediate transfer stand. This should take us another f(n) chances. Hence

f(n+1) = f(n) + 1 + f(n) = 2 f(n) + 1

For n = 1 , the number of chances needed are obviously equal to 1. Let us use this relation starting from n = 2 to n

F[2]=F[1]+1+F[1]=2*F[1] + 1 

F[3]= 2^2*F[1]+[2 + 1]

F[4]=2^3*F[1]+[2^2+2+1]

..................................

F[N]=[2^(N-1)][F(1)]+[{2^(N-2)}+.....+2+1] = [2^(N-1)][F(1)]+2^(N-1)+1

This shows the utility of this method even in a totally new situation. As mentioned in the beginning , though this method is not taught as such ,the principle is widely used as an important technique in several derivations in high school and college levels as we shall see subsequently in the following para . We had been discussing different methods to formulate a route plan to solve a problem and different techniques that could be used under those methods to travel the actual path under a route plan . Recurrence method can also be used as a technique under different methods to solve problems .

Useful Techniques :-

Our Teacher used to preface use of these techniques by saying “ See No Magic No Mantram No Maaya” ,just use these simple techniques and note the transformations that take place …

Multiply and Divide :- Consider the example below for simplification for further work or to get a simplified answer.

SIMPLIFY OR DIFFERENTIATE ..ETC..

F[X]=[1+X][1+X^2][1+X^4]....[1+X^[2N)]....MULTIPLY & DIVIDE WITH [1-X] TO GET 

F[X] = [1-X^(4N)] / [ 1-X] ...WHICH IS EASY TO DEAL WITH ...

Add and Subtract :- Consider the following example from sum of series of natural numbers.

Prove that the sum of cubes of any ‘n’ consecutive natural numbers is divisible by their sum.

Note the stipulation ,any ‘n’ consecutive natural numbers, not necessarily starting from 1.

Had it been starting from 1 ,it is quite simple ,as

1^3+2^3+...+N^3= [0.5*N(N+1)]^2 IS DIVISIBLE BY 1+2+...+N=[0.5N(N+1)]..

BUT WE HAVE 

A^3+(A+1)^3+.....+[A+(N-1)]^3 ..SO ADD & SUB TRACT ...1^3+2^3+....+(A-1)^3

 WE GET ..

A^3+(A+1)^3+.....+[A+(N-1)]^3 = [1^3+2^3+....+(A+N-1)^3] - [ 1^3+2^3+....+(A-1)^3]

= [0.5*(A+N-1)(A+N)]^2 - [0.5*(A-1)(A)]^2 = X^2 - Y^2 ...SAY ...................

A+(A+1)+......+(A+N-1) = [1+2+......+(A+N-1)] -[1+2+....(A-1)] 

= [0.5(A+N-1)(A+N)]-[0.5(A-1)(A)] = X- Y ....................

 OBVIOUSLY ...X^2-Y^2 IS DIVISIBLE BY X-Y ...PROVED

TAIL PIECE

There is a saying that politicians act only under 2 circumstances , namely, once when their interest is threatened or secondly when ‘there is no alternative ‘ called in short as T I N A effect. This shows that they are experts in understanding and using Pigeon hole principle as this principle can be taken as nothing but another way of stating the T I N A effect. So do not under estimate them as they are the better exponents and the frequent users of Pigeon hole principle which is one of the best methods to tackle problems of a wide variety as we have learnt in this lesson.