OFO 2022 Problema 11

Problemas que aparecen en el Archivo de Enunciados.
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

OFO 2022 Problema 11

Mensaje sin leer por Turko Arias »

Hallar todos los enteros positivos $n$ tales que dentro de cualquier conjunto de $n$ reales positivos $a_1,\ldots ,a_n$ que cumple que $\max (a_1,\ldots ,a_n)\leq n\cdot \min (a_1,\ldots ,a_n)$, siempre es posible elegir tres que sean los lados de un triángulo acutángulo.

Aclaración: $\max (a_1,\ldots ,a_n)$ denota al máximo número entre $a_1,\ldots ,a_n$ y $\min (a_1,\ldots ,a_n)$ denota al mínimo.
Fundamentalista del Aire Acondicionado

Y todo el orgullo de ser bien bilardista
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 2022 Problema 11

Mensaje sin leer por Turko Arias »

Aquí publicaremos la solución oficial.
Fundamentalista del Aire Acondicionado

Y todo el orgullo de ser bien bilardista
sebach

Colaborador-Varias OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Bronce-OFO 2020 OFO - Medalla de Plata-OFO 2021
OFO - Medalla de Plata-OFO 2022 OFO - Medalla de Plata-OFO 2023 OFO - Medalla de Oro-OFO 2024
Mensajes: 202
Registrado: Dom 06 Mar, 2011 11:49 am
Medallas: 8
Nivel: Exolímpico

Re: OFO 2022 Problema 11

Mensaje sin leer por sebach »

Spoiler: mostrar
Primero veamos qué significa que tres valores formen un triángulo acutángulo.

El teorema del coseno dice que en todo triángulo de lados $a, b, c$ con $C$ el ángulo opuesto al lado $c$, se cumple que $c^2 = a^2 + b^2 - 2*a*b*cos(C)$.
Ahora bien, definiendo al $cos$ de un ángulo agudo como, en un triángulo rectángulo, el valor del lado adyacente al ángulo dividido la hipotenusa, se puede ver que el coseno es positivo. También podríamos verlo a partir de la circunferencia unitaria, siendo $cos$ la primera coordenada del primer cuadrante. O viendo ya pulida la curva de la función coseno, que sale de ahí.

Entonces, como $a, b, c$ son valores positivos, el hecho de que $C$ sea agudo indica que debe ocurrir que $c^2 < a^2 + b^2$ necesariamente.$(1)$
Y si el triángulo es acutángulo, todos los ángulos son agudos, por lo que en particular esto se deberá cumplir para $c$ el valor del lado más grande (las otras dos desigualdades son irrelevantes).
Esta condición, además, es suficiente: Si un lado cumple esta última desigualdad $(1)$, el ángulo que se formará opuesto a él será agudo, ya que $cos$ de un ángulo obtuso (menor a $180$) es negativo, y en un triángulo rectángulo tenemos la igualdad, como dijo Pitágoras.
Como la desigualdad $c^2 < a^2 + b^2 < a^2 + b^2 + 2ab = (a+b)^2$ implica la desigualdad triangular $c < a + b$, tenemos que si el lado mayor $c$ cumple con $(1)$ entonces se podrá formar un triángulo, y será acutángulo.

A partir de ahora, el problema se reduce a encontrar los valores de $n$ tales que en conjuntos que cumplen lo dado, siempre existen valores $a_i, a_j, a_k$ tales que se cumple $(1)$.

Como las funciones $max$ y $min$ son simétricas respecto del orden, pensemos a nuestro conjunto como ya ordenado, es decir, $a_1 \leq a_2 \leq … \leq a_n$.

Entonces, debemos encontrar los valores de $n$ tales que si $a_n \leq n*a_1$, entonces puedo encontrar valores que cumplan con $(1)$.

Voy a empezar buscando una condición necesaria para que en un conjunto NO se puedan encontrar valores que cumplan con $(1)$.
Supongamos que tengo $a_1$ y $a_2 \geq a_1$.
Luego, para que $a_1, a_2, a_3$ no cumplan con el enunciado, debe ocurrir que $a_3^2 \geq a_2^2 + a_1^2$.
Para que $a_2, a_3, a_4$ no cumplan con el enunciado, debe ocurrir que $a_4^2 \geq a_3^2 + a_2^2$. Veamos que cualquier terna con $a_4$ como el más grande nos daría una desigualdad que ya está implicada por esta última, ya que $a_3$ y $a_2$ son los más grandes de los primeros.
De la misma forma, $a_5^2 \geq a_4^2 + a_3^2$ (e igual que antes y como seguirá ocurriendo, sólo basta con mirar la desigualdad usando los dos lados más grandes previos al último que estamos mirando).
Así sucesivamente, $a_i^2 \geq a_{i-1}^2 + a_{i-2}^2$ para todo $i > 2$ es una condición necesaria para que en este conjunto no se pueda elegir una terna que formen un triángulo acutángulo.
Es decir, si alguna de ellas no se cumple, listo, tenemos la terna.
Además, es suficiente! Por lo que dijimos antes, si todas se cumplen no podemos encontrar tres valores que formen un acutángulo, ni siquiera entre valores que no estén consecutivos en la secuencia ordenada.

Entonces, para resumir, un conjunto contiene un triángulo acutángulo si y sólo si, al ordenarlo, alguna de las desigualdades se rompe.

Para que todas las desigualdades valgan, debe ocurrir que:
$a_3^2 \geq a_2^2 + a_1^2 \geq 2a_1^2$
$a_4^2 \geq a_3^2 + a_2^2 \geq 3a_1^2$
$a_5^2 \geq a_4^2 + a_3^2 \geq 5a_1^2$
$a_6^2 \geq a_5^2 + a_4^2 \geq 8a_1^2$
!!!!

Se puede ver por inducción que obtenemos que $a_i^2 \geq F_{i}a_1^2$, donde $F_1=1, F_2=1, F_i=F_{i-1}+F_{i-2}$ es la sucesión de Fibonacci.
Para $i=1, 2$ se ve trivialmente y del orden, y luego si se cumple para los $j<i$ se tiene que
$$a_{i}^2 \geq a_{i-1}^2 + a_{i-2}^2 \geq (F_{i-1}a_1^2) + (F_{i-2}a_1^2) = F_{i}a_1^2$$

Entonces en particular, si se cumplen todas las desigualdades, se cumple que $a_n^2 \geq F_na_1^2$

Ahora cabe mencionar que esta es una condición necesaria, ya no suficiente, dado que estamos viendo una única desigualdad y en el medio podría pasar que se rompan las desigualdades.
Es decir, yo puedo tener por ejemplo $a_1=1, a_2=2, a_5 = F_{5}a_1^2 = 5$, que cumple la desigualdad, pero en el medio tener por ejemplo $a_3=2$ que hace que exista un triángulo acutángulo con los primeros tres valores, rompiendo la desigualdad $a_3^2 \geq a_{2}^2 + a_{1}^2$.

Entonces, algo importante que sabemos hasta acá es que para que un conjunto de $n$ NO tenga valores que forman un acutńauglo, DEBE necesariamente ocurrir que $a_i^2 \geq F_{i}a_1^2$ para todo $1 < i \leq n$.

Veamos que $k > 12 \Rightarrow F_k > k^2$.
$F_{13} = 233 > 13^2$
$F_{14} = 377 > 14^2$
Ahora, si se cumple para dos valores consecutivos $k, k+1$, se tiene que:
$$F_{k+2} = F_{k+1} + F_{k} \geq (k+1)^2 + k^2 = k^2 + 2k + 1 + k^2 = 2k^2 + 2k + 1$$

Como $k > 12$, $k^2 = k*k > 12k > 11k + 12$, por lo que $2k^2 + 2k + 1 > k^2 + (11k+12) + 2k + 1 > k^2 + 4k + 4 = (k+2)^2$.
Demostramos entonces que $k > 12 \Rightarrow F_k > k^2$.

Por lo tanto, si $n > 12$, si tengo un conjunto que cumple con lo que pide el enunciado, es decir, $a_n \leq n*a_1$, ocurrirá que $a_n^2 \leq n^2a_1^2 < F_na_1^2$, por lo que la condición mencionada antes, que es necesaria para que NO haya un triángulo acutángulo, no se cumple.
Esto significa que todos los $n > 12$ cumple el enunciado, es decir podemos garantizar que en absolutamente cualquier conjunto de reales positivos que cumplan la desigualdad del enunciado, podremos encontrar una terna que forme un triángulo acutángulo.

Ahora hay que ver qué pasa con los $n \leq 12$.

Si miramos la sucesión $a_1=1, a_2=1, a_i = \sqrt{a_{i-1}^2 + a_{i-2}^2}$ para todo $i > 2$, tenemos que la sucesión queda $\sqrt{1}, \sqrt{1}, \sqrt{2}, \sqrt{3}, \sqrt{5}, \sqrt{8}, \sqrt{13}, \sqrt{21}, \sqrt{34}, \sqrt{55}, \sqrt{89}, \sqrt{144}$.
Se puede ver que está ordenada, y que para todo $k$ se cumple que $a_k \leq k*a_1 = k$.
Por lo tanto, tomar como conjunto de $n$ los primeros $n$ valores de esta sucesión generan un conjunto como los del enunciado.
Además, vemos que de esta forma, se cumplen todas las desigualdades $a_i^2 \geq a_{i-1}^2 + a_{i-2}^2$. Más específicamente es una igualdad, por lo que tomando tres valores consecutivos del conjunto generamos un triángulo rectángulo, y tomando tres valores no-consecutivos, por lo explicado antes, se formará un triángulo obtusángulo.

Entonces para todo $n \leq 12$ encontramos conjuntos que cumple la desigualdad del max/min pero donde NO se pueden elegir valores que formen un acutángulo.

Los valores $n$ que cumple con el enunciado son los ${n > 12}$.
Responder