You have the numbers 1,2,3...,99,100. From that set you have to choose 55 different numbers.
Show that:
There are 2 numbers with a difference 9,10,12,13
Show that there aren't neccessarily 2 with a difference 11.
I have no idea how to do this, it seems really counterituitive to me. How do i approach this?
Reworded to be correct: Prove that however one selects 55 integers 1 ≤ x1 < x2 < x3 < ... < x55 ≤ 100, there will be some two that differ by 9, some two that differ by 10, a pair that differ by 12, and a pair that differ by 13. Surprisingly, there need not be a pair of numbers that differ by 11.
Start by choosing numbers from your set of numbers and think yout the pigeonhole principle:
For differing by $9$, we would arrange $9$ consecutive numbers $1$ to $9$, but then need a gap of 9, so the next would be $19-27$, continuing with $37-45$, $55-63$, $73-81$, $91-99$. This uses $54$ numbers, with no place for the 55th except in some hole less that is than $9$ from some other entry. Only by choosing $100$ will it differ from only one other number. All other choices will differ by $9$ from two numbers.
For $10$, we have $1-10$, $21-30$, $41-50$, $61-70$, $81-90$ which leaves $5$ numbers and all remaining holes ten away from an existing number.
For $11$, we have $1-11$, $23-33$, $45-55$, $67-77$, and $89-100$, which uses all $55$ numbers.
Twelve can have $1-12$, $25-36$, $49-60$, $73-84$, $97-100$, which accounts for $52$ of the $55$.
Thirteen can have $1 -13$, $27-39$, $53-65$, $79-91$,which accounts for $52$ of the numbers. Note that once we can have $\lfloor55/4 \rfloor$= 14 numbers in a group there is no problem, e.g. $1 -14$, $29-42$, $57-71$, $86-99$ allows for $56$ numbers.