OFO 2018 Problema 9

Problemas que aparecen en el Archivo de Enunciados.
tuvie

Colaborador-Varias OFO - Medalla de Oro-OFO 2015 OFO - Medalla de Oro-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Jurado-OFO 2017
FOFO 7 años - Jurado-FOFO 7 años OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 OFO - Jurado-OFO 2021 OFO - Jurado-OFO 2022
Mensajes: 629
Registrado: Dom 09 Sep, 2012 11:58 am
Medallas: 14
Nivel: Exolímpico

OFO 2018 Problema 9

Mensaje sin leer por tuvie »

Cada número entero positivo se pintó de celeste o de blanco. Probar que existe una sucesión infinita $a_1 < a_2 < a_3 < \ldots$ de números enteros positivos tal que los números $$ a_1, \, \frac{a_1+a_2}{2}, \, a_2, \, \frac{a_2+a_3}{2}, \, a_3, \, \ldots $$ son enteros positivos y además están todos pintados del mismo color.
tuvie

Colaborador-Varias OFO - Medalla de Oro-OFO 2015 OFO - Medalla de Oro-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Jurado-OFO 2017
FOFO 7 años - Jurado-FOFO 7 años OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 OFO - Jurado-OFO 2021 OFO - Jurado-OFO 2022
Mensajes: 629
Registrado: Dom 09 Sep, 2012 11:58 am
Medallas: 14
Nivel: Exolímpico

Re: OFO 2018 Problema 9

Mensaje sin leer por tuvie »

Solución Oficial:
Spoiler: mostrar
Supongamos que es imposible conseguir una sucesión como la requiere el enunciado, y obtengamos un absurdo.

Consideremos sin perdida de generalidad que al $1$ lo pintamos de celeste.

Comenzamos $x_1=1$ y empezamos a construir una sucesión $x_1,x_2,\ldots,x_M$ (notar que son todos impares) de forma tal que todos los promedios consecutivos son celestes, y de forma tal que no podemos definir $x_{M+1}$ para que $\frac{x_M+x_{M+1}}{2}$ y $x_{M+1}$ sean celestes. Esto quiere decir que para cualquier entero positivo $a$, $x_M+a$ y $x_M+2a$ no pueden ser ambos celestes.

Notar en particular que existe un blanco impar mayor a $x_M$ que definimos como $y_1$ (pues de lo contrario, si a partir de $2l+1$ todos los impares son celestes, tomamos $2l+1,2l+5,2l+9,\ldots$) y hacemos lo mismo que antes. Construimos $y_1,y_2,y_3,\ldots,y_N$ hasta que no podamos construir mas. Esto hace que para cualquier entero positivo $a$, alguno de $y_N+a$ y $y_N+2a$ debe ser celeste, o sea, no pueden ser ambos blancos.

Consideramos ahora un entero positivo $X>y_N$ que sea blanco. Entonces, debe ser que $2X-y_N$ es celeste por el argumento del segundo párrafo, y por lo tanto, como $2X-y_N$ es impar, debe ser $\frac{x_M+2X-y_N}{2}=X-\frac{x_M-y_N}{2}$ de color blanco por el argumento del primer párrafo. En síntesis, si $X>y_N$ es blanco, entonces $X-\frac{x_M-y_N}{2}$ es blanco. Tomando el contrarrecíproco, tenemos que si $Y>y_N$ es celeste, entonces $Y+\frac{x_M-y_N}{2}$ es celeste, y por lo tanto comenzando con $z_1$ un blanco cualquiera mayor a $y_N$ (que si no existe es porque a partir de un momento son todos celestes) tenemos que $z_1 = Y+n\cdot \frac{x_M-y_N}{2}$ es celeste para todo $n$, como requería el enunciado. Pero esto es un absurdo.

Concluimos entonces que lo que pide el enunciado siempre se puede lograr.
jujumas

OFO - Mención-OFO 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Oro perfecto-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017
FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
FOFO 9 años - Jurado-FOFO 9 años OFO - Jurado-OFO 2020 COFFEE - Jurado-COFFEE Ariel Zylber
Mensajes: 402
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 13
Nivel: Exolímpico

Re: OFO 2018 Problema 9

Mensaje sin leer por jujumas »

Espero que mi letra se entienda más o menos bien.
Spoiler: mostrar
OFO 2018 Problema 9.pdf
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
Avatar de Usuario
davisbeckam18

OFO - Medalla de Bronce-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 OFO - Medalla de Oro-OFO 2018
Mensajes: 19
Registrado: Sab 17 Dic, 2016 8:57 pm
Medallas: 3
Nivel: 2

Re: OFO 2018 Problema 9

Mensaje sin leer por davisbeckam18 »

Solución
Spoiler: mostrar
Sean $a_1< a_2< a_3< ...$ una secuencia infinita de enteros positivos. Llamemos $especial$ a dicha secuencia si verifica que en la secuencia siguiente todos sus términos son enteros y están pintados del mismo color.
$$ a_1, \, \frac{a_1+a_2}{2}, \, a_2, \, \frac{a_2+a_3}{2}, \, a_3, \, \ldots $$
Partamos por contradicción, es decir que no podemos una secuencia infinita de enteros positivos que sea $especial$.
Supongamos que existe una cantidad finita de números pintados de alguno de los dos colores. Entonces podemos tomar un $a_1$ muy grande tal que los números $a_1< a_2< ...$ sean de la misma paridad y estén pintados del mismo color y por tanto formarían una secuencia $especial$. Contradicción.
Ahora supongamos que existen infinitos números pintados de cada color. Si todos los pares estuvieran pintados de un mismo color, entonces la secuencia $a_1< a_2< a_3 ...$ donde $a_i$ es múltiplo de 4 sería $especial$, ya que es fácil ver que todos los términos de la secuencia $ a_1, \, \frac{a_1+a_2}{2}, \, a_2, \, \frac{a_2+a_3}{2}, \, a_3, ...$ serán pares y por tanto todos los números del mismo color (por lo supuesto de que todos los pares están pintados de un mismo color). Contradicción.
Supongamos ahora que existen al menos un número par de cada color. Sin pérdida de generalidad, $2\alpha<2\beta$, donde el primero es de celeste y el segundo deblanco. Probemos que existe una secuencia infinita de enteros positivos $especial$ donde su primer término es $\alpha_1=2\alpha$ o $\beta_1=2\beta$ (sean estas secuencias $T_ \alpha$ y $T_\beta$). De hecho probaremos que si tenemos dos secuencias finitas de números pares que sean $especiales$: $x_1< x_2<...<x_k$ ; $y_1< y_2<...<y_l$ (supongamos que $x_k<y_l$), entonces siempre podemos encontrar un nuevo número par mayor que $y_l$ tal que al "agregarlo" a alguna de las dos secuencias anteriores, esta sigue siendo $especial$. Llamemos $algoritmo$ a este proceso. Si aplicamos infinitas veces el $algoritmo$, entonces agregaríamos (contando a las dos) infinitos términos a las dos secuencias iniciales. Entonces, por casillas al menos una de las dos secuencias tendrá una cantidad infinita de números y además sería $especial$. Nuevamente por contradicción supongamos que no existe una secuencia $especial$ donde su primer término sea o $2\alpha$ o $2\beta$. Denotemos por $F(a_i)=C$ si el término $a_i$ es de color celeste. De forma similar si fuera de color blanco. Consideremos la secuencia $a_i=(3-i)\alpha+(i-1)\beta$, con $i=1,2,3, ...$. Notemos que $a_1=2\alpha> 0$ ; además si $i<j$ entonces $(j-i)\alpha<(j-i)\beta$ $\Rightarrow$ $3\alpha -\beta + (j-i)\alpha < 3\alpha -\beta +(j-i)\beta$ $\Rightarrow$ $(3-i)\alpha+(i-1)\beta < (3-j)\alpha+(j-1)\beta$ $\Rightarrow$ $a_i < a_j$. Entonces cada término es positivo. Por lo supuesto $F(a_1=\alpha_1)=C$ y $F(a_3=\beta_1)=B$. Si $F(a_5)=B$, además si $F(a_4)=B$ $\Rightarrow$ Hacemos que $\beta_2=a_4$ y $\beta_3=a_5$ en $T_\beta$ (porque $\frac{a_3+a_5}{2}=a_4$ y los tres son del mismo color) . Pero si $F(a_4)=C$, además si $F(a_7)=C$ $\Rightarrow$ Hacemos que $\alpha_2=a_4$ y $\alpha_3=a_7$ en $T_\alpha$ (porque $\frac{a_1+a_7}{2}=a_4$). Pero si $F(a_7)=B$ $\Rightarrow$ Hacemos que $\beta_2=a_5$ y $\beta_3=a_7$ en $T_\beta$ (porque $\frac{a_3+a_7}{2}=a_5$). Ahora si $F(a_5)=C$, además si $F(a_9)=C$ $\Rightarrow$ Hacemos que $\alpha_2=a_5$ y $\alpha_3=a_9$ en $T_\alpha$ (porque $\frac{a_9+a_1}{2}=a_5$). Pero si $F(a_9)=B$, además si $F(a_6)=B$ $\Rightarrow$ Hacemos $\beta_2=a_6$ y $\beta_3=a_9$ en $T_\beta$ (porque $\frac{a_9+a_3}{2}=a_6$). Pero si $F(a_6)=C$, además si $F(a_{11})=C$ $\Rightarrow$ Hacemos $\alpha_2=a_6$ y $\alpha_3=a_{11}$ en $T_\alpha$ (porque $\frac{a_{11}+a_1}{2}=a_6$). Pero si $F(a_{11})=B$, además si $F(a_7)=B$ $\Rightarrow$ Hacemos $\beta_2=a_7$ y $\beta_3=a_{11}$ en $T_\beta$ (porque $\frac{a_{3}+a_{11}}{2}=a_7$). Pero si $F(a_7)=C$, además si $F(a_{13})=C$ $\Rightarrow$ Hacemos $\alpha_2=a_7$ y $\alpha_3=a_{13}$ en $T_\alpha$ (porque $\frac{a_{13}+a_1}{2}=a_7$). Pero si $F(a_{13})=B$, además si $F(a_8)=B$ $\Rightarrow$ Hacemos $\beta_2=a_8$ y $\beta_3=a_{13}$ en $T_\beta$ (porque $\frac{a_{13}+a_3}{2}=a_8$). Pero si $F(a_8)=C$, además si $F(a_{15})=C$ $\Rightarrow$ Hacemos $\alpha_2=a_8$ y $\alpha_3=a_{15}$ en $T_\alpha$ (porque $\frac{a_{15}+a_1}{2}=a_8$). Pero si $F(a_{15})=B$ $\Rightarrow$ Hacemos $\beta_2=a_9$ y $\beta_3=a_{15}$ en $T_\beta$ (porque $\frac{a_{15}+a_3}{2}=a_9$).
Vemos que en todos los casos a $T_\alpha$ o a $T_\beta$ le "agregamos" mediante el $algoritmo$ dos términos más tal que esta sigue siendo $especial$. Además, estos dos términos son los mayores contando ambas sucesiones. Como podemos repetir el $algoritmo$ infinitas veces, al menos una de las sucesiones $T_\alpha$ o $T_\beta$, por casillas, tendrá infinitos términos. Contradicción.
Hemos llegado a una contradicción en todos los casos. Entonces existe una sucesión "especial" de infinitos términos.
Última edición por davisbeckam18 el Jue 09 Ago, 2018 10:12 am, editado 1 vez en total.
Avatar de Usuario
Elsa Muray

OFO - Medalla de Bronce-OFO 2018
Mensajes: 23
Registrado: Vie 26 Ene, 2018 3:10 pm
Medallas: 1
Nivel: 1
Ubicación: La Plata

Re: OFO 2018 Problema 9

Mensaje sin leer por Elsa Muray »

Responder