Problem #PRU-5045

Problems Mathematical logic
 10–13  2.0

Problem

One of the most useful tools for proving mathematical statements is the Pigeonhole principle. Here is one example: suppose that a flock of 10 pigeons flies into a set of 9 pigeonholes to roost. Prove that at least one of these 9 pigeonholes must have at least two pigeons in it.