FOFO 11 Años - Problema 5

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

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021
Mensajes: 391
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 9
Nivel: Exolímpico
Ubicación: Ciudad Gotica

FOFO 11 Años - Problema 5

Mensaje sin leer por Joacoini »

Consideramos todas las permutaciones de los números del $1$ al $n$, y las concatenamos todas en orden lexicográfico (de diccionario). Demostrar que si aparecen $n$ números consecutivos cuya suma es $\dfrac{n(n+1)}{2}$ entonces necesariamente son los números del $1$ al $n$ en algún orden.
NO HAY ANÁLISIS.

Avatar de Usuario
Joacoini

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021
Mensajes: 391
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 9
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Re: FOFO 11 Años - Problema 5

Mensaje sin leer por Joacoini »

Aquí publicaremos la solución oficial.
NO HAY ANÁLISIS.

EmRuzak

OFO - Medalla de Plata-OFO 2021
Mensajes: 38
Registrado: Dom 13 Dic, 2020 2:17 am
Medallas: 1
Nivel: 3

Re: FOFO 11 Años - Problema 5

Mensaje sin leer por EmRuzak »

Spoiler: mostrar
Supongamos que tenemos dos permutaciones de $1$ a $n$ consecutivas lexicográficamente, $a_1$, $a_2$... $a_n$ y

$b_1$, $b_2$... $b_n$ la primera menor a la segunda.

Entonces desde $i=0$ hasta $i=k$, $a_i=b_i$, (si $i=0$, $a_1$ es distinto a $b_1$)

$b_{k+1}>a_{k+1}$, ya que de otra forma la secuencia de $a$ sería mayor o igual a la de $b$.


Si es que los números después de $a_{k+1}$ no están ordenados de mayor a menor, al ordenarlos se obtendría una secuencia $x$ mayor a $a$, pero menor a $b$, ya que $x_{k+1}<b_{k+1}$

lo mismo pasa con $b$ pero al ordenarlos de menor a mayor.

Entonces los números que que quedan en $a$ después de $k+1$ (si es que quedan mas de $2$), deben estar ordenados de mayor a menor, y en $b$ de menor a mayor, ya que de otra forma, habría una permutación entre las dos, y $a$, $b$ no serían consecutivas.

Llamamos $S_a(i)$ a la suma de los números desde $a_1$ hasta $a_i$, lo mismo con $S_b(i)$ pero para $b$

Con $i<k+1$ $S_a(i)=S_b(i)$

Llamamos $x=a_{k+1}$, $y=b_{k+1}$, $x<y$

En la permutación $a$, $y$ aparece después de $x$, ya que de lo contrario, $y$ estaría entre la posición $1$ y $k$, pero estos números se comparten con $b$, lo que significa que $y$ aparece dos veces en $b$, contradicción.

Por el mismo argumento, $x$ aparece después de $y$ en la permutación $b$

Entonces $a_{k+2}\geq y$, $b_{k+2}\geq x$.

$S_a(k+2)-S_b(k+2)=x-y+a_{k+2}-b_{k+2}\geq 0$, con igualdad en $a_{k+2}=y$, $b_{k+2}=x$ (*1)

también como a partir de $k+2$, $a$ es descendiente y $b$ creciente, $a_i-b_i$ disminuye, por lo que $S_a(i)-S_b(i)$
no puede ser igual a $0$ con $i<n$, ya que para eso la suma debería disminuir hasta llegar a un número negativo, y después aumentar hasta llegar a $0$, por lo que la diferencia entre dos sumas consecutivas primero sería negativa, y después positiva, contradicción ya que $a_i-b_i$ disminuye.

Entonces el único caso después de $k$ donde $S_a(i)-S_b(i)=0$ es con $i=k+2$ cuando se cumple la igualdad (*1), por lo que en $a$ y $b$ desde $i=1$ hasta $i=k+2$ están los números de $a_1$ hasta $a_k$, y $(x,y)$ en $a$, y $(y,x)$ en $B$.

Entonces si $S_a(i)=S_b(i)$, la lista desde $a_1$ hasta $a_i$, es una permutación de la lista de $b_1$, hasta $b_i$.

Si concatenamos todas las permutaciones en orden lexicográfico, y seleccionamos una subsecuencia de $n$ de largo, va a quedar entre $2$ permutaciones.

va a ser: $a_{i+1}, a_{i+2}... a_n, b_1, b_2, ... b_{i}$ con $i\geq0$, entonces si la suma es $\frac{n(n+1)}{2}$, es decir la suma de los números del $1$ al $n$, $S_a(i)=\frac{n(n+1)}{2}-(\frac{n(n+1)}{2}-S_b(i))=S_b(i)$ entonces los elementos desde $b_1$ hasta $b_i$ son los mismos que desde $a_1$ hasta $a_i$, y los números desde $a_{i+1}$ hasta $a_{n}$ son los números desde $1$ hasta $n$ que faltan en la secuencia de $b_1$ a $b_i$, entonces en:

$a_{i+1}, a_{i+2}... a_n, b_1, b_2, ... b_{i}$ están todos los números del $1$ al $n$

Responder