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.
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$
