combinatorics 1 - basic methods

1.1 - the pigeon-hole principle

The pigeon-hole principle is where my university modules on combinatorics started, which makes sense. This is a nice result which gets right at the heart of what (I think) makes mathematics so interesting, the ability to travel from a state of not knowing to a state of knowing. Knowing just how much stuff we have, and how many places we have to put it, we can say with certainty if it is possible to organise it so that everything has its own place to go.

My professor for my combinatorics class at university was a chap called Peter Cameron. His passion for his work and care for his students was clear to see, even from the back of a lecture hall. He would at times take a break from his teaching to give us some kind of anecdote on the content we were covering. In one of these he explained that as we are in Scotland, it was not right to refer to the "pigeon-hole principle", but rather that we should embrace the culture and dub this result the more appropriate "doocot principle". As such, I will carry on the the tradition.

Theorem 1.1 - The doocot principle

Let n and k be positive integers such that n > k. Suppose we have to place n identical balls into k identical boxes. Then there will be at least one box in which we place at least two balls.

Proof

Let $ n, k \in \mathbb{Z} $ such that $ n > k $, and suppose we have placed n identical balls into k identical boxes with no two balls in the same box. Then every box has either 1 or 0 balls inside. For $ i \in \{ 1, 2, ..., k \} $, let $ a_i $ be the number of balls in box i. Then since each of our n balls are in one of our k boxes, we must have $ n = \sum_{i = 1}^{k} a_i \le \sum_{i = 1}^{k} 1 = k < n $. This is a contradiction, so our claim is proved. □

Results like the doocot principle are not revolutionary, world-changing results in themselves. They are, instead, the sort of things which will be useful again and again. There are a couple of examples shared by Bóna, which are shared below, but these are not close to extensive. An obvious application I can think of in my day-to-day would be selecting the correct subnet mask.

Example 1.2

There is an element in the sequence 7, 77, 777, 7777, ... which is divisible by 2003.

Proof

Consider the first 2003 elements of our sequence. Assume that none of these is divisible by 2003. Then by euclidean division, each of our elements have a remainder between 1 and 2002 when divided by 2003. As there are 2003 remainders to consider, and only 2002 possible values for these, the doocot principle tells us that two of our remainders must share a value. Call the indices of the elements of our sequence which have these equal remainders i and j, with $ i < j $, and call the elements themselves $ a_i $ and $ a_j $.

Now, with a wee bit of modular arithmetic, we see that for some $ p_i, p_j, r \in \mathbb{N} $, we have $ a_j - a_i = (2003 \cdot p_j + r) - (2003 \cdot p_i + r) = 2003 ( p_j - p_i ) $, so the difference of $ a_j $ and $ a_i $ is divisible by 2003. So,

$$\begin{eqnarray} a_j - a_i &= 77777777777 - 77777 \nonumber \\ &= 77777700000 \nonumber \\ &= [\text{j - i 7s}][\text{i 0s}] \nonumber \\ &= a_{j - i} \cdot 10^i \nonumber \end{eqnarray}$$

Now we can notice that 2003 is prime, and so specifically is coprime with $ 10^i $, so since the difference of $ a_j $ and $ a_i $ is divisible by 2003 we conclude that a_{j - i} is divisible by 2003. □