3

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.

anonymous67
  • 3,458

3 Answers3

3

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$.

saulspatz
  • 53,131
1

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.

Ayoub
  • 1,456
  • Since $37+37-13=61$, it suffices to consider the map $x\mapsto x+13$. Your solution is better optimized though. – anonymous67 Jun 20 '20 at 06:53
1

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.

Alexey Burdin
  • 5,214