Certainty Problems and The Pigeonhole Principle

The pigeonhole principle is one of those simple yet beautiful, widely used theorems with lots of applications. Any high school going kid may understand what the theorem wants to say, yet its beauty baffles and brings excitement in even the most experienced mathematician. Someone has said that mathematics unveils the patterns of nature and the pigeonhole principle is a manifestation of this fact.

Sometimes it is also referred to as the Dirichlet’s principle (Lejeune Dirichlet is supposed to be the first person to have stated the principle ) or the Box principle or the Dirichlet’s Box principle.

Statement:-

1. Simple form :
   Given $$n$$ boxes and $$m>n$$ objects, at least one box must contain more than one object.
2. Generalized form :
   If $$n$$ objects are placed into $$k$$ boxes, then there exists at least one box containing at least $$\lceil \frac{n}{k}\rceil$$ objects, where is the ceiling function (The ceiling function returns the greatest integer greater than or equal to the parameter).

Illustration through examples: –

1. Atleast two people in a group of $$13$$ people have their birthdays in the same month. Similarly in a group of $$367$$ people have their birthdays on the same day of the year.
2. If $$qs+1$$ balls have to put into $$q$$ boxes then atleast one box should contain $$s+1$$ or more balls.
3. The decimal expansion of $$\frac{a}{b}$$ where $$a$$ and $$b$$ with coprime $$a,b$$ has at most $$b-1$$ period, i.e. the numbers recur after at most $$b-1$$ places.
4. Among any group of six people on Facebook we may find a group of three such that all of them are friends or all of them are strangers.

Certain famous problems:-

1. (Erdos-Szekeres.) Prove that every sequence of $$n^2$$ distinct numbers contains a subsequence of length $$n$$ which is monotone (i.e. either always increasing or always decreasing)
   OR

   Let $$p$$ and $$q$$ be positive integers. Show that within any sequence of $$pq+1$$ distinct real numbers, there exists either a increasing subsequence of $$p+1$$ elements, or a decreasing subsequence of $$q + 1$$ elements.

2. (Paul Erdos.) Let A be a set of $$n+1$$ integers from $${1,2,3,\ldots,2n}$$. Prove that some element of $$A$$ divides another.
3. Let $$a_1,a_2,\ldots,a_n$$ be positive integers. Prove that we can choose some of these numbers to obtain a sum divisible by $$n$$.
4. (Chinese Remainder Theorem) Let $$m$$ and $$n$$ be relatively prime positive integers. Then the system:
   $$x = a \pmod{m}$$
   $$x = b \pmod{n}$$

   has a solution.

5. Given two disks, one smaller than the other. Each disk is divided into $$200$$ congruent sectors. In the larger disk $$100$$ sectors are chosen arbitrarily and painted red; the other $$100$$ sectors are painted blue. In the smaller disk each sector is painted either red or blue with no stipulation on the number of red and blue sectors. The smaller disk is placed on the larger disk so that the centers and sectors coincide. Show that it is possible to align the two disks so that the number of sectors of the smaller disk whose color matches the corresponding sector of the larger disk is at least $$100$$.
6. Show that given any set $$A$$ of $$13$$ distinct real numbers, there exist $$x, y \in A$$ such that

   $$0<\dfrac{x-y}{1+xy}<2-\sqrt{3}$$

Generally the problems which appear in Olympiads in which we have to ascertain existence or speak certainly about something use the pigeonhole principle. The following are the problems which have appeared in RMO and INMO papers of previous years concerning pigeonhole principle.

RMO problems :-

1. 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 (radius). Prove that there are at least $$3$$ balls which lie in the same box have the same colour and have the same size (radius).
   (1990)
2. Let A be a set of 16 positive integers with the property that the product of any two distinct numbers of A will not exceed 1994. Show that there are two numbers a and b in A which are not relatively prime.
   (1994)
3. If A is a fifty-element subset of the set $${1, 2, 3,\ldots, 100}$$ such that no two numbers from A add up to 100. Show that A contains a square.
   (1996)
4. Find the minimum possible least common multiple of twenty natural numbers whose sum is 801.
   (1998)
5. Suppose the integers $$1,2,3,\ldots,10$$ are split into two disjoint collections $$a_1,a_2,a_3,a_4,a_5$$ and $$b_1,b_2,b_3,b_4,b_5$$ such that $$a_1<a_2<a_3<a_4<a_5$$ and $$b_1>b_2>b_3>b_4>b_5$$
   1. Show that the larger number in any pair $${a_j,b_j}$$, $$1\leq j\leq 5$$ is atleast $$6$$.
   2. Show that for every such partition $$\sum_{i=1}^5 | a_i-b_i| = 25$$.
      (2002)
6. A square is dissected in to 9 rectangles by lines parallel to its sides such that all these rectangles have integer sides. Prove that there are always two congruent rectangles.
   (2006)
7. A computer program generated $$175$$ positive integers at random, none of which had a prime divisor greater than $$10$$. Prove that there are three numbers among them whose product is the cube of an integer.
   (2012)

INMO problems :-

1. Suppose five of the nine vertices of a regular nine-sided polygon are arbitrarily chosen. Show that one can select four among these five such that they are the vertices of a trapezium.
   (2011)
2. All the points in the plane are colored using three colors.Prove that there exists a triangle with vertices having the same color such that either it is isosceles or its angles are in geometric progression.
   (2009)
3. Given any nine integers show that it is possible to choose, from among them, four integers $$a,b,c,d$$ such that $$a + b-c-d$$ is divisible by $$20$$. Further show that such a selection is not possible if we start with eight integers instead of nine.
   (2001)
4. Some $$46$$ squares are randomly chosen from a $$9 \times 9$$ chess board and colored in red. Show that there exists a $$2\times 2$$ block of $$4$$ squares of which at least three are colored in red.
   (2006)
5. In any set of $$181$$ square integers, prove that one can always find a subset of $$19$$ numbers, sum of whose elements is divisible by $$19$$.
   (1994)

Additional Information:-

1. Many refer to the Pigeonhole Principle as PHP.
2. A very beautiful application of PHP is the Thue’s lemma which is useful in proving the Fermat’s two square theorem.
3. Its use arises in computer science, analysis, probability, etc.
4. The Ramsey’s theorem, which is an application of PHP gives rise to a very deep theory in mathematics called the Ramsey theory.
5. Some other methods of proof which may be used in solving certainty problems are reductio ad absurdum, pairity checking, construction of an example by brutal force, creating bijections, extremal principle, transformation of the theorem into graphs or some easy geometric interpretation and using colouring proofs on them, etc.

References:-

1. www.mathlinks.ro
2. http://olympiads.hbcse.tifr.res.in/subjects/mathematics/previous-question-papers-and-solutions
3. Wikipedia
4. Arthur Engel, Problem Solving Strategies, Springer
5. M.R. Modak, S.A. Katre, V.V. Acharya, V.M. Sholapurkar, An Excursion in Mathematics, Bhaskaracharya Pratishthana
6. David M. Burton, Elementary Number Theory, McGraw Hill