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

2.6k Views Asked by At

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$?

3

There are 3 best solutions below

0
On

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$.

0
On

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.

3
On

I don't get it? Should 8 pigeons or numbers is enough so that the difference of any 2 numbers is divisible by 7.

For example if one picked 1, 2, 3, 4, 5, 6, 7 and one random whole number, the difference of the last number with any of 1 to 7 should be divisible by 7.

Please correct me if I am wrong.