EGMO 2020 - P4

[Gianni De Rico]

Una permutación de los enteros $1,2,\ldots ,m$ se llama fresca si no existe ningún entero positivo $k<m$ tal que los primeros $k$ elementos de la permutación son los números $1,2,\ldots ,k$ en algún orden. Sea $f_m$ el número de permutaciones frescas de los enteros $1,2,\ldots ,m$.
Demuestre que $f_n\geq n\cdot f_{n-1}$ para todo $n\geq 3$.

Aclaración: Por ejemplo, para $m=4$ la permutación $(3,1,4,2)$ es fresca, mientras que la permutación $(2,3,1,4)$ no lo es.

[Turko Arias]

Hermoso problema, que viva la combinatoria

Spoiler: mostrar

Para resolver este problema, vamos a tomar una idea prestada de este problema, la idea es que no nos interesa contar cuantas hay, sino simplemente asignarle a cosas del primer grupo, cosas del segundo grupo de manera que a elementos diferentes se le asignen grupos disjuntos. En el problema ese realizamos una inyección.
Acá lo que vamos a hacer es a cada permutación fresca de longitud $n-1$, asignarle $n$ permutaciones frescas de longitud $n$, de manera que si dos conjuntos fueron asignados a permutaciones de longitud $n-1$ distintas, entonces son disjuntos, esto nos va a asegurar que $f_n \geq nf_{n-1}$. La asignación que vamos a hacer es, dada una permutación fresca $( a_1, a_2,...,a_{n-1})$, le asignamos las $n-1$ permutaciones que se obtienen al reemplazar $a_i$ por $n$, para los $i$ entre $1$ y $n-1$ y desplazar todos los números en la permutación un lugar a la derecha. Por último, asignamos la permutación que se obtiene al reemplazar $n-1$ en donde esté, por $n$, y ubicar $n-1$ al final de la permutación. Es claro que las $n$ permutaciones obtenidas son frescas. Por otro lado, consideramos el conjunto $A$ en el que van a estar las $(n-1)f_{n-1}$ permutaciones frescas obtenidas con el primer método. Veamos que todas estas son distintas entre sí, ya que en cada una, si miramos en que orden aparecen los $n-1$ números de $1$ a $n-1$ en todos es distinto si fueron obtenidos a partir de distintas permutaciones frescas de longitud $n-1$, y en caso de que hayan sido obtenidas de la misma permutación, entonces difieren en la posición en la que está ubicado $n$. Sea $B$ el conjunto de las $f_{n-1}$ permutaciones obtenidas con el segundo método. Es fácil ver que la función que manda cada permutación fresca de longitud $n-1$ a una permutación fresca de longitud $n$ de $B$ mediante la segunda operación es una biyección, por lo que todos los elementos de $B$ son distintos. Ahora supongamos que hay un elemento de $B$ que está en $A$ también, como está en $A$, al eliminar $n$ obtenemos la permutación original de la que partimos, pero como está en $B$ también, el último elemento es $n-1$, pero entonces tendríamos una permutación fresca de longitud $n-1$ que termina en $n-1$, lo cual es absurdo. Luego, todos los elementos de $A$ y todos los elementos de $B$ son distintos. Por otro lado, $nf_{n-1}=(n-1)f_{n-1}+f_{n-1}=\#A+\#B \leq f_n$ y estamos $\blacksquare$

[Fran5]

No sé si sea igual que la del Turko, pero en estos tipos de problemas donde te piden mostrar que $nf_{n-1} \leq f_n$ hay una forma muy interesante de proceder

Spoiler: mostrar

Sea $A = a_1, \ldots, a_{n-1}$ una permutación fresca de $[n-1]$. Vamos a construirnos $n$ nuevas permutaciones frescas de $[n]$
Observacion: ninguna permutación fresca de $[n]$ termina en $a_n = n$.

Consideremos, ahora, para cada $1 \leq i \leq n-1$ la permutación $A_i$ dada por $a_1, a_2, \ldots, a_{i-1}, n, a_i, \ldots, a_{n-1}$. (para $i=1$ tenemos que empieza con $n$.

Es facil ver que tenemos $(n-1)f_{n-1}$ nuevas permutaciones frescas $A_i$. Ahora nos falta una mas, y aprovecharemos la observación.

Todas las listas frescas que nos hicimos no terminan en $n$, pero como vienen de frescas de $[n-1]$ tampoco terminan en $n-1$.
Entonces reemplazamos $n$ en el lugar de $n-1$ y ponemos $n-1$ en el final. Voilà

Le dejo al lector el hecho de verificar que las $n$ listas son frescas, y que no hay dos listas frescas de $[n-1]$ que nos den la misma lista fresca de $[n]$