Prove that from any set of of 100 integers one can choose 15

Solution

method 1--

Let S be a set of 100 integer numbers.

Dividing each element of S by 7 we will get a new set Swith 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..

Since 714=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.

method 2--

For the difference to be a multiple of 7, the integers must have equal modulo 7 residues.

To avoid having 15 with the same residue, 14 numbers with different modulo 7 residues can be picked (14*7=98). Thus, two numbers are left over and have to share a modulo 7 residue with the other numbers under the pigeonhole principle.