You open a book in English and pick some words at random. How many words would you have to read to ensure that at least two of them start with the same letter?
Keep reading to find out, or skip ahead to today's challenge.
If you read just words, they can easily start with different letters, say A and B. Adding an extra word doesn't help much, because it could start with C, for example. It's possible, albeit unlikely, that even words start with different letters from A to Z. However, if you add more word, its first letter must have been already used simply because the English alphabet contains fewer than letters.
This is a direct consequence of a seemingly obvious but very powerful theorem, the pigeonhole principle:
If items are put into containers, where then at least one container must contain more than one item.
In this case, we put "items" (words) into "containers" (letters), so one letter had to be assigned two words.
We'll take a look at one more application, this time in number theory. Let's choose at random distinct integers between and The pigeonhole principle tells us that at least two of our integers are consecutive. Why?
Suppose we start at and pair off consecutive integers so we have sets This gives us "containers" to put our "items" into. Since we pick numbers ("items"), at least one of our "containers" must hold two numbers, which are a consecutive pair.
Now you're ready to tackle today's challenge!