Let $N=\{1,2,...,100\}$ and $A$ be a subset of $N$ with $|A|=55$. Show that $A$ contains two numbers with difference $9$. Is this also true for $|A|=54$?
I was trying to solve this via the pigeonhole principle:
Consider pairs of elements taken from $N$ with differences of $9$. e.g. $\{1,10\}, \{2,11\}, \{3,12\}, \ldots , \{n, n+9\}$, where $1 \leq n \leq 91$, as the lower and upper bounds of $N$ are $1$ and $100$. Thus there are $91-1= 90$ possible pairs which result in a difference of $9$. I reasoned that thus, if $|A|=91$, that via the pigeonhole principle, the extra element would necessarily have to pair and be a difference.
However, intuitively this seems wrong (also obviously so since it asks me to prove $|A|$ must only equal $55$). I think I am misunderstanding the application of the pigeonhole principle...any help/alternative solutions would be appreciated!
Look at the numbers modulo $9$. There are $55$ numbers you are putting into $9$ categories, at least one of the modulo classes has $7$ numbers in there. If they were all separated by at least $18$, they would have minimum difference of $108$ from the biggest and smallest element.