Nacional 2023 N3 P5

[Uriel J]

Sea $n$ un entero positivo. Beto escribe en el pizarrón una lista de $n$ enteros no negativos. Luego él realiza una sucesión de movidas (de dos pasos) del siguiente tipo:
Primero para cada $i = 1,2,...,n$, él cuenta cuántos números del pizarrón son menores o iguales que $i$.
Sea $a_i$ el número obtenido para cada $i = 1,2,...,n$.
A continuación, borra todos los números del pizarrón y escribe los números $a_1, a_2,...,a_n$.
Por ejemplo, si $n = 5$ y los números iniciales del pizarrón son $0, 7, 2, 6, 2$, al cabo de la primera movida los números del pizarrón serán $1, 3, 3, 3, 3;$ después de la segunda movida serán $1, 1, 5, 5, 5$, y así siguiendo.
$a)$ Demostrar que, para todo $n$ y para toda configuración inicial, llegará un momento a partir del cual los números ya no se modificaran más al utilizar esta movida.
$b)$ Hallar (en función de $n$) el mínimo valor de $k$ tal que, para toda configuración inicial, las movidas realizadas a partir de la movida número $k$ no cambiarán los números del pizarrón.

[fran :)]

Spoiler: mostrar

Voy a interpretar el enunciado como: $k$ es la cantidad de movimientos que se necesita para llegar a un pizarrón que nunca cambia.

Si el enunciado se interpreta como: El movimiento número $k$ no cambia el estado del pizarrón, entonces el resultado es el mismo que con la interpretación anterior, pero con $k' = k + 1$

Representaremos al pizarrón de esta manera:
$
\overset{n}{\overbrace{
\begin{pmatrix} a_0 & a_1 & a_2 & ... & a_n \end{pmatrix}
}}
$
Llamaremos a los estados del pizarrón $P_0, P_1, P_2, ..., P_k$

Veamos que sucede con el pizarrón del ejemplo:

Spoiler: mostrar

$\begin{pmatrix} 0 & 7 & 2 & 6 & 2 \end{pmatrix}$
$\begin{pmatrix} 1 & 3 & 3 & 3 & 3 \end{pmatrix}$
$\begin{pmatrix} 1 & 1 & 5 & 5 & 5 \end{pmatrix}$
$\begin{pmatrix} 2 & 2 & 2 & 2 & 5 \end{pmatrix}$
$\begin{pmatrix} 0 & 4 & 4 & 4 & 5 \end{pmatrix}$
$\begin{pmatrix} 1 & 1 & 1 & 4 & 5 \end{pmatrix}$
$\begin{pmatrix} 3 & 3 & 3 & 4 & 5 \end{pmatrix}$
$\begin{pmatrix} 0 & 0 & 3 & 4 & 5 \end{pmatrix}$
$\begin{pmatrix} 2 & 2 & 3 & 4 & 5 \end{pmatrix}$
$\begin{pmatrix} 0 & 2 & 3 & 4 & 5 \end{pmatrix}$
$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \end{pmatrix}$
$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \end{pmatrix}$
Si observamos atentamente el final del pizarrón, cuando $a_i = i$, nunca más cambia. Esto, además, sucede inevitablemente luego de 2 movimientos. Vamos a intentar formalizar esto y usarlo para la demostración.

Lema 1: Desde $P_1$ para adelante, para todo $i$, $a_i \leq n$. Demostración:

Spoiler: mostrar

En $P_{p+1}$ cada $a_i$ cuenta la cantidad de enteros menores en $P_p$ menores o iguales a $i$. Hay $n$ enteros en $P_p$, entonces en $P_{p+1}$, $a_i \leq n$

Lema 2: Desde $P_2$ para adelante, $a_n = n$. Demostración:

Spoiler: mostrar

En $P_{p+1}$, $a_n$ cuenta la cantidad de enteros menores en $P_p$ menores o iguales a $n$. Por el lema $n$, esto se cumple para los $n$ números del pizarrón cuando $p \geq 1$, entonces cuando $p + 1 \geq 2$, $a_n = n$

Lema 3: Cuando $a_n = n$, el subpizarrón formado por todos los $a_i$ excepto $n$ se comporta como un pizarrón independiente sin $a_n$. Expresado de otra manera: Si borramos $a_n$ cuando $a_n = n$, el comportamiento de los otros números no cambia.

Spoiler: mostrar

En el subpizarrón, todos los $a_i$ con $i < n$ todos cuentan números menores a $n$. Entonces, nunca cuentan a $a_n$.
En el pizarrón independiente, ninguno de los $a_i$ cuenta a $a_n$, porque $a_n$ no está.
Entonces, ambos casos tratan a $a_n$ de la misma manera: lo ignoran.
Los demás $a_i$ son iguales en el subpizarrón y el pizarrón independiente.

Como la única diferencia entre un pizarrón independiente sin $a_n$ y el subpizarrón es $a_n$, entonces ambos se comportarán de la misma manera.

Lema 4: Para todo $n$, con $2n$ movimientos se llega a un estado estable
Demostración:

Spoiler: mostrar

Lo voy a demostrar por inducción:
Hipótesis inductiva: Con $m$ números en el pizarrón, con $2m$ movimientos se llega a un estado estable
Caso base: $m = 1$.

Spoiler: mostrar

Por el Lema 2, desde $P_2$ para adelante, $a_1 = 1$. Este es el único número del pizarrón, y nunca cambiará. $2 = 2m$ entonces queda probado el caso base.

Paso inductivo: $m + 1$

Spoiler: mostrar

La hipótesis inductiva nos dice que con $m$ números en el pizarrón alcanza con $2m$ movidas para llegar a un pizarrón estable.

Por el Lema 2, desde $P_2$ para adelante, $a_{m+1} = m + 1$.
Por el Lema 3, una vez que tenemos un pizarrón así, el resto del pizarrón actúa como un pizarrón independiente, entonces la hipótesis inductiva aplica para éste.
$
\overset{m+1}{\overbrace{
\begin{pmatrix} a_0 & a_1 & a_2 & ... & a_m & a_{m+1} \end{pmatrix}
}}
$
Con 2 movimientos:
$
\overset{m+1}{\overbrace{
\begin{pmatrix} a_0 & a_1 & a_2 & ... & a_m & m + 1 \end{pmatrix}
}}
$
Usando el Lema 3:
$
\overset{m}{\overbrace{
\begin{pmatrix} a_0 & a_1 & a_2 & ... & a_m \end{pmatrix}
}} \begin{pmatrix} m + 1 \end{pmatrix}
$
Con la hipótesis inductiva, luego de $2m$ movimientos:
$
\overset{m}{\overbrace{
\begin{pmatrix} \text{<pizarrón estable>} \end{pmatrix}
}} \overset{1}{\overbrace{\begin{pmatrix} \text{<pizarrón estable>} \end{pmatrix}}}
$
Entonces, con $2m + 2 = 2(m+1)$ movimientos alcanza para llegar a un pizarrón estable.

Lema 5: Para todo $n$, existe un pizarrón que necesita $2n$ movidas para estabilizarse.

Spoiler: mostrar

Este pizarrón es $
\overset{n}{\overbrace{
\begin{pmatrix} n + 1 & n + 1 & n + 1 & ... & n + 1 \end{pmatrix}
}}
$
Voy a probar que necesita $2n$ movidas por inducción en todos los naturales $< n + 1$.
Hipótesis: Un pizarrón de este formato necesita $2n$ movidas para estabilizarse.
Caso base: $m = 1$

Spoiler: mostrar

$\begin{pmatrix} 2 \end{pmatrix}$
Como $2 > 1$, luego de 1 movimiento.
$\begin{pmatrix} 0 \end{pmatrix}$
Luego de otro movimiento, como $0 \leq 1$
$\begin{pmatrix} 1 \end{pmatrix}$, que es estable por el Lema 4.

Paso inductivo: $m + 1$

Spoiler: mostrar

$\overset{m+1}{\overbrace{
\begin{pmatrix} n + 1 & n + 1 & n + 1 & ... & n + 1 \end{pmatrix}
}}$
Como $n + 1 > m + 1 \geq i$, luego de 1 movimiento.
$\overset{m+1}{\overbrace{
\begin{pmatrix} 0 & 0 & 0 & ... & 0 \end{pmatrix}
}}$
Como los $m + 1$ números en el pizarrón son $\leq m + 1$, luego de otro movimiento.
$\overset{m+1}{\overbrace{
\begin{pmatrix} m + 1 & m + 1 & m + 1& ... & m + 1 \end{pmatrix}
}}$
Usando el Lema 3, como $a_{m+1} = m_1$:
$
\overset{m}{\overbrace{
\begin{pmatrix} m + 1 & m + 1 & m + 1 & ... & m + 1 \end{pmatrix}
}} \begin{pmatrix} m + 1 \end{pmatrix}
$
El pizarrón que queda en la izquierda es del formato de los que construimos, por lo que cumple con la hipótesis inductiva. Por la hipótesis inductiva necesita $2m$ movimientos para estabilizarse. Entonces, esto necesita $2 + 2m = 2(m+1)$ movimientos para estabilizarse,

Con la combinación de los lemas 4 y 5, probamos a) y b) con $k = 2n$

[Ignacio Daniele]

Spoiler: mostrar

Notemos que tras el primer movimiento, ningún número de la lista será más grande que n (y eso va a pasar siempre, pues solo hay n números), entonces, tras el segundo movimiento, $a_n=n$, por lo que los otros números de la lista no lo contarán a $a_n$, y $a_n=n$ para siempre, pues como dije antes, ningún número superará a n luego de eso. Entonces, es como si quedara una lista nueva de $n-1$ números, un número constante y 2 movidas. Repito ese planteo varias veces, hasta que llego a que en $2n$ movimientos como mucho siempre se llegará a la lista fija, por lo que en $2n+1$, por primera vez es obligatorio que se repita la lista anterior. Un ejemplo que requiere esos $2n$ o $2n+1$ movidas dependiendo la interpretación (si te pide las movidas hasta llegar a la lista estable, o la cantidad de movidas hasta que la lista se repita), sería que todos los números de la lista son $n+1$. Se pasa de todos los números $n+1$, luego todos 0, luego $n$ veces el número $n$. Se repite el proceso varias veces, y se puede ver que en este caso se requieren $2n$ movidas para llegar a la lista constante.
En conclusión, $k=2n(+1)$, pongo el $+1$ entre paréntesis porque es opcional, dependiendo de la interpretación de lo que te pide.