At least two points are $13$ apart Let $x_0,\dots,x_{37}$ be $38$ distinct integral points inside $[0,60]$ with $x_0=0$ (e.g. $0,1,2,\dots 37$ or $0,2,3,\dots 38$, etc). Prove that there exists two points $x_i$ and $x_j$ such that $x_j-x_i=13$.
I thought of pigeonhole principle, but couldn't find a way to apply.
 A: Let the pigeonholes be the congruence classes modulo $13$.  Since two numbers in the pigeonhole must differ by at least $26$, there isn't room for more than $3$ numbers in a pigeonhole.  But only pigeonholes $0$ through $8$ have room for $3$ numbers.  The other $4$ only have room for $2$.  This gives a maximum of $9\cdot3+4\cdot2=37$ with no two differing by $13$.
A: Suppose it's possible. Call $S=\{x_0,...,x_{37}\}$ such a solution.
Then split $[0;60]$ in intervals of length 12, except for the last one.
$$I_1=[0;12]\quad I_2=[13;25]\quad I_3=[26;38]\quad I_4=[39;41]\quad I_5=[42;54]\quad I_6=[55;60]$$
Then consider the map that sends :

*

*every $x\in S\cap I_{2k}\quad\quad$ to $\quad x-13\in \bar{S}\cap I_{2k-1} $

*every $x\in S\cap I_{2k-1}\quad $ to $\quad x+13 \in \bar{S}\cap I_{2k} $.

This map is well-defined except for at most $7$ numbers in $I_5$ (those who lie between $48$ and $54$).
This map is injective and by definition $S$ and $f(S)$ are disjoint subsets of $[0;60]$.
But the cardinality of $S\cup f(S)$ is at least $38 + 38-7= 69 > 61$. Contradiction.
A: Consider remainders of division $x_i$ by $13$. Congruence classes for $0,\ldots,60$ $\pmod{13}$ has crdinalities $5$ (for $9$ classes) or $4$ (for the other $4$ classes: $9,10,11,12$).
We have $38=3\cdot13-1$ numbers, so if we have no remainder with $4$ numbers in it (if we have some, if of cardinality $4$, we're done, if of cardinality $5$ then there are only $1$ vacant place in this congruence class, thus there will be neighbours with the difference of $13$), we have (by the puigenhole principle) $12$ classes with $3$ numbers in each and $1$ class with $2$ numbers.
But within these $12$ classes there are one (hm, at least $3$, but we don't need all) with cardinality $4$ so we'll have neighbours with $13$ difference and we're done.
