Maths olympiad question with subset of a $55$ elements of which $2$ numbers differ by 9.

Question

Prove that every subset of $55$ elements of the set $\{1,2,3,\ldots,98,99,100\}$ contains at least $2$ numbers with a difference of $9$.

What I've done is used the following trick:

Divide the set into $\{1,\ldots,50\}$ and the second set is determined by the last element of the first set (i.e. $50$) $+$ the elements of the first set consecutively. Then there are $50$ pairs that differ from $50$. So by the pigeon hole principle if you select 55 elements there are 2 elements who form a pair with a difference of $9$.

Would this proof considered to be valid?

Answer 1

Divide $S=\{1,2,\ldots,100\}$ into the following sets: $$ \{1,10,19,28,37,46,55,64,73,82,91,100\},\quad\text{12 elements} \\ \{2,11,20,29,38,47,56,65,74,83,92\}, \quad\text{11 elements}\\ \{3,12,21,30,39,48,57,66,75,84,93\}, \quad\text{11 elements}\\ \{4,13,22,31,40,49,58,67,76,85,94\},\quad\text{11 elements} \\ \{5,14,23,32,41,50,59,68,77,86,95\}, \quad\text{11 elements}\\ \{6,15,24,33,42,51,60,69,78,87,96\}, \quad\text{11 elements}\\ \{7,16,25,34,43,52,61,70,79,88,97\},\quad\text{11 elements} \\ \{8,17,26,35,44,53,62,71,80,89,98\}, \quad\text{11 elements}\\ \{9,18,27,36,45,54,63,72,81,90,99\}\quad\text{11 elements}. $$ If we pick 55 elements out of these 9 subsets, then in at least one of these subsets, we will have picked at least 7 elements. In such case, in that subset, among the 7 elements, there will be at least a pair of consecutive elements, i.e. of difference 9.

Answer 2

How does the fact that we have $50$ pairs with a difference $50$ helps you conclude there is a pair of integers with differnece $9$?

Here's a hint how to solve this problem. Try to construct a counterexample. Divide the set into subsets modulo $9$. So for example one of the subsets would be: $\{1,10,19,28,37,46,55,64,73,82,91,100\}$. What's the biggest number of integers you can include without having a pair of integers with a difference $9$? Now do the same for all subsets.