Stuffing Things in Boxes (Tuklas Vol. 16, No. 1 - October 18, 2014)

STUFFING THINGS IN BOXES

Suppose you and four other friends are dining at a restaurant. Looking at the menu, you see that there are four different rice meals that can be ordered. Is it possible for each of you to order a unique rice meal?

A quick guess could be no. How would we solve this? If we pair off each rice meal to a person, we see that by the time we reach the fifth person there is no longer a unique rice meal that that person can order. 1

This example illustrates a very powerful technique with interesting applications. In fact, the underlying math involved is so simple that hardly anyone can see it. This technique is called the pigeonhole principle. First formally introduced by the German mathematician Peter Gustave Lejeune Dirichlet under the name Schubfachprinzip 2, we can state it roughly as follows:

If \(n+1\) objects are put into \(n\) boxes, then at least one box contains two or more objects.

In our first example, the objects refer to the diners and the boxes refer to the kinds of meals. Since there are five diners and only four kinds of meals, one diner must have the same kind of meal as one of the other four. Albeit simple, this technique can be used to prove some interesting and surprising mathematical results.

Let us first consider an easy variation of what is called the birthday problem.

Given a set of \(n\) randomly chosen people, what is the probability that some pair of them will have the same birthday?

The problem arises when one is called to find the value of \(n\) for different situations. While this is an interesting problem for another time, the pigeonhole principle actually guarantees that a pair will always exist for \(n \geq 367\), simply because there are \(366\) unique days in a year (including February 29). Here, the days are the boxes and the people are the objects.

Suppose we now make those \(n\) people shake hands. The pigeonhole principle can be used to show that there is always a pair of people who will shake hands with the same number of people. To illustrate this, we determine what the boxes or holes should be. Note that each person can shake hands with \(0\) up to \(n-1\) people. If we let our holes be equivalent to the number of people a person has shaken hands with, then one of the "\(0\)" or "\(n-1\)" holes must necessarily be empty. Why is this the case? Note that if the "\(0\)" hole is nonempty, then there is a person who has not shaken hands with anyone. Hence, the "\(n-1\)" hole must be empty. 3 This implies that we have at most \(n-1\) holes to fill in with \(n\) people, guaranteeing at least one pair that would have shaken hands with the same number of people.

The previous example highlights one of the mildly frustrating consequences of using the pigeonhole principle. Its highly intuitive concept makes it harder to apply than other more methodical techniques. The difficulty lies in trying to determine what the holes should represent; once that is overcome, everything else becomes easier.

Consider, for instance, this charming problem.

Show that given any set \(A\) of \(13\) distinct real numbers, there exist \(x, y \in A\) such that \[ 0 < \frac{x-y}{1+xy} \leq 2 - \sqrt{3}. \]

An elegant solution to this problem is as follows. We recognize the middle expression as equivalent to the difference of tangents identity. Thus, we set \(x = \tan(u)\) and \(y = \tan(v)\) for some angles \(u,v\) considered modulo \(\pi\) (by the periodicity of the tangent function). We have \[ \frac{x-y}{1+xy} = \tan(u-v), \]implying that we are interested in closing the gap between the angles \(u\) and \(v\) (as implied by \(u-v\)). Specifically, we set the gap to be smaller than \(\frac{\pi}{12}\). This observation is supported by noting that the \(13\) distinct real numbers imply that we divide the angles in \([0,\pi]\) into 12 equal sectors. Moreover, we have \(\tan\left(\frac{\pi}{12}\right) = 2 - \sqrt{3}\). By the pigeonhole principle, we are done.

ABOUT THE AUTHOR:
Jesus Lemuel L. Martin, Jr. is an Instructor at the Ateneo de Manila University. He obtained his B.S. in Applied Mathematics major in Computational Science at the Ateneo de Manila University in 2010 and his M.S. in Mathematics at the same university in 2013.

ENDNOTES:

[1] In short, person number five will have to copy someone else's order, or get an appetizer instead if uniqueness is such an issue.

[2] Roughly translated as "drawer principle" or "shelf principle", it is sometimes called Dirichlet's box principle or Dirichlet's box principle.
[3] Equivalently, if the "n-1" hole is nonempty, then there is a person who has shaken everyone else's hand, making the "0" hole empty.

ENDNOTES:

- Bogomolny, Alexander. Pigeonhole Principle. Retrieved from http://www.cut-the-knot.org/do_you_know/pigeon.shtml.

- Chen, Beifang and Wang, J. "The Pigeonhole Principle." (2005) Retrieved from https://www.math.ust.hk/~mabfchen/Math391I/Pigeonhole.pdf.

- Chen, Chuan-Chong and Koh, K.-M. Principles and Techniques in Combinatorics (1992).

OLYMPIAD CORNER

from the Belarus National Contest, 2000

Problem: Let \(M\) be the intersection point of the diagonals \(AC\) and \(BD\) of a convex quadrilateral \(ABCD\). The bisector of angle \(ACD\) hits ray \(BA\) at \(K\). If \(MA\cdot MC+MA\cdot CD=MB\cdot MD\), prove that \(\angle BKC=\angle CDB\).

Solution: 

Let \(N\) be the intersection of lines \(K\) and \(BD\). By the Angle Bisector Theorem applied to triangle \(MCD\),\(\frac{CD}{DN}=\dfrac{MC}{MN}\), or \(CD=\dfrac{MC\cdot DN}{MN}\). We then have \[ MB\cdot MD=MA\cdot MC+MA\cdot \dfrac{MC\cdot ND}{MN}=(MA\cdot MC)\cdot\frac{MD}{MN}, \]or \(MA\cdot MC=MB\cdot MN\). 

Because \(M\) lies inside quadrilateral \(ABCN\), the Power of a Point Theorem implies that \(A\), \(B\), \(C\), and \(N\) are concyclic. Hence, \(\angle KBD=\angle ABN=\angle ACN=\angle NCD=\angle KCD\), implying that \(K\), \(B\), \(C\), and \(D\) are concyclic. Thus, \(\angle BKC=\angle CDB\), as desired.

PROBLEMS

1. There are given \(2014\) sets, each containing \(40\) elements. Every two sets have exactly one element in common. Prove that all \(2014\) sets have exactly one element in common.
   
2. Let \(a, b, c\) be positive real numbers such that \(abc=1\). Prove the inequality \[ \frac{a}{a+b^{4}+c^{4}}+\frac{b}{b+c^{4}+a^{4}}+\frac{c}{c+a^{4}+b^{4}}\leq1. \]
3. Circles \(C_{1}\) and \(C_{2}\) with centers \(O_{1}\) and \(O_{2}\) respectively intersect each other at \(A\) and \(B\). Ray \(O_{1}B\) intersects \(C_{2}\) at \(F\) and ray \(O_{2}B\) intersects \(C_{1}\) at \(E\). The line parallel to \(EF\) and passing through \(B\) intersects \(C_{1}\) and \(C_{2}\) at \(M\) and \(N\), respectively. Prove that \(MN=AE+AF\).

We welcome readers to submit solutions to the problems posed below for publication consideration. Solutions may ONLY be submitted online via vantonio@ateneo.edu. Solutions must be preceded by the solver's name, school affiliation and year level. The deadline for submission is 4:00 PM October 25, 2014.