Olimpiadas de Matemáticas
Página de preparación y problemas

Dado un entero positivo $n$, diremos que una sucesión $a_1,a_2,\ldots,a_k$ de enteros positivos, con $k\geq n$, es universal si podemos encontrar cualquier permutación de los números del $1$ al $n$ sin más que eliminar algunos términos de la sucesión. Por ejemplo, $1,2,3,1,2,1,3$ es universal para $n=3$, mientras que $1,2,3,2,1,3,1$ no lo es porque no se puede encontrar la permutación $3,1,2$ (en este orden).

1. Dar un ejemplo de sucesión universal de $n^2$ elementos.
2. Dar un ejemplo de sucesión universal de $n^2-n+1$ elementos.
3. Demostrar que cualquier sucesión universal contiene al menos $\frac{n(n+1)}{2}$ elementos.
4. Demostrar que la sucesión universal más corta para $n=4$ contiene $12$ elementos.

Nota. En el problema original también se proponía encontrar la longitud óptima de la sucesión universal para todo $n$. Este se daba como un problema abierto y se indicaba que la mejor cota superior encontrada por el comité organizador de la olimpiada es $n^2-2n+4$ elementos.