FOFO 12 Años - Problema 4

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
LorenzoRD

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Mención-FOFO Pascua 2020 COFFEE - Mención-COFFEE Carolina González FOFO 10 años - Medalla-FOFO 10 años
OFO - Medalla de Bronce-OFO 2021 FOFO 11 años - Mención-FOFO 11 años FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023
Mensajes: 44
Registrado: Dom 13 Ene, 2019 11:07 pm
Medallas: 9
Nivel: Exolímpico
Ubicación: Almagro

FOFO 12 Años - Problema 4

Mensaje sin leer por LorenzoRD »

Sean $a_1,a_2,\ldots ,a_M$ números enteros no negativos tales que$$\frac{1}{2^{a_1}}+\frac{1}{2^{a_2}}+\cdots +\frac{1}{2^{a_M}}=1.$$Demostrar que $a_i<M$ para todo $i$.
1  
Ver este mensaje... te llena de determinación.
Avatar de Usuario
LorenzoRD

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Mención-FOFO Pascua 2020 COFFEE - Mención-COFFEE Carolina González FOFO 10 años - Medalla-FOFO 10 años
OFO - Medalla de Bronce-OFO 2021 FOFO 11 años - Mención-FOFO 11 años FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023
Mensajes: 44
Registrado: Dom 13 Ene, 2019 11:07 pm
Medallas: 9
Nivel: Exolímpico
Ubicación: Almagro

Re: FOFO 12 Años - Problema 4

Mensaje sin leer por LorenzoRD »

Aquí publicaremos la solución oficial.
Ver este mensaje... te llena de determinación.
FabriATK

COFFEE - Mención-COFFEE Matías Saucedo OFO - Mención-OFO 2020 COFFEE - Mención-COFFEE Carolina González COFFEE - Mención-COFFEE Iván Sadofschi OFO - Medalla de Plata-OFO 2021
FOFO 11 años - Mención-FOFO 11 años OFO - Medalla de Plata-OFO 2022 FOFO Pascua 2022 - Mención-FOFO Pascua 2022 FOFO 12 años - Medalla-FOFO 12 años OFO - Medalla de Plata-OFO 2023
OFO - Jurado-OFO 2024
Mensajes: 60
Registrado: Mié 17 Abr, 2019 11:17 pm
Medallas: 11
Nivel: Exolímpico
Ubicación: Corrientes

Re: FOFO 12 Años - Problema 4

Mensaje sin leer por FabriATK »

Solución:
Spoiler: mostrar
Supongamos WLOG que $a_1 \geq a_2 \geq a_3\geq ... \geq a_m$

$\frac{1}{2^{a_1}} + \frac{1}{2^{a_2}}+...+ \frac{1}{2^{a_m}} = 1$

$\frac{1 + 2^{a_1-a_2} + 2^{a_1 - a_3}... + 2^{a_1 - a_m}}{2^{a_1}} = 1$

$1 + 2^{a_1-a_2} + 2^{a_1 - a_3}... + 2^{a_1 - a_m} = 2^{a_1}$

Y supongamos que existe $a_i$ tal que $a_i \geq m$
Entonces $a_1 \geq m$

Ahora supongamos que existe $K$ tal que:

$1 + 2^{a_1-a_2} + 2^{a_1 - a_3}... + 2^{a_1 - a_k} \not \equiv 0 \pmod {2^u}$ y $a_1 - a_{k+1} \geq u$ Para algún $1 \leq u \leq m$ natural

Como $a_{k+1} \geq a_{k+2}...\geq a_m$ entonces $a_1- a_{k+1} \leq a_1 - a_{k+2} \leq ... \leq a_1 - a_m$

Así que si que si $a_1 - a_{k+1} \geq u$ entonces $ a_1 - a_{k+2}, ... ,a_1 - a_m$ también.
Así que $2^{a_1-a_{k+1}} \equiv 2^{a_1-a_{k+2}} ... \equiv 2^{a_1-a_{m}} \equiv 0 \pmod{2^u}$

Luego, $1 + 2^{a_1-a_2} + 2^{a_1 - a_3}... + 2^{a_1 - a_m} \equiv 1 + 2^{a_1-a_2} + 2^{a_1 - a_3}... + 2^{a_1 - a_k} \not \equiv 0 \pmod {2^u}$


Y nosotros queremos que $1 + 2^{a_1-a_2} + 2^{a_1 - a_3}... + 2^{a_1 - a_m} \equiv 0 \pmod{2^m}$

Y por lo que dijimos antes, si $1 + 2^{a_1-a_2} + 2^{a_1 - a_3}... + 2^{a_1 - a_k} \not \equiv 0 \pmod {2^{k+1}}$, $a_1- a_{k+1}$ será a lo mucho $k$.


Usando eso mostramos, por inducción, que $a_1 - a_{k+1} \leq k-1$ para todo k natural:
Spoiler: mostrar
Supongamos que $1 + 2^{a_1-a_2} + 2^{a_1 - a_3}... + 2^{a_1 - a_{k-1}} = 2^{k-2}$, entonces por lo que dijimos, $a_1 - a_{k} \leq k-2$

y Ahora $1\leq 1 + 2^{a_1-a_2} + 2^{a_1 - a_3}... + 2^{a_1 - a_k} \leq 2^{k-2} + 2^{k-2} = 2^{k-1}$

Entonces $ 1 + 2^{a_1-a_2} + 2^{a_1 - a_3}... + 2^{a_1 - a_k} \not \equiv \pmod{2^{k}}$
así que $a_1 - a_{k+1} \leq k-1$
Y tenemos caso base con $k = 2$.
Entonces $1 + 2^{a_1-a_2} + 2^{a_1 - a_3}... + 2^{a_1 - a_m} \leq 1 + 2^0 + 2^1 + ... + 2^{m-2} = 2^{m-1} < 2^m$

Así que no puede existir $a_i$ tal que $a_i \geq m$ y estamos.
Avatar de Usuario
fran :)

FOFO 12 años - Mención-FOFO 12 años OFO - Medalla de Plata-OFO 2023 FOFO 13 años - Copa-FOFO 13 años
Mensajes: 20
Registrado: Mié 22 Jun, 2022 6:04 pm
Medallas: 3
Nivel: 3
Ubicación: Buenos Aires

Re: FOFO 12 Años - Problema 4

Mensaje sin leer por fran :) »

Mi solución, que me dio 7 puntos:
Spoiler: mostrar
Nota: Voy a usar $2^{-x}$ en vez de $\frac{1}{2^x}$ porque es más corto.

Resumen de la solución: Primero pruebo que en todas las sumas así hay dos $a_i$ que son iguales. Esto lo uso para hacer inducción, porque puedo sumar esos dos para crear una suma con un término menos pero que suma lo mismo, y así hasta llegar a $1 = 1$. También pruebo que en esta transformación, la propiedad $a_i<M$ se conserva. Entonces hago inducción y queda probado.

Lema 1: Para cualquier x entero, $2^m + 2^n = 2^x$ si y solo si $m = n = x - 1$
Prueba:
Spoiler: mostrar
Lema 1.1: Para cualquier entero $x, m, n$, si $2^m + 2^n = 2^x$, entonces $m = n = x - 1$
Prueba:

$2^m + 2^n = 2^x$
Sea $d = m - n$
$2^{d + n} + 2^n = 2^x$
$2^d 2^n + 2^n = 2^x$
$2^n (2^d + 1) = 2^x$
$2^d + 1 = 2^{x - n}$

Las únicas dos potencias de 2 que difieren por 1 son $2^0$ y $2^1$, entonces
$d = 0$, $x - n = 1$.
$m = n = x - 1$. QED

Lema 1.2: Para cualquier x entero, si $m = n = x - 1$, $2^m + 2^n = 2^x$
Prueba: $ 2^x = 2^x = 2 \cdot 2^{x - 1} = 2^{x - 1} + 2^{x - 1} = 2^m + 2^n$. QED

Entonces:
Lema 1: Para cualquier x entero, $2^m + 2^n = 2^x$ si y solo si $m = n = x - 1$
Lema 2: Asumimos sin pérdida de generalidad que $a_m$ es el mayor de todos los numeros en conjunto, y que todos los numeros están ordenados de menor a mayor.

Lema 3: Para cualquier serie de sumas del tipo especificado en el problema con $m > 1$, siempre va a haber dos $a_x$ que sean iguales.

Prueba:
Spoiler: mostrar
Vamos a probarlo por contradicción. Asumimos que todos son distintos.

Como $m > 1$, entonces todos los $a_x$ son mayores a $0$. (porque $2^{-0}+2^{-a_x}$ ya es $> 1$ sin importar el valor de $a_x$).

Es un hecho conocido que la suma infinita $2^{-1}+2^{-2}+2^{-3}...$ converge a 1.

En la suma $2^{-1}+2^{-2}+2^{-3}...$ hay infinitos terminos, todos de la forma $2^{-n}$ donde n es un entero positivo
En la suma $2^{-a_0}+2^{-a_1}+...+2^{-a_m}$ hay $m$ terminos, todos de la forma $2^{-n}$ donde n es un entero positivo

Entonces, por el principio del palomar, hay términos en la suma $2^{-1}+2^{-2}+2^{-3}...$ que no están en $2^{-a_0}+2^{-a_1}+...+2^{-a_m}$, pero no al revés (porque la suma $2^{-1}+2^{-2}+2^{-3}...$ tiene a todos los enteros negativos en los exponentes, pero $m$ es finito)

Entonces $2^{a_0}+2^{a_1}+...+2^{a_m} < 2^{-1}+2^{-2}+2^{-3}...$, entonces $2^{-a_0}+2^{-a_1}+...+2^{-a_m} < 1$ que contradice lo que dice el problema.
Entonces necesariamente hay dos $a_x$ que son iguales. QED
Lema 4: $a_m < m$ para todo $m > 0$
Prueba:
Spoiler: mostrar
Voy a probarlo por inducción.
Lema 4.1: Para $m = 1$, $a_m < m.$
Prueba:
$2^{-a_m} = 1$
$2^{-a_m} = 2^0$
$-a_m = 0$
$a_m = 0 < 1$. QED

Lema 4.2: Para todo $q$, si $a_i < m$ cuando $m = q$, entonces $a_i < m$ cuando $m = q + 1$ para todo $i$
Prueba:

Lema 4.2.1: Para todo $a_i$ cuando $m = q$, $a_i < q$, porque $a_i < m$ cuando $m = q$.

Sea $T$ una suma cualquiera del tipo del problema con $m = q + 1$

Por el Lema 3, agarro a dos $2^{-a_x}$ que son iguales en $T$, y los sumo.

Llamamos $S$ a esta suma. En la suma $S$, $m = (q + 1) - 1 = q$, porque unimos dos términos de $T$ que tiene $q + 1$ términos.

Por el Lema 1, el término que me queda en la suma $S$ es $2^{-(a_x-1)}$. Todos los demás $a$ son iguales en las dos sumas Entonces tenemos que.

Lema 4.2.2: Todos los $a_i$ en $T$ tal que $a_i \neq a_x$ también están en $S$.

$a_q$ es el mayor $a_i$ en $S$ por el lema 2 y $a_{q+1}$ es el mayor $a_i$ en $T$ por la misma razón.

Recordamos que $a_x$ y $a_x - 1$ está en $T$, $a_x - 1$ y $a_q$ en $S$,

En la suma S se cumple que $a_i < m$ para todo $i$, entonces $a_q < q$

Como $2^{a_x - 1}$ está en $S$, $a_x - 1 \leq a_q < q$

Vamos a comparar uno por uno todos los $a_i$ de $T$ con $q + 1$ y probar que $a_i < q + 1$.

Para cada $a_i$, hay dos casos:

$a_i \neq a_x$.
Spoiler: mostrar
En este caso, por el lema 4.2.2, $a_i$ está en $S$ porque es distinto a $a_x$. Entonces por el lema 4.2.1, $a_i < q$. Entonces $a_i < q + 1$. QED.
$a_i = a_x$
Spoiler: mostrar
En este caso, $a_i - 1$ está en $S$ porque $a_x - 1$ está en $S$.

Por el lema 4.2.1, $a_i - 1 < q$. Entonces, $a_i < q + 1$. QED
Cubrimos todos los casos entonces $a_i < q + 1$ siempre. Entonces, $a_m < q + 1$ porque $i$ puede ser $m$. QED.

Tenemos una prueba para $a_m < m$ cuando $m = 1$, y $a_m < m$ cuando $m = n + 1$ y la condición se cumple para $m = n$. Entones, por inducción en los naturales, podemos probar que $a_m < m$ para todo $m > 0$. QED
Como $a_m$ es el mayor de los términos, entonces $a_i < m$ para todo $m$, $i$. QED
$$\phantom{[muajajacaracteresinfinitos=}\begin{matrix}(λx.F\;a)&→&x=a;F\\(\{x_0\;x_1\}\;a)&→&\{a_0\;a_1\}=a;\{(x_0\;a_0)\;(x_1\;a_1)\}\\\{a_0\;a_1\}=\{b_0\;b_1\}&→&a_0=b_0;a_1=b_1\\\{a_0\;a_1\}=λx.F&→&x=\{x_0\;x_1\};\{f_0\;f_1\}=F;a_0=λx_0.f_0;a_1=λx_1.f_1\end{matrix}\phantom{]}$$
Responder