Torneo de las Ciudades - Marzo 2020 - NJ P7

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

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020
Mensajes: 306
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 6
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Torneo de las Ciudades - Marzo 2020 - NJ P7

Mensaje sin leer por Joacoini » Mié 11 Mar, 2020 3:52 pm

Gaby elige enteros positivos $N$ y $a$ ($a<N$) y escribe en el pizarrón el número $a$. Luego, en cada turno, hace lo siguiente: toma el último número escrito en el pizarrón, hace en una hoja aparte la división de $N$ por esté último número y escribe en el pizarrón el resto de esta división. Cuando escriba el número $0$, se detiene. Determinar si puede elegir $N$ y $a$ de modo que la suma de los números del pizarrón sea mayor que $100N$.
NO HAY ANÁLISIS.

Avatar de Usuario
Matías V5

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020
Mensajes: 957
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 7
Nivel: Exolímpico

Re: Torneo de las Ciudades - Marzo 2020 - NJ P7

Mensaje sin leer por Matías V5 » Dom 15 Mar, 2020 7:28 pm

Muchas gracias a @lucasdeamorin y @tuvie por la ayuda para llegar a esta solución.
Spoiler: mostrar
Llamemos $a_1,a_2,a_3,\ldots$ a los números que Gaby escribe en el pizarrón (en particular, $a_1=a$). Vamos a construir un ejemplo en el cual se cumpla que $a_1 > \frac N2$, $a_2 > \frac N3$, $a_3 > \frac N4$, y así siguiendo hasta un término $a_r > \frac{N}{r+1}$. Esto sumado al hecho de que la suma $\frac 12 + \frac 13 + \frac 14 + \ldots + \frac{1}{r+1}$ puede tomar valores arbitrariamente grandes al aumentar $r$ (que demostraremos al final), probará que sí es posible lograr que la suma de los números escritos por Gaby sea mayor que $100N$.
Consideramos los números $$ b_{n,k} = \sum_{i=k}^n (-1)^{k+i} \frac{(k-1)!}{i!},$$ definidos para cualquier par de enteros positivos $(n,k)$ con $n \geq k$. Usaremos estos números para nuestra construcción. Antes, probemos dos propiedades sobre ellos que vamos a necesitar.

Lema 1: Si $n > k+1$, entonces $\frac{1}{k+1} < b_{n,k} < \frac{1}{k}$.
Spoiler: mostrar
Demostración. Notemos que la suma que define a $b_{n,k}$ comienza así: $$\frac{(k-1)!}{k!} - \frac{(k-1)!}{(k+1)!} + \frac{(k-1)!}{(k+2)!} - \ldots = \frac{1}{k} - \frac{1}{k(k+1)} + \frac{1}{k(k+1)(k+2)} - \ldots$$ Si la cantidad de términos desde $i = k + 1$ hasta $i = n$ es par, entonces dichos términos se pueden agrupar en parejas de consecutivos, en las cuales el número que aparece restando es mayor que el que aparece sumando, y por lo tanto el resultado en cada pareja es negativo, así que $b_{n,k} < \frac{1}{k}$. Si en cambio la cantidad de términos es impar, entonces se puede hacer la división en parejas dejando suelto el último término, que también es negativo así que sigue siendo cierto que $b_{n,k} < \frac{1}{k}$.
Para la otra desigualdad, observamos que $\frac{1}{k} - \frac{1}{k(k+1)} = \frac{1}{k+1}$. Ahora si la cantidad de términos desde $i = k + 2$ hasta $i = n$ es par, podemos armar parejas donde el número que aparece sumando es más grande que el número que aparece restando y por lo tanto el resultado es positivo; si la cantidad es impar hacemos lo mismo dejando suelto el último término, que es positivo. En todos los casos se concluye que $b_{n,k} > \frac{1}{k+1}$. $\blacksquare$
Lema 2: Si $n > k$, entonces $b_{n,k+1} = 1 - kb_{n,k}$.
Spoiler: mostrar
Demostración. Sacando factor común $–k$ en la suma que define a $b_{n,k+1}$ obtenemos $$b_{n,k+1} = \sum_{i=k+1}^n (-1)^{k+1+i} \frac{k!}{i!} = -k \left( \sum_{i=k+1}^n (-1)^{k+i} \frac{(k-1)!}{i!} \right) .$$ La suma dentro del paréntesis es $b_{n,k}$ quitándole el término que corresponde a $i = k$, es decir $\frac{1}{k}$. Entonces $b_{n,k+1} = -k \left(b_{n,k} - \frac{1}{k} \right) = 1 - kb_{n,k}$, como habíamos afirmado. $\blacksquare$
Ahora sí veamos cómo elegir $N$ y $a$. Tomamos un entero positivo suficientemente grande $m$, que precisaremos luego. Observemos que $b_{2m,1} < b_{2m+1,1}$, pues el término que se agrega para armar la segunda suma tiene el signo de $(-1)^{1+2m+1}$, es decir que es positivo. Además $b_{2m+1,1} < 1$ (por el Lema 1). Podemos entonces tomar $N$ suficientemente grande de modo que entre $b_{2m,1}N$ y $b_{2m+1,1}N$ haya al menos un entero, y elegir $a$ en ese intervalo.
Veamos que con esta elección, para todo $k \leq 2m-1$ se cumple que
  • si $k$ es impar, entonces $b_{2m,k}N < a_k < b_{2m+1,k} N$; y
  • si $k$ es par, entonces $b_{2m+1,k}N < a_k < b_{2m,k} N$.
Procedemos por inducción. Para $k = 1$ se cumplen las desigualdades pues así se eligió $a$.
Supongamos que $k<2m-1$ es impar y se cumple que $b_{2m,k}N < a_k < b_{2m+1,k} N$. Por el Lema 1, sabemos que en particular $\frac{N}{k+1} < a_k < \frac{N}{k}$; entonces, el cociente de dividir $N$ por $a_k$ es precisamente $k$. Luego, $a_{k+1} = N-ka_k$, así que, en virtud del Lema 2, $$a_k < b_{2m+1,k} N \quad \Rightarrow \quad a_{k+1} > N - kb_{2m+1,k} N = \left(1 - kb_{2m+1,k} \right) N = b_{2m+1,k+1} N,$$ $$a_k > b_{2m,k} N \quad \Rightarrow \quad a_{k+1} < N - kb_{2m,k} N = \left(1 - kb_{2m,k} \right) N = b_{2m,k+1} N.$$ Para $k$ par el paso inductivo se prueba de la misma manera invirtiendo las últimas desigualdades.
Hemos probado que para todo $k \leq 2m-1$ se cumple que $a_k > b_{2m,k}N$ o $a_k > b_{2m+1,k}N$, dependiendo de la paridad de $k$; en ambos casos, por el Lema 1 podemos concluir que $a_k > \frac{N}{k+1}$ (en realidad, para $k=2m-1$ el lema no aplica pero en ese caso es $b_{2m,2m-1} = \frac{1}{2m}$, así que también vale). Entonces la suma de los números escritos por Gaby será mayor que $ \left( \frac 12 + \frac 13 + \frac 14 + \ldots + \frac{1}{2m} \right) N$.
Sólo resta probar que se puede elegir $m$ de modo que la suma entre paréntesis sea mayor que $100$. Afirmamos que $m = 2^{199}$ cumple lo que queremos. En efecto: el primer término de la suma es $\frac12$; los dos siguientes suman más que $2$ veces $\frac14$ (es decir $\frac12$); los cuatro siguientes suman más que $4$ veces $\frac18$ (es decir $\frac12$); y continuamos acotando de esta manera hasta que los últimos $2^{199}$ términos tienen una suma mayor que $2^{199} \cdot \frac{1}{2^{200}} = \frac{1}{2}$. Así, hemos descompuesto nuestra suma en $200$ bloques, cada uno con suma mayor o igual que $\frac12$ (mayor estricto en todos los casos salvo el primer bloque). Por lo tanto, la suma es mayor que $100$.
La solución está completa. $\blacksquare$
3  
"La geometría es el arte de hacer razonamientos correctos a partir de figuras incorrectas." -- Henri Poincaré

Responder