OFO 2019 Problema 5

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

OFO - Medalla de Bronce-OFO 2015 OFO - Medalla de Bronce-OFO 2016 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 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022
Mensajes: 157
Registrado: Sab 15 Sep, 2012 6:28 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: San Martín, Buenos Aires

OFO 2019 Problema 5

Mensaje sin leer por AgusBarreto »

Para cada entero positivo $n$, sea $f(n)$ el mayor cubo perfecto menor o igual a $n$. Por ejemplo, $f(10)=8$ y $f(1)=1$. Sea $a$ un entero positivo. Definimos la sucesión $a_0,a_1, \ldots$ por $a_0=a$ y $a_{n+1}=3a_n-2f(a_n)$.
Hallar todos los valores de $a$ para los que esta sucesión está acotada.

Aclaración: Una sucesión $a_0,a_1, \ldots$ se dice acotada si existe una constante $M$ tal que $a_n<M$ para todo $n$.
Avatar de Usuario
AgusBarreto

OFO - Medalla de Bronce-OFO 2015 OFO - Medalla de Bronce-OFO 2016 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 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022
Mensajes: 157
Registrado: Sab 15 Sep, 2012 6:28 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: San Martín, Buenos Aires

Re: OFO 2019 Problema 5

Mensaje sin leer por AgusBarreto »

Aquí publicaremos la solución oficial
Avatar de Usuario
Turko Arias

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023
Mensajes: 591
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 17
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: OFO 2019 Problema 5

Mensaje sin leer por Turko Arias »

Spoiler: mostrar
Supongamos que existe algún subíndice $i$ tal que $a_i=k^3$ para algún entero positivo $k$, luego $a_{i+1}=3k^3-2f(k^3)=k^3$, luego si $a_{i}$ es un cubo perfecto, la sucesión es constante a partir de ese término, y, en particular, es acotada ya que la sucesión recorre una cantidad finita de valores. Luego, si $a_0$ es cubo perfecto la sucesión es acotada.
Veamos que si $a_0$ no es cubo perfecto la sucesión no es acotada, para eso supongamos ahora que para algún cierto subíndice $i$, $a_i$ no es un cubo perfecto, luego, existen $k$ y $b$ enteros positivos tales que $a_i=k^3+b$ y además $0<b \leq 3k^2+3k$. Tenemos entonces que $a_{i+1}=3a_i-2f(a_i)=3k^3+3b-2k^3=k^3+3b$. Vamos a ver que $a_{i+1}<(k+3)^3$. Tenemos $(k+3)^3=k^3+9k^2+27k+27$, por otro lado $a_{i+1}=k^3+3b \leq k^3+9k^2+9k<k^3+9k^2+27k+27=(k+3)^3$. Por lo que $a_{i+1}=$ "un cubo perfecto+un múltiplo de $3$". Pero por lo visto antes, pueden darse tres cosas:
$1) a_{i+1}=k^3+c$
$2) a_{i+1}=(k+1)^3+c$
$3) a_{i+1}=(k+2)^3+c$
Siendo $k^3$, $(k+1)^3$ y $(k+2)^3$ respectivamente en cada caso los mayores cubos perfectos menores o iguales que $a_{i+1}$ y $c$ "lo que sobra". Vamos a ver que siempre sucede que $c\neq 0$. Supongamos que $a_{i+1}=q^3$ para algún entero positivo $q$, luego, como $a_{i+1}=k^3+3b$ tenemos que $q^3 \equiv k^3(3)$, pero por otro lado $q^3 \equiv q(3)$ y $k^3 \equiv k(3)$, con lo que $q \equiv k(3)$, pero además claramente $q>k$, luego $q\geq k+3$ con lo que $q^3 \geq (k+3)^3$, pero habíamos probado que $a_{i+1}<(k+3)^3$, absurdo, luego es imposible que $a_{i+1}$ sea un cubo perfecto, y por ende siempre se cumple que $c\neq 0$. De este modo probamos que si en algún momento de la sucesión nos topamos con algún término que no es un cubo perfecto, entonces el siguiente tampoco lo será, iterando este razonamiento llegamos a que si un término no es cubo perfecto, todos los que le siguen no lo serán, en particular, si $a_0$ no es cubo perfecto, ningún elemento de la sucesión lo será, y por ende no estará acotada.
1  
Fundamentalista del Aire Acondicionado

Y todo el orgullo de ser bien bilardista
Avatar de Usuario
enigma1234

OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 OFO - Medalla de Oro-OFO 2024
Mensajes: 211
Registrado: Sab 03 Jun, 2017 8:07 pm
Medallas: 5
Nivel: Exolímpico

Re: OFO 2019 Problema 5

Mensaje sin leer por enigma1234 »

Spoiler: mostrar
Caso 1: $a$ es un cubo perfecto
Entonces $f(a)=a$ y entonces la sucesion es constante,es decir es acotada.
Caso 2: $a$ no es un cubo perfecto
Supongamos que existe $a_n$ que es un cubo perfecto entonces sea $m$ el menor tal que $a_m$ es un cubo perfecto entonces $a_{m-1}$ no es un cubo perfecto, sea $x$ tal que $x^3<a_{m-1}<{(x+1)}^3$, si $a_{m-1}=x^3+y$ entonces $a_m=x^3+3y>x^3$ y al ser $a_m$ un cubo mayor que $x^3$ y congruente en modulo 3 con este entonces:
$$a_m=x^3+3y\geq (x+3)^3\to 3y\geq 9x^2+27x+27\to y\geq 3x^2+9x+9$$
Pero como:

$x^3+y=a_{m-1}<{(x+1)}^3 \to y<3x^2+3x+1$.
Lo que es una contradiccion. Entonces ningun $a_n$ es un cubo perfecto entonces tenemos que $a_n>f(a_n)$ entonces $a_n$ es estrictamente creciente, esto es no acotada.
Por lo tanto los únicos $a$ que cumplen son los cubos prefectos
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 FOFO 11 años - Medalla-FOFO 11 años OFO - Medalla de Plata-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 280
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 11
Nivel: 3

Re: OFO 2019 Problema 5

Mensaje sin leer por Sandy »

Spoiler: mostrar

Veamos primero que si se puede llegar a cualquier $a_n=k^3$ con $k$ natural la sucesión será acotada, ya que $f(k^3)=k^3$, entonces $a_{n+1}=3a_n-2f(a_n)=3k^3-2k^3=k^3$, por lo que $a_n=a_{n+1}$, y todos los términos a partir de $a_n$ serán iguales a $a_n$, por lo que la sucesión será acotada. Notemos también que si nunca alcanza a un cubo perfecto, la sucesión será no acotada, ya que, si $a_n\neq k^3$, entonces $f(a_n)<a_n$, entonces $3a_n-2f(a_n)>3a_n-2a_n \Rightarrow a_{n+1}>a_n$, y como es una sucesión de enteros, aumentará siempre en mínimo 1, por lo que, de nunca darse que $a_n$ sea cubo perfecto, la sucesión será no acotada.
Ahora entonces sabemos que si $a=k^3$, la sucesión será acotada. Veamos entonces el caso si en la sucesión hay algún $a_n$ que no sea un cubo perfecto.
Como $a_n$ no es cubo perfecto, diremos que $f(a_n)=k^3<a_n$.
$k^3<a_n<(k+1)^3$
Entonces $3k^3-2k^3<3a_n-2k^3<3(k+1)^3-2k^3$
$k^3<a_{n+1}<3k^3+9k^2+9k+3-2k^3$
$k^3<a_{n+1}<k^3+9k^2+9k+3$
Pero notemos que $(k+3)^3=k^3+9k^2+27k+27> k^3+9k^2+9k+3$ (ya que para todo $k>0$, $27k+27>9k+3$ )
Entonces tenemos que:
$k^3<a_{n+1}<k^3+9k^2+9k+3<(k+3)^3$
Por lo que, de ser $a_{n+1}$ un cubo perfecto, podrá ser solamente $(k+1)^3$ o $(k+2)^3$, ya que se encuentra entre $k^3$ y $(k+3)^3$.
Veamos los dos casos:
a) $3a_n-2k^3=(k+1)^3$
$3a_n=k^3+3k^2+3k+1+2k^3$
$3a_n=3k^3+3k^2+3k+1$
$3a_n=3(k^3+k^2+k)+1$
Pero esto es un absurdo, ya que, mirando congruencia módulo $3$, tenemos que el miembro izquierdo es congruente a $0$, mientras que el derecho es congruente a $1$.

b) $3a_n-2k^3=(k+2)^3$
$3a_n=k^3+6k^2+12k+8+2k^3$
$3a_n=3k^3+6k^2+12k+8$
$3a_n=3(k^3+2k^2+4k)+8$
Pero llegamos nuevamente a un absurdo, ya que, mirando congruencia módulo $3$ de nuevo, tenemos que el miembro izquierdo es congruente a $0$, mientras que el derecho es congruente a $2$.

Por lo tanto, queda probado que, si $a_n$ no es un cubo perfecto, $a_{n+1}$ tampoco lo será, por lo que, si $a$ no es un cubo perfecto, la sucesión será estrictamente creciente, con $a_{n+1}-a_n \geq 1$, por lo que, para que la sucesión sea acotada, $a$ tiene que ser un cubo perfecto.
Fallo inapelable.
Avatar de Usuario
nico ferres

OFO - Medalla de Plata-OFO 2019 OFO - Mención-OFO 2021
Mensajes: 8
Registrado: Mié 23 Abr, 2014 11:24 am
Medallas: 2
Nivel: Exolímpico
Ubicación: Entre Rosario y Capital

Re: OFO 2019 Problema 5

Mensaje sin leer por nico ferres »

Spoiler: mostrar
Para comenzar escribimos $a = k^3 + r$ , con $0\leq r< (k+1)^3-k^3 = 3k^2+3k+1$

Es claro que $f(a) = k^3$

Si $r = 0$, entonces $a_n = a$, $\forall n \in \mathbb{N_0}$ , ya que $a_0 = a$.
Supongamos que para $k \in \mathbb{N_0}$, se cumple que $a_k = a$, entonces $a_{k+1} = 3a_k - 2f(a_k) = 3(k^3)-2k^3 = k^3 = a$.
Luego por el principio de induccion, se cumple que $a_n = a$, $\forall n \in \mathbb{N_0}$.

Entonces si $a$ es un cubo perfecto, la sucesion de $a_n$ esta acotada por $M = a+1$.

Probaremos que si $a$ no es un cubo perfecto ( $r>0$ ), entonces la sucesión es estrictamente creciente, y como esta en los enteros, no estaria acotada.

Separemos en dos casos:

Primer caso: $\boxed{ f(a_{n+1}) = f(a_n)}$

Tenemos que $a_{n+1} = 3a_n - 2f(a_n) = 3(k^3+r) - 2k^3 = k^3 +3r > k^3+r = a_n$
(Notemos que $f(a_{n+k}) = f(a_n) = k^3$ siempre que $3^k * r < 3k^2+3k+1$ , ya que sino, $f(a_{n+k}) \geq (k+1)^3$

Entonces mientras eso suceda, la sucesion sera de la forma $k^3+r , k^3+3r , \ldots , k^3+3^l *r $.
En estos casos, como la sucesion es creciente, no hay problema.

Segundo caso: $\boxed { f(a_{n+1})> f(a_n) = k^3 } $

Primero veamos que $f(a_{n+1}) < (k+3)^3$

Para eso, notemos que $a_{n+1} = 3a_n - 2f(a_n) = k^3+3r < k^3 + 3(3k^2+3k+1) = k^3 + 9k^2+9k+3 < k^3+9k^2+27k+27 = (k+3)^3$

Luego $f(a_{n+1}) = (k+j)^3$ con $j = 1,2$

Se sabe que $a_{n} = k^3+3r \geq f(a_{n})$, por lo tanto $a_{n+1} = 3a_n - f(a_n) = a_n +2(a_n-f(a_n))> a_n$
(ya que $r>0$, por ende $a_n>f(a_n)$)

Solo queda probar que la solucion nunca arriba a un cubo. (es decir, que nunca pasa que $a_{n+1} = a_n$)

Para eso, suponemos que $a_{n+1} = k^3+3r = (k+j)^3$ con $j = 1,2$

Pero entonces $k^3 + 3r = k^3 +3k^2j+3j^2k+j^3$ y
$j^3 = 3(r-k^2j-kj^2)$, lo cual es imposible porque $3$ no divide a $j$.

Con esto hemos probado que la sucesion esta acotada por $M=a+1$ si $a$ es un cubo perfecto, o es estrictamente creciente si no lo es (y como estamos en naturales) no estaria acotada.
Legalmente puedo manejar una cosechadora
Avatar de Usuario
Violeta

OFO - Mención-OFO 2017 FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019
Mensajes: 405
Registrado: Sab 04 Jun, 2016 11:50 pm
Medallas: 5
Ubicación: Puerto Rico

Re: OFO 2019 Problema 5

Mensaje sin leer por Violeta »

enigma1234 escribió: Lun 28 Ene, 2019 9:29 am
Spoiler: mostrar
Caso 1: $a$ es un cubo perfecto
Entonces $f(a)=a$ y entonces la sucesion es constante,es decir es acotada.
Caso 2: $a$ no es un cubo perfecto
Supongamos que existe $a_n$ que es un cubo perfecto entonces sea $m$ el menor tal que $a_m$ es un cubo perfecto entonces $a_{m-1}$ no es un cubo perfecto, sea $x$ tal que $x^3<a_{m-1}<{(x+1)}^3$, si $a_{m-1}=x^3+y$ entonces $a_m=x^3+3y>x^3$ y al ser $a_m$ un cubo mayor que $x^3$ y congruente en modulo 3 con este entonces:
$$a_m=x^3+3y\geq (x+3)^3\to 3y\geq 9x^2+27x+27\to y\geq 3x^2+9x+9$$
Pero como:

$x^3+y=a_{m-1}<{(x+1)}^3 \to y<3x^2+3x+1$.
Lo que es una contradiccion. Entonces ningun $a_n$ es un cubo perfecto entonces tenemos que $a_n>f(a_n)$ entonces $a_n$ es estrictamente creciente, esto es no acotada.
Por lo tanto los únicos $a$ que cumplen son los cubos prefectos
Efectivamemte escribimos la misma solución :D
1  
Para todo [math], existen [math] primos en sucesión aritmética.
Responder