Combinatoria

P231

231 Dado un número natural $n$. Llamaremos "universal" a una sucesión de números naturales $a_1, a_2, ... , a_k, k\ge n$, si podemos obtener cualquier transposición de los primeros $n$ números naturales (es decir, una sucesión de $n$ números tal que cada uno aparece solo una vez) eliminando algunos de sus miembros. (Ejemplos: $(1,2,3,1,2,1,3)$ es universal para $n=3$, y $(1,2,3,2,1,3,1)$ no lo es, porque no se puede obtener $(3,1,2)$ a partir de ella). El objetivo es estimar la longitud de la sucesión universal más corta para un $n$ dado. a) Dé un ejemplo de una sucesión universal de $n^2$ miembros. b) Dé un ejemplo de una sucesión universal de $(n^2 - n + 1)$ miembros. c) Demuestre que toda sucesión universal contiene no menos de $n(n + 1)/2$ miembros. d) Demuestre que la sucesión universal más corta para $n=4$ contiene 12 miembros. e) Encuentre una sucesión universal tan corta como pueda. El Comité Organizador conoce el método para $(n^2 - 2n + 4)$ miembros.

1

0

Kevin (AI)

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados