# Choosing $15$ out of $100$ whole numbers with difference of any $2$ divisible by $7$

How can we prove with the pigeonhole principle that having $100$ whole numbers, one can choose $15$ of them so that the difference of any $2$ is divisible by $7$?

-
Hint: consider remainders upon dividing by 7. – vadim123 Sep 3 '13 at 4:26
And $100 / 7 > 14$. – ShreevatsaR Sep 3 '13 at 4:34

## 2 Answers

Let $S$ be a set of $100$ integer numbers. Dividing each element of $S$ by $7$ we will get a new set $S'$ with residues modulo $7$ elements. Next, we divide that new set $S'$ into $7$ subsets, where each subset contains $14$ elements with the same residue modulo $7$. If we can't find such division into $7$ sets, then we are done(why?). Since $7\cdot 14=98$, we left with two elements, by taking one of them and putting in the suitable set(of the seven), we get a set of $15$ numbers with same residue modulo $7$.

-

Let the pigeonholes consist of the remainders after division by 7. Let the pigeons be the 100 numbers. By the generalized PHP, some pigeonhole must have at least $$\left\lceil \frac{100}{7}\right\rceil = 15$$ pigeons. These 15 numbers all have the same remainder upon division by 7; hence the difference of any pair is a multiple of 7.

-