The pigeonhole principle: using simplicity to understand complexity
Suppose you have a certain number of pigeons, and a certain number of pigeonholes. You must place each pigeon into one pigeonhole. If you have more pigeons than you do pigeonholes, then clearly there must exist a pigeonhole containing more than one pigeon. This statement is known as the pigeonhole principle. It seems a very trivial and obvious statement. Having twelve pigeonholes for thirteen pigeons will result in an overpopulation of pigeons, so that at least two of them will have to share a hole. However, this simple statement has an astounding number of applications in solving very non-trivial mathematical…