go back

based on the cambridge seniors maths chapter 1H

Pigeonhole principle

If n+1 or more objects are placed into n holes, then some hole contains at least two objects

Example 31

You have 13 red, 10 blue and 8 green socks. How many socks need to be selected at random to ensure that you have a matching pair.

Solution:

Label three holes with the colours red, blue and green. R B G Selecting just three socks is clearly not sufficient, as you might pick one sock colour. Selet four socks and place each sock into the hole corresponding to the colour of the sock. As there are four socks and three holes, the pigeonhole principle guarantees that some hole contains at least two socks. This is the required pair.

Generalised Pigeonhole principle

If at least mn + 1 objects are placed into n holes, then some hole contains at least m + 1 objects

Example 33

Sixteen natural numbers are written on a whiteboard. Perove that at least four numbers will leave the same remainder when divided by 5.

Solution

We label five holes with each of the possible remainders on division by 5. 0 1 2 3 4 There are 16 numbers to be placed into five holes. Since there is some hole with at least 4 numbers, each of which leaves the same remainder when divided by 5.