Pigeonhole Congestion

Sorting the mail that comes into an office generally requires that each piece be slipped into the appropriate slot of an array of pigeonholes—one for each employee. Suppose that a small business needs ten such slots. When 11 pieces of mail arrive, one or more of the slots will have to contain at least two items.

So, if there are more pigeons than holes, some of the pigeons have to double up. Expressed mathematically, the so-called pigeonhole principle is a handy idea for proving theorems, and it often comes up in Ramsey theory to demonstrate the inevitability of certain patterns (see "Party Games").

By Pigeons-in-holes.jpg by en:User:BenFrantzDale; this image by en:User:McKay - Transferred from en.wikipedia to Commons.; Original text : Edited from Image:Pigeons-in-holes.jpg, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=4658682

Perhaps the simplest possible application of the pigeonhole principle concerns groups of men and women. If there are three people present in a gathering, at least two must be men or at least two must be women.

The same principle can be applied to any allocation of a given type of object, whether it is balls dropped into boxes, people slotted into a number of categories, or numbers meeting particular criteria.

For a more subtle, nontrivial use of the pigeonhole principle, we can look at sequences of numbers. Consider, for example, the set of numbers 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. In this case, the numbers are written in an increasing sequence. Each successive number is larger than its predecessor.

The numbers can also be written as a decreasing sequence: 9, 8, 7, 6, 5, 4, 3, 2, 1, 0.

Now suppose the order of these numbers is randomly scrambled. Mathematicians argue that the resulting sequence of numbers will always contain a shorter sequence (or subsequence) of at least four increasing or at least four decreasing numbers.

For example, in the scrambled set 1, 2, 8, 0, 3, 6, 9, 4, 5, 7, the numbers 1, 2, 8, 9 represent an increasing subsequence. The scrambled sequence 8, 4, 9, 2, 1, 6, 3, 7, 0, 5 happens to contain a decreasing consisting of 8, 4, 2, 1, 0.

How can we be sure that an arbitrary sequence of ten different numbers will have an increasing or decreasing subsequence containing at least four numbers?

The number of differently ordered sets containing ten members is 10 ✕ 9 ✕ 8 ✕ 7 ✕ 6 ✕ 5 ✕ 4 ✕ 3 ✕ 2 ✕ 1 (or 10!), which equals 3,628,800. As in the party-of-six example, the array of possible arrangements is too large for each one to be checked individually.

The most direct, elegant proof of this claim hinges on the pigeonhole principle. Consider the sequence 3, 0, 6, 2, 1, 8,7, 9, 5, 4. The idea is to put the numbers in an array of slots so that consecutive numbers in each row increase going to the right and in each column decrease going down (below). The first number goes into the slot in the upper-left corner.

The next number, 0, is smaller than 3, so it goes into the slot below 3. The following number, 6, is larger than 0, so it can't go in the slot beneath 0. It goes in the slot to the right of 3.

The number 2 is larger than 0 but smaller than 6, so it fits into the slot to the right of 0 and below 6. Similarly, 1 is smaller than 2 and 6 and larger than 0, so the only place it fits according to the allocation rule is in the slot below 2.

Each number in turn can be slotted into the array, and from the result it's easy to read off both increasing (3, 6, 8, 9) and decreasing (8, 7, 5, 4) subsequences of length four (below).

Because every number has to fit into its own slot, the diagram suggests that the very best that anyone can do is to cram nine of the numbers into a three-by-three corner, leaving the tenth number to complete either an increasing or decreasing subsequence of length four.

In general, there has to be at least one such subsequence in any scrambled set of numbers.

For strings of 101 arbitrarily ordered numbers, you find increasing or decreasing subsequences of length 11 or more, and that's not necessarily true of a sequence of just 100 different, scrambled numbers.

Generally, it's possible to prove that for n² + 1 different numbers in a sequence, you will always get increasing or decreasing subsequences of length at least n + 1.

In the example given above, n = 3, so sequences have 3² + 1, or 10,  members and subsequences have a length of at least 3 + 1, or 4.

The pigeonhole principle is one tool that mathematicians can use to identify certain patterns that are inevitably present in a random array. In a more general sense, it also applies to everyday situations.

Anyone who frequently plays solitaire card games has undoubtedly noticed that when the cards start falling into place early, the game more often than not proceeds rapidly and open slots get filled, leaving chance a smaller field on which to cofound the ultimate result. In some games, there's no need to unveil the last few hidden cards because a successful outcome is already guaranteed.

So, patterns and predictability can arise in a variety of ways even in the realm of pure chance. Ramsey theory involves establishing the guarantees for such unexpectedly regular behavior among sequences of numbers, in geometric arrays of dots and lines, and in mathematical logic.

Previously: Party Games

Next: Playing Fields of Logic