IMO 2003 - P1

[Gianni De Rico]

Sea $A$ un subconjunto del conjunto $S=\{1,2,\ldots ,1000000\}$ con $101$ elementos exactamente. Demostrar que existen números $t_1,t_2,\ldots ,t_{100}$ en $S$ tales que los conjuntos

$A_j=\{x+t_j\mid x\in A\}$ para $j=1,2,\ldots ,100$

son disjuntos dos a dos.

[jhn]

Spoiler: mostrar

Sea $D=\{x-y:x,y\in A\}$. $A_i$ y $A_j$ tienen un elemento común $x+t_i=y+t_j$ si y sólo si $t_i-t_j=y-x\in D$, por lo tanto elegiremos los $t_i$ de modo que las diferencias entre ellos no estén en $D$. Hay a lo sumo $101\times 100$ diferencias de dos elementos distintos de $A$, luego agregando el 0 se tiene que $|D|\le 10101$. Escojamos como $t_1$ cualquier elemento de $S$, como $t_2$ cualquier elemento de $S\setminus (A+t_1)$, como $t_3$ cualquier elemento de $S\setminus (A+t_1)\cup(A+t_2)$ y así sucesivamente hasta $t_{100}$ cualquier elemento de $S\setminus \bigcup_{i=1}^{99}(A+t_i)$. Estas elecciones son posibles pues
$|\bigcup_{i=1}^k(A+t_i)|\le 10101k\le 999999<1000000$. Listo.