Pigeon hole principle to prove $a-b=9$ in subset.

Question

I have a set of numbers $$ [n] = \{1,2,...,n\} $$ in my special case $n = 100$, and I have a subset of $[100]$ with the following specification $$ A\subseteq[100] $$ and $$ |A| >= 55 $$ now I should prove, that this statement is true for some $$ a,b\in A: a-b=9 $$

I thought about the problem and I realised, that if I just take the numbers $1-55$ that there are a lot of pairs $a,b$ that match the condition.

So I tried to build a set in which no pair matches the condition. Therefore I just used the even numbers from $2-100$. Because even-even=even. But there are only $50$ even numbers in $[100]$, so I have to add at least $5$ odd numbers. So as soon as I add one odd number my set matches the condition.

Using the pigeonhole principle: $$ n,m \in \mathbb{N}, f: [n] \to [m], |f^{-1}(j)|, j \in [m], \exists j^{*} \in [m], |f^{-1}|>=\lceil\frac{n}{m}\rceil $$ I get, that there is at least $$ \lceil\frac{100}{55}\rceil = 1 $$ solution to my problem.

But I think that I have to specify the function for the projection to prove the problem. And I think that I can use the modulo operator to achieve my goal, but currently I am stuck. Could someone please help me?

Answer 1

First consider partitioning [$100$] in following manner :

$$ \{1,2,\ldots,18 \} \, \{19,20,\ldots,36 \} \cdots \{73,74,\ldots,90 \} \, \{91,92,\ldots,100 \} $$

Now in each of first five sets we have $9$ pairs differing by $9$ like $$ (1,10) , (2,11) , \ldots (9,18), \ldots, (89,90) $$

and in last, one pair $(91,100)$. Remaining are unpaired.

Can you complete?

We have $9\cdot5+1=46$ pairs. And $8$ : ${92,93,\ldots,99}$ are unpaired. To make a set $A$ not having the property, choose one number from each pair and all the unpaired ones. But we can choose only $46+8=54$ such numbers. $55^{th}$ number belongs to one of previous pairs, so $a-b=9$ must satisfy.