IMO 2021 - Problema 6

Avatar de Usuario
Sandy

OFO - Medalla de Bronce-OFO 2019 OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Copa-FOFO 10 años
OFO - Medalla de Oro-OFO 2021
Mensajes: 248
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 6
Nivel: 3

IMO 2021 - Problema 6

Mensaje sin leer por Sandy »

Sean $m\geq 2$ un entero, $A$ un conjunto finito de enteros (no necesariamente positivos), y $B_1,B_2,B_3,\ldots ,B_m$ subconjuntos de $A$. Suponemos que para cada $k=1,2,\ldots ,m$, la suma de los elementos de $B_k$ es $m^k$. Probar que $A$ contiene al menos $m/2$ elementos.
Fallo inapelable.

Avatar de Usuario
Sandy

OFO - Medalla de Bronce-OFO 2019 OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Copa-FOFO 10 años
OFO - Medalla de Oro-OFO 2021
Mensajes: 248
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 6
Nivel: 3

Re: IMO 2021 - Problema 6

Mensaje sin leer por Sandy »

Solución
Spoiler: mostrar
Sean $\mid A\mid =n$ y $a_1,a_2,\ldots , a_n$ los elementos de $A$. Sean $c_{i,j}\in \{0,1\}$ para $1\leq i\leq n$, $1\leq j\leq m$. Tenemos que, para todo $k$ entre $1$ y $m$, $m^k=\sum \limits _{i=1}^nc_{i,k}a_i$. Sea $x\in \{0,1,2,\ldots ,m^m-1\}$. Es claro que podemos escribir $x=\sum \limits _{j=0}^{m-1}d_{j+1}m^j$ con $d_j\in \{0,1,2,\ldots ,m-1\}$.
Luego tenemos que $mx=\sum \limits _{j=1}^md_jm^j=\sum \limits _{j=1}^md_j\: \sum \limits _{i=1}^nc_{i,j}a_i=\sum \limits _{i=1}^n\left (\sum \limits _{j=1}^md_jc_{i,j}\right )a_i$.
Pero $0\leq \sum \limits _{j=1}^md_jc_{i,j}\leq m(m-1)$. Luego el lado izquierdo toma exactamente $m^m$ valores, mientras que el derecho toma como mucho $[m(m-1)+1]^n$, por lo que obtenemos que $m^m\leq [m(m-1)+1]^n=(m^2-m+1)^n<m^{2n}$, de lo que es inmediato que $n>\frac{m}{2}$.
1  
Fallo inapelable.

Responder