The Pigeonhole Principle
Given n pigeonholes, if you place n+1 pigeons into the holes, then at least one
hole contains at least two pigeons.
Profound isn't int? But wait--you can prove stuff with it. For example, we are
given that a book has more chapters than pages, and that each chapter starts on a
new page. If not, then we say that the new chapter "owns" the page it starts on.
Then we can prove that there exists some consecutive chapters such that the
number of pages in those chapters is a multiple of the number of chapters in the
book, which we will call C for short.
If you are asking yourself why? or who cares? at this point, just read on...
The proof:
We start by listing the numbers of pages in all chapters up to chapter 1,2,3,...
until the end of the book. Let's call the numbers Ai.
A1=the number of pages in the first chapter.
A2=the number of pages in the first 2 chapters.
An=the number of pages in the first n chapters.
Now it is possible that some An is a multiple of C. If so, we are done.
So let us then assume that NONE of the An is a multiple of C. Thus if
we divide each An by C, we will get a remainder that cannot be zero,
and must be smaller than C. To put it distinctly, the values that these remainders
can have range from 1 to C-1. But we have C of them, since there are C chapters in
the book. We can now use the pigeonhole principle to conclude that there must be at
least two An with the same remainder. We will just use two of them,
although there could be more, and call those two Alo and Ahi.
If we subtract, Ahi-Alo will give us the number of pages.
The chapters will be from lo+1 to hi.
Now try it yourself:
- First get any book with chapters, a piece of paper, and a pencil.
- Next, write down the page before each new chapter starts.
- If any of those numbers is a multiple of the number of chapters, you're done!
- Otherwise, divide each number by the number of chapters.
- Write down the remainders.
- Look for common values among the remainders--then you're done.
NOTE:
- It is possible that there are MORE than one string of chapters that this works for.
- Although the pigeonhole principle has many uses in proving solutions exist, it
does not always say how to find them..
Coming soon even more cool stuff.Until then ...42...