#### MATH-TRICK-9

####
*Pigeon Hole Principle (P.H.P.) is also known as Dirichlet's Box Principle.*

__Introduction__: If 4 pigeons fly into 3 pigeon-holes, then some pigeon hole(s) must receive at least 2 pigeons. The statement is an obvious one.

**Theorem :- If n+1 objects are distributed into n boxes, then at least one box has at least two objects.**

__A more generalised form of this principle is as follows__: If N pigeons are to be placed into K boxes, then there is at least one box containing at least [N/K] objects, where [x] stands for greatest integer function of x.

The proof is an obvious one.

Let us illustrate these through examples.

**Ex.1. How many students,each of whom comes from the one of 50 states,must be enrolled in a college to guarantee that there are at least 100 who comes from the same state?**

Ans : Here we have to find the number of students (or,pigeons) say N, so that at least 100 come from the same state (or, pigeon holes) ,i.e., number of pigeon holes is 50, then by the generalized form of P.H.P.

[N/50] = 100 => N/50 > 99 => N > 99*50 = 4950

Therefore, N=4951 is the required number of students.

**Ex.2. A box contains three pair of socks; coloured red,blue & white. Suppose I take out the socks without looking at them. How many socks must I take out in order to be sure that they will include a matching pair?**

Ans : If I take only 2 or 3 socks, it is possible that they are all different.

For example, they may be one red one blue or one red, one blue & one white. But if I take 4 socks,there must include a matching pair. Here the 4 chosen socks are the "objects" & 3 colours are the "boxes". So by P.H.P. at least two of the 4 chosen socks must have the same colour & hence must for a matching pair. Thus the minimum number of socks to be drawn is 4.

**Ex.3. Show that in a group of 8 people, at least two will have their birthday on the same day of the week.**

Ans : Here the 8 peoples are the "objects" & 7 days are the "boxes". Hence by P.H.P. at least two of the 8 people must belong to the same day. Similarly, it is clear that in a group of 13 people, at least two will have their birthday in the same month.

**Ex.4.Two boxes contain between them 65 balls of several different sizes. Each ball is white,black,red or yellow. If you take any 5 balls of the same colour, at least two of them will always be of the same size. Prove that there are at least 3 balls which lie in the same box, have the same colour & are of the same size.**

Ans : Here we will make repeated use of P.H.P. As there are 65 balls & 2 boxes, so one of these boxes will contain at least [65/2] + 1 = 33 balls.

Consider that box, now we have four colours, so there must be at least [33/4]+1 = 9 balls of the same colour. There can be at most four different sizes available for these 9 balls of the same colour ( see 3 rd line of the question). Thus for these 9 balls (of the same colour & in the same box) there must be at lest [9/4]+1=3 balls of the same size (as at most 4 different sizes are available).

**Ex.5. Prove that no 7 integers,not exceeding 24, can have the sum of all subsets different.**

Ans : Let S be any 7-subset of {1,2, . . . ,24}. The number of non-empty subsets of S having at most 4 elements is

7C1 + 7C2 + 7C3 + 7C4 = 98.

If T is any one of these subsets,then the sum of elements in T is between 1 and 21+22+23+24=90.

Since 90 < 98, by P.H.P. it follows that the sums corresponding to the above 98 subsets can't all be different.

__Remark__: While using P.H.P. the main step is to decide what are the "objects" and what are the "boxes" . A clue is provided by the fact that the arithmetic of the numbers involved in the problem is to be exploited.