The Boxer and the Pigeons
Suppose a boxer has 11 weeks to prepare for a fight, and he intends
to have at least one training session each day. However, he decides
not to schedule more than 12 training sessions in any 7-day period,
to keep from getting burned out. Prove that there exists a sequence
of successive days during which the boxer has exactly 21 training
This problem can be solved by a double application of the pigeonhole
principle. First, since the boxer has no more than 12 sessions per
week, he can't have more than 132 sessions in 11 weeks. Now let x_n
denote the total number of sessions that have been held after n days.
Since the boxer trains at least once per day, we have
1 <= x_1 < x_2 < x_3 < ... < x_77 <= 132
Also, we can add 21 to each of these numbers to give the sequence
(x_1 + 21) < (x_2 + 21) < ... < (x_77 + 21) <= 153
There are 77 numbers x_n and 77 more numbers x_n + 21 for a total of
154 numbers, all in the range from 1 to 153. Thus, at least two of
these 154 numbers must be equal. But the x_n are all distinct, as
are the (x_n + 21), so any "overlap" must be between a number of the
form x_n and one of the form (x_m + 21), which implies
x_n = x_m + 21
This proves that there are indices m,n such that exactly 21 training
sessions were held during the sequence of consecutive days from day
n+1 to day m.
Obviously the same argument works if we replace 21 with any number
less than 21, so it follows that for each integer N from 1 to 21
that there exists a sequence of successive days during which the
boxer has exactly N training sessions.
It's interesting that nature makes frequent use of the pigeon hole
principle, because no two fermions (such as electrons) can occupy
the same quantum state. This is called the Pauli Exclusion Principle,
and is responsible for the variety of atoms that are found in nature.
Each valence shell, with a given spin, can contain only one electron,
so there can be only two electrons in any shell. Hence for atoms
with more electrons, more of the valence shells must be occupied,
resulting in the range of elements - each with their unique
properties - found in nature.
Return to MathPages Main Menu