Nacional 2022 - Nivel 3 - Problema 2

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

OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Mención-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 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
OFO - Jurado-OFO 2023 OFO - Jurado-OFO 2024
Mensajes: 381
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 17
Nivel: Exolímpico

Nacional 2022 - Nivel 3 - Problema 2

Mensaje sin leer por Monazo »

Determinar todos los números enteros positivos $n$ para los que se pueden escribir en algún orden los $n$ números enteros entre $1$ y $n$ inclusive, digamos $x_1,x_2,\ldots ,x_n$, con la propiedad de que el número $x_1+x_2+\ldots +x_k$ sea divisible por $k$, para todo $1\leq k\leq n$. Es decir, que
$1$ divide a $x_1$, $2$ divide a $x_1+x_2$, $3$ divide a $x_1+x_2+x_3$,
y así siguiendo hasta que $n$ divide a $x_1+x_2+\ldots +x_n$.
Soy una Estufa en Piloto
:shock:
Avatar de Usuario
Fran2001

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años FOFO 9 años - Medalla Especial-FOFO 9 años
Mensajes: 68
Registrado: Mié 29 Mar, 2017 11:09 am
Medallas: 4
Nivel: Exolímpico
Ubicación: Rosario

Re: Nacional 2022 - Nivel 3 - Problema 2

Mensaje sin leer por Fran2001 »

Spoiler: mostrar
Notemos primero que $n = 1$ y $n = 3$ son solución.
Veamos ahora que son las únicas.
Para empezar, veamos que $n$ no puede ser par, ya que la última condición nos dice que $\frac{1+2+\ldots + n}{n} = \frac{n(n+1)}{2n} = \frac{n+1}{2}$ es entero.

Si $n$ es impar y mayor a $3$, podemos escribirlo como $n=2k+1$ para $k\geq 2$. Lo que vamos a ver es que en estos casos, para cumplir la condición del enunciado es necesario que $x_{n-1} = x_n$.

Lema: $|k+1-x_i| < n-2$ para todo $i$.
Spoiler: mostrar
Primero notemos que $2\leq k\Rightarrow 3\leq k+1\leq 2k-1 = n-2.$ Además $1\leq x_i\leq n$.
Luego resulta que $k+1-x_i\leq n-2-1 = n-3< n-2$.
Además $x_i-(k+1)\leq n-3 < n-2$.
Con esto concluimos que $|k+1-x_i| < n-2$, como queríamos.
Ahora miremos la penúltima suma módulo $n-1$. Tenemos que $$\begin{align}
k+1 - x_n
&\equiv n(k+1) - x_n \\
&= \frac{n(n+1)}2 - x_n \\
&= x_1+x_2+\ldots + x_{n-1} + x_n - x_n \\
&= x_1+x_2+\ldots + x_{n-1} \\
&\equiv 0 \pmod{n-1}.
\end{align}$$ Es decir, $n-1|k+1-x_n$, y por el lema resulta $x_n = k+1$.

Además, mirando módulo $n-2$ resulta $$\begin{align}
k+1 - x_{n-1}
&\equiv (n-1)(k+1) - x_{n-1} \\
&= n(k+1) - (k+1) - x_{n-1} \\
&= \frac{n(n+1)}2 - x_n - x_{n-1} \\
&= x_1+x_2+\ldots + x_{n-2} + x_{n-1} + x_n - x_n - x_{n-1} \\
&= x_1+x_2+\ldots + x_{n-2} \\
&\equiv 0 \pmod{n-2}.
\end{align}$$ Es decir, $n-2|k+1-x_{n-1}$, y por el lema resulta $x_{n-1} = k+1 = x_n$, lo que es absurdo.
Ya le rimo la respuesta // que de la duda nos saca // el animal que usted dice // tiene por nombre la vaca
https://www.youtube.com/watch?v=7ydlVCj94x4
Responder