Soit un entier naturel n. On dit que S(n,k), suite de k nombres entiers naturels (avec k > n), est universelle d’ordre n si on peut obtenir n’importe quelle des n ! permutations des entiers {1,2,….,n} en supprimant k – n de ses termes. Par exemple, la suite de 3 termes (1,2,1) est universelle d’ordre 2 car on peut obtenir les 2 permutations (1,2) et (2,1) en supprimant respectivement le troisième chiffre qui est égal à 1, ce qui donne (1,2,*) et le premier chiffre lui aussi égal à 1, ce qui donne (*,2,1). A l’inverse (1,2,2) ne l’est pas car il est impossible d’obtenir (2,1).
On désigne par L(n) la longueur de la suite universelle d’ordre n la plus courte possible. On a par exemple L(2) = 3.
1) Démontrez que L(3) = 7 et L(4) = 12.
2) A partir de suites universelles S(3,7) et S(4,12) d’ordres 3 et 4 et de longueur minimale, donnez et justifiez un mode de construction de suites universelles d’ordre 5, 6, 7,….n dont la longueur vous paraît minimale.
Pour les plus audacieux et les plus courageux qui ont trouvé une suite universelle de longueur 4 028 052 pour n = 2008, il ne leur reste plus qu’à démontrer que L(2008) = 4 028 052 (difficulté : *******).

Source : d’après Olympiade 1976 de mathématiques en URSS – Problème n°12

 Solution