Problema 6 Nivel 2 Río 2019

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

OFO - Medalla de Bronce
Mensajes: 72
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 1
Nivel: 3

Problema 6 Nivel 2 Río 2019

Mensaje sin leer por Sandy » Mar 10 Dic, 2019 1:01 pm

Una sucesión $a_1$, $a_2$, $...$, $a_n$ de $n≥2$ enteros positivos se dice empinada si satisface

$\frac{a_n}{a_{n-1}}≥\frac{a_{n-1}}{a_{n-2}}≥ ... ≥ \frac{a_2}{a_1} > 1$

a) Halle, para cada $n$, una sucesión empinada $a_1$, $a_2$, $...$, $a_n$ con $a_n≤n^2$.
b) Demuestre que si $a_1$, $a_2$, $...$, $a_n$ es empinada entonces $a_n≥\frac{3}{4}n^2-n$.

Avatar de Usuario
Prillo

Colaborador OFO - Jurado
Mensajes: 400
Registrado: Sab 18 Dic, 2010 8:52 pm
Medallas: 2

Re: Problema 6 Nivel 2 Río 2019

Mensaje sin leer por Prillo » Vie 20 Dic, 2019 2:36 am

a)
Spoiler: mostrar
Consideremos la sucesión $a_1,a_2,\dots,a_n$ dada por $a_n = n^2, a_{n-1} = n^2 - (n-1), a_{n-2} = n^2 - (n-1) - (n-2),\dots,a_1 = n^2 - (n - 1) - (n - 2) - \dots - 1$. Es decir, $a_i = n^2 - (n - 1) - (n - 2) - \dots - (n - (n - i)) = \frac{n^2 + n + i(i-1)}{2}$, ó pensado recursivamente, $a_n = n^2$ y $a_i = a_ {i+1} - i$ para cada $1\le i\le n - 1$. Los terminos de esta progresión son trivialmente enteros, y positivos ya que $a_i = \frac{n^2 + n + i(i - 1)}{2} \ge \frac{1 + 1 + 1\cdot 0}{2} > 0$. Veamos que además esta es una sucesión empinada. Tomemos un $2\le i\le n - 1$ y veamos que $\frac{a_{i+1}}{a_i} \ge \frac{a_i}{a_{i-1}}$. Tenemos que
$\frac{a_{i+1}}{a_i} \ge \frac{a_i}{a_{i-1}}$
$\iff \frac{a_i + i}{a_i} \ge \frac{a_i}{a_i - (i-1)}$
$\iff a_i\ge i(i-1)$
$\iff \frac{n^2 + n + i(i-1)}{2} \ge i(i-1)$
$\iff n^2 + n\ge i(i-1)$
que se cumple pues $i(i-1)\le n(n-1) < n(n + 1)= n^2 + n$. Por último, como trivialmente $a_2 > a_1$ entonces se cumple también que $\frac{a_2}{a_1} > 1$, y luego la sucesión dada es una sucesión empinada con $a_n \le n^2$.
b)
Spoiler: mostrar
Sea $a_1,a_2,\dots,a_n$ una sucesión empinada. Primero notemos que $a_n>a_{n-1}>\dots>a_1$. En efecto, es fácil probar que $a_{k+1}>a_k$ para $1 \le k \le n - 1$ por inducción en $k$: esto es claro por la condición del enunciado para $k=1$, y si vale para algún $1\le k\le n-2$, para $k+1$ se tiene por la condición del enunciado que $a_{k+2}\ge a_{k+1}(\frac{a_{k+1}}{a_k})>a_{k+1}$. Ahora, sea $d_k=a_{k+1}-a_k$ para cada $1\le k\le n-1$. Operando con la condición $\frac{a_{k+1}}{a_k}\ge \frac{a_k}{a_{k-1}}$ donde $2\le k\le n-1$ obtenemos que
$\frac{a_{k+1}}{a_k}\ge \frac{a_k}{a_{k-1}}$
$\iff a_{k+1}a_{k-1}\ge a_k^2$
$\iff (a_k+d_k)(a_k-d_{k-1})\ge a_k^2$
$\iff a_k(d_k-d_{k-1})\ge d_kd_{k-1}.\ (1)$
Como la sucesión $(a_i)$ es estrictamente creciente, tenemos que $d_i>0$ para todo $1 \le i \le n - 1$ y de $(1)$ se deduce que $d_k>d_{k-1}$ para todo $2\le k\le n-1$, luego la sucesión $(d_k)$ también es estrictamente creciente, y en particular $d_i\ge i$ para todo $1\le i\le n-1$. De aquí es fácil obtener una cota para $a_n$, pues $a_n=a_1+d_1+d_2+\dots+d_{n-1}\ge 1+(1+2+\dots+(n-1))=\frac{n(n-1)}{2}+1$. Pero podemos hacer mejor. En efecto, como vale $d_k>d_{k-1}$, podemos divir por $d_k-d_{k-1}$ en $(1)$ para obtener
$a_k\ge \frac{d_kd_{k-1}}{d_k-d_{k-1}}.$
Supongamos primero que $d_k-d_{k-1}\ge 2$ para todo $2\le k\le n - 1$. Luego $d_k \ge 2k - 1$ para todo $1\le k\le n - 1$ y asi $a_n=a_1+d_1+d_2+\dots+d_{n-1}\ge 1+(1+3+\dots+(2n-3))=(n-1)^2+1$; como $(n-1)^2+1\ge \frac{3}{4}n^2-n\iff (n-2)^2+4\ge 0$ ya terminamos. Si por el contrario existiera algún $2\le k \le n - 1$ tal que $d_k-d_{k-1}=1$, entre todos estos $k$ consideremos el mayor. Para este $k$ resulta entonces que
$a_k\ge \frac{d_kd_{k-1}}{d_k-d_{k-1}}=d_{k-1}(d_{k-1}+1).$
Por otra parte, por la maximalidad de $k$ tenemos que $d_{k + i + 1} \ge d_{k + i} + 2$ para todo $0 \le i \le n - 2 - k$ y luego $d_{k+i}\ge d_k+2i$ para todo $1 \le i \le n - 1 - k$. Usando que $d_{k-1}\ge k-1$ y que $d_k \ge k$, se sigue que
$a_n=a_k+d_{k}+d_{k+1}+\dots+d_{n-1}$
$\ge d_{k-1}(d_{k-1}+1)+(d_k)+(d_k+2)+\dots+(d_k+2(n-1-k))$
$\ge (k-1)k+(k)+(k+2)+\dots+(k+2(n-1-k))$
$=(k-1)k+k(n-k)+2(1+2+\dots+(n-1-k))$
$=(k-1)k+k(n-k)+(n-k-1)(n-k)$
$=k^2 - k + nk - k^2 + n^2 -nk -nk +k^2 -n + k$
$=n^2-k(n-k)-n=n^2-[\frac{n^2}{4}-(\frac{2k-n}{2})^2]-n\ge n^2-\frac{n^2}{4}-n=\frac{3}{4}n^2-n$,
como queríamos.
Nota:
Spoiler: mostrar
La cota $\frac{3}{4}n^2-n$ es bastante buena, como se ve en este grafico (la curva azul $L(n)$ es el optimo, calculado con una computadora). Tambien, si se cambia la cota por $\frac{3}{4}n^2$ (una cota mas 'linda') el problema es mentira para todo $n \le 40$.
RioN2P6.png
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
1  

Responder