Exercice national 1 — Plus fort ! (tous candidats)

5. \(L_n(0)\) correspond à la liste strictement décroissante (unique), \(L_n(n-1)\) à la liste strictement croissante (unique).

6. Pour construire une liste de longueur \(n+1\) et de score \(k\), insérer la valeur \(n+1\) dans une liste de longueur \(n\) : l'insérer à la toute fin ne change pas le score (le nouveau dernier terme est le plus grand possible, donc crée une nouvelle ascension) sauf si on l'insère en dernière position d'une liste qui se terminait déjà par une ascension... Plus précisément, distinguer selon que \(n+1\) est inséré juste après un « pic » existant (ne change pas le score) ou ailleurs (augmente le score de 1) : cela donne la récurrence générale demandée en 6e, cas particulier de la formule des nombres eulériens.

6f. Ce tableau est exactement le triangle des nombres eulériens \(\left\langle{n\atop k}\right\rangle\), bien connu en combinatoire.

1a. Autre exemple de score 3, longueur 8

On cherche une permutation de \(\{1,2,\dots,8\}\) dont le score (nombre de fois où un terme dépasse le précédent) est exactement 3.

Exemple : \([1, 3, 2, 5, 4, 7, 6, 8]\)

Vérification :

• \(3 > 1\) → +1

• \(2 < 3\) → 0

• \(5 > 2\) → +1

• \(4 < 5\) → 0

• \(7 > 4\) → +1

• \(6 < 7\) → 0

• \(8 > 6\) → +1

Total : 3. ✅

1b. Toutes les listes de longueur 3 et leurs scores

Les permutations de \(\{1,2,3\}\) sont au nombre de \(3! = 6\). On calcule le score pour chacune.

| Liste | Score | Détail |

|-------|-------|--------|

| \([1,2,3]\) | 2 | \(2>1\), \(3>2\) |

| \([1,3,2]\) | 1 | \(3>1\), \(2<3\) |

| \([2,1,3]\) | 1 | \(1<2\), \(3>1\) |

| \([2,3,1]\) | 1 | \(3>2\), \(1<3\) |

| \([3,1,2]\) | 1 | \(1<3\), \(2>1\) |

| \([3,2,1]\) | 0 | \(2<3\), \(1<2\) |

2. Fonction Python calculant le score

```python

def score(liste):

s = 0

for i in range(1, len(liste)):

if liste[i] > liste[i-1]:

s += 1

return s

```

Test avec l'exemple donné : `score([2,5,7,6,1,8,4,3])` renvoie 3.

3. Montrer que le score est toujours entre 0 et \(n-1\) ; donner un exemple pour chaque extrême.

Soit une liste de longueur \(n\). Pour chaque \(i\) de 1 à \(n-1\), on compare \(a_i\) et \(a_{i-1}\). Il y a exactement \(n-1\) comparaisons. Chaque comparaison donne soit 0 soit 1. Donc le score \(s\) vérifie \(0 \le s \le n-1\).

• Score 0 : liste strictement décroissante. Exemple : \([n, n-1, \dots, 1]\).

• Score \(n-1\) : liste strictement croissante. Exemple : \([1, 2, \dots, n]\).

4. Pour \(1 \le k \le n-2\)

a) Montrer qu'une liste de score \(k\) existe

On peut construire une permutation de score exactement \(k\) de la façon suivante :

• Prendre les nombres \(1,2,\dots,k+1\) dans l'ordre croissant : cela donne \(k\) augmentations consécutives.

• Puis placer tous les nombres restants \(k+2, k+3, \dots, n\) dans l'ordre décroissant : cela ne produit aucune augmentation supplémentaire car chaque terme est plus petit que le précédent.

Exemple pour \(n=6\), \(k=3\) : \([1,2,3,4,6,5]\) donne les comparaisons :

\(2>1\), \(3>2\), \(4>3\) (3 augmentations), puis \(6>4\) (1 augmentation de plus → attention, ici on a 4 augmentations, donc il faut ajuster).

Pour éviter une augmentation supplémentaire, on peut placer d'abord les \(k+1\) premiers nombres dans l'ordre croissant, puis le reste dans l'ordre décroissant en commençant par le plus grand : \([1,2,\dots,k+1, n, n-1, \dots, k+2]\).

Vérifions : entre \(k+1\) et \(n\) : \(n > k+1\) → cela donne une augmentation de plus. Donc il faut plutôt prendre les \(k\) premiers nombres croissants, puis un grand, puis les autres décroissants.

Construction correcte :

Soit la liste : \([1,2,\dots,k, n, n-1, \dots, k+1]\).

• Les \(k-1\) premières comparaisons (entre 1 et 2, ..., entre \(k-1\) et \(k\)) donnent \(k-1\) augmentations.

• Comparaison entre \(k\) et \(n\) : \(n > k\) → +1, total \(k\).

• Ensuite, tous les termes suivants sont en ordre décroissant, donc aucune augmentation supplémentaire.

Ainsi, on obtient exactement \(k\) augmentations. Donc une liste de score \(k\) existe.

b) En existe-t-il deux ?

Oui, on peut en construire plusieurs. Par exemple, pour \(n=4\), \(k=1\) :

• \([1,4,3,2]\) donne score 1 (car \(4>1\) seulement)

• \([2,4,3,1]\) donne score 1 (car \(4>2\) seulement)

Donc au moins deux listes distinctes existent.

5. Déterminer \(L_n(0)\) et \(L_n(n-1)\)

• \(L_n(0)\) : score 0 signifie aucune augmentation, donc la liste est strictement décroissante. Il n'y a qu'une seule permutation strictement décroissante : \([n, n-1, \dots, 1]\). Donc \(L_n(0) = 1\).

• \(L_n(n-1)\) : score \(n-1\) signifie que chaque comparaison donne une augmentation, donc la liste est strictement croissante. Une seule possibilité : \([1,2,\dots,n]\). Donc \(L_n(n-1) = 1\).

6a. Déterminer \(L_3(0), L_3(1), L_3(2)\) ; comment insérer 4 dans \([3,1,2]\) pour garder un score de 1 ?

D'après le tableau de la question 1b :

• \(L_3(0) = 1\) (liste \([3,2,1]\))

• \(L_3(1) = 4\) (listes \([1,3,2], [2,1,3], [2,3,1], [3,1,2]\))

• \(L_3(2) = 1\) (liste \([1,2,3]\))

Insertion de 4 dans \([3,1,2]\) pour garder un score de 1 :

Liste initiale : \([3,1,2]\) de score 1 (car \(1<3\) et \(2>1\)).

On insère 4 à différentes positions :

• Avant 3 : \([4,3,1,2]\) → comparaisons : \(3<4\) (0), \(1<3\) (0), \(2>1\) (1) → score 1 ✅

• Entre 3 et 1 : \([3,4,1,2]\) → \(4>3\) (1), \(1<4\) (0), \(2>1\) (1) → score 2 ❌

• Entre 1 et 2 : \([3,1,4,2]\) → \(1<3\) (0), \(4>1\) (1), \(2<4\) (0) → score 1 ✅

• Après 2 : \([3,1,2,4]\) → \(1<3\) (0), \(2>1\) (1), \(4>2\) (1) → score 2 ❌

Donc on peut insérer 4 en première ou troisième position.

6b. Comment insérer 4 dans \([3,2,1]\) pour garder un score nul ?

Liste initiale : \([3,2,1]\) de score 0.

On insère 4 :

• Avant 3 : \([4,3,2,1]\) → \(3<4\) (0), \(2<3\) (0), \(1<2\) (0) → score 0 ✅

• Entre 3 et 2 : \([3,4,2,1]\) → \(4>3\) (1) → score 1 ❌

• Entre 2 et 1 : \([3,2,4,1]\) → \(2<3\) (0), \(4>2\) (1) → score 1 ❌

• Après 1 : \([3,2,1,4]\) → \(2<3\) (0), \(1<2\) (0), \(4>1\) (1) → score 1 ❌

Donc seule la première position convient.

6c. Vérifier \(L_4(1) = 2L_3(1) + 3L_3(0)\)

On calcule \(L_4(1)\) directement : listes de longueur 4 avec exactement 1 augmentation.

Listes possibles (on peut les énumérer) :

• \([4,3,2,1]\) : score 0

• \([4,3,1,2]\) : \(1<3\) (0), \(2>1\) (1) → score 1

• \([4,2,3,1]\) : \(2<4\) (0), \(3>2\) (1), \(1<3\) (0) → score 1

• \([4,2,1,3]\) : \(2<4\) (0), \(1<2\) (0), \(3>1\) (1) → score 1

• \([4,1,3,2]\) : \(1<4\) (0), \(3>1\) (1), \(2<3\) (0) → score 1

• \([4,1,2,3]\) : \(1<4\) (0), \(2>1\) (1), \(3>2\) (1) → score 2

• \([3,4,2,1]\) : \(4>3\) (1), \(2<4\) (0), \(1<2\) (0) → score 1

• \([3,4,1,2]\) : \(4>3\) (1), \(1<4\) (0), \(2>1\) (1) → score 2

• \([3,2,4,1]\) : \(2<3\) (0), \(4>2\) (1), \(1<4\) (0) → score 1

• \([3,2,1,4]\) : \(2<3\) (0), \(1<2\) (0), \(4>1\) (1) → score 1

• \([3,1,4,2]\) : \(1<3\) (0), \(4>1\) (1), \(2<4\) (0) → score 1

• \([3,1,2,4]\) : \(1<3\) (0), \(2>1\) (1), \(4>2\) (1) → score 2

• \([2,4,3,1]\) : \(4>2\) (1), \(3<4\) (0), \(1<3\) (0) → score 1

• \([2,4,1,3]\) : \(4>2\) (1), \(1<4\) (0), \(3>1\) (1) → score 2

• \([2,3,4,1]\) : \(3>2\) (1), \(4>3\) (1), \(1<4\) (0) → score 2

• \([2,3,1,4]\) : \(3>2\) (1), \(1<3\) (0), \(4>1\) (1) → score 2

• \([2,1,4,3]\) : \(1<2\) (0), \(4>1\) (1), \(3<4\) (0) → score 1

• \([2,1,3,4]\) : \(1<2\) (0), \(3>1\) (1), \(4>3\) (1) → score 2

• \([1,4,3,2]\) : \(4>1\) (1), \(3<4\) (0), \(2<3\) (0) → score 1

• \([1,4,2,3]\) : \(4>1\) (1), \(2<4\) (0), \(3>2\) (1) → score 2

• \([1,3,4,2]\) : \(3>1\) (1), \(4>3\) (1), \(2<4\) (0) → score 2

• \([1,3,2,4]\) : \(3>1\) (1), \(2<3\) (0), \(4>2\) (1) → score 2

• \([1,2,4,3]\) : \(2>1\) (1), \(4>2\) (1), \(3<4\) (0) → score 2

• \([1,2,3,4]\) : score 3

On compte les listes de score 1 : \([4,3,1,2], [4,2,3,1], [4,2,1,3], [4,1,3,2], [3,4,2,1], [3,2,4,1], [3,2,1,4], [3,1,4,2], [2,4,3,1], [2,1,4,3], [1,4,3,2]\) → 11 listes.

Donc \(L_4(1) = 11\).

Calculons \(2L_3(1) + 3L_3(0) = 2 \times 4 + 3 \times 1 = 8 + 3 = 11\). ✅

6d. Montrer \(L_{n+1}(1) = 2L_n(1) + nL_n(0)\)

Soit \(A\) une liste de longueur \(n+1\). On lui enlève l'élément \(n+1\) (le plus grand), ce qui donne une liste \(B\) de longueur \(n\), et \(A\) s'obtient en insérant \(n+1\) dans l'une des \(n+1\) positions possibles de \(B\) (avant le premier terme, entre deux termes, ou après le dernier). Comme \(n+1\) est le plus grand de tous, chaque insertion a un effet prévisible sur le score :

• Insertion avant le premier terme : la nouvelle comparaison est (premier de \(B\)) \(

• Insertion après le dernier terme : la nouvelle comparaison est (dernier de \(B\)) suivi de \(n+1\), qui est toujours une augmentation → le score augmente de 1.

• Insertion entre deux termes \(x,y\) de \(B\) : la comparaison \(x,y\) (une seule) est remplacée par deux comparaisons \(x,n+1\) et \(n+1,y\). Comme \(xy\) toujours (pas une augmentation), ces deux nouvelles comparaisons contribuent exactement 1 augmentation au total — autant que la seule comparaison \((x,y)\) si elle en était déjà une, ou 1 de plus si elle n'en était pas une. Donc : si le couple \((x,y)\) était une augmentation dans \(B\), le score ne change pas ; s'il n'en était pas une, le score augmente de 1.

Ainsi, pour obtenir une liste \(A\) de score \(1\) :

• soit \(B\) a déjà score \(1\) (une seule augmentation), et on insère \(n+1\) soit avant le premier terme, soit dans l'unique gap-augmentation de \(B\) : cela fait \(2\) positions qui préservent le score — d'où le terme \(2L_n(1)\) ;

• soit \(B\) a score \(0\) (aucune augmentation, donc \(B\) est l'unique liste strictement décroissante), et on insère \(n+1\) dans l'un des \(n-1\) gaps entre ses termes (chacun étant une non-augmentation, donc le score passe de 0 à 1), ou après le dernier terme (score passe aussi de 0 à 1) : cela fait \((n-1)+1=n\) positions qui donnent score 1 (la seule position qui NE donne PAS score 1 est celle du tout début, qui laisse le score à 0) — d'où le terme \(nL_n(0)\).

Au total : \(L_{n+1}(1) = 2L_n(1) + nL_n(0)\).

6e. Exprimer \(L_{n+1}(k)\) en fonction de \(L_n(k)\) et \(L_n(k-1)\).

Le même raisonnement se généralise à tout \(k\). Une liste \(B\) de longueur \(n\) et de score \(k\) a \(k\) gaps-augmentation et \(n-1-k\) gaps-non-augmentation (plus les positions extrêmes avant/après). D'après l'analyse ci-dessus :

• À partir de \(B\) de score \(k\) : les positions qui préservent le score sont les \(k\) gaps-augmentation, plus la position tout au début : soit \(k+1\) positions.

• À partir de \(B\) de score \(k-1\) : les positions qui font passer le score à \(k\) sont les \((n-1-(k-1))=(n-k)\) gaps-non-augmentation, plus la position tout à la fin : soit \(n-k+1\) positions.

D'où la formule générale (récurrence des nombres eulériens) :

\[L_{n+1}(k) = (k+1)\,L_n(k) + (n-k+1)\,L_n(k-1).\]

6f. Tableau des \(L_n(k)\) pour \(n\in\{3,4,5\}\), \(k\in\{0,\ldots,4\}\).

\(n\backslash k\)	0	1	2	3	4
3	1	4	1	0	0
4	1	11	11	1	0
5	1	26	66	26	1