Let the pigeons be the 16 numbers that you choose. And let the holes be either 0 or 1 or 2, a number is determined in which hole it goes to by its remainder upon division by 3 (i.e. 17 goes into the 2 hole). This means that there are at least elements in A that all have the same remainder upon division by three. Let us call these elements . Since these guys have the same remainder is means is a multiple of three. Assume (for contradiction) that each then it would mean because it needs to be a multiple of three and one of 6,9,12,15,18 or 21 are allowed. But then this means . This is a contradiction therefore there must be so that .