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
.