IMO 2003 - P1

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial
Mensajes: 829
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

IMO 2003 - P1

Mensaje sin leer por Gianni De Rico » Mié 18 Jul, 2018 3:26 pm

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.
[math]

Avatar de Usuario
jhn

OFO - Medalla de Plata
Mensajes: 504
Registrado: Mié 10 Oct, 2012 3:25 pm
Medallas: 1
Nivel: Otro
Ubicación: Venezuela
Contactar:

Re: IMO 2003 - P1

Mensaje sin leer por jhn » Lun 23 Jul, 2018 6:45 am

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.
Todo problema profana un misterio; a su vez, al problema lo profana su solución.
https://jhnieto.000webhostapp.com/

Responder