Exercice académique 1 — Ramasse tes billes (tous candidats)

C'est le problème classique des « étoiles et barres » (stars and bars) : un rangement de \(b\) billes dans \(c\) compartiments se code par un mot de \(b\) lettres \(B\) et \(c-1\) lettres \(P\) (les parois séparant les compartiments), de longueur \(b+c-1\). Le nombre de tels mots est \(\binom{b+c-1}{c-1}=\binom{b+c-1}{b}\).

5. Le nombre de façons de placer 2 lettres \(B\) parmi \(2025+1=2026\) positions est \(\binom{2026}2\).

6. Le dual d'un mot à \(b\) lettres \(B\) et \(c-1\) lettres \(P\) a \(c-1\) lettres \(B\) et \(b\) lettres \(P\) : il code un rangement de \(c-1\) billes dans \(b+1\) compartiments. Pour \((b,c)=(2024,3)\), le dual correspond exactement au rangement de la question 5.

3c. Utiliser la relation de récurrence de la question 3a appliquée à deux valeurs consécutives de \(b\) (ou de \(c\)) pour faire apparaître un télescopage.

Correction officielle APMEP.

Première Partie

1. Des cas particuliers :
   1. On prend ici \(b = 2\) (deux billes) et \(c = 3\) (trois compartiments) :

      En choisissant une case pour 2 billes, on a 3 possibilités, puis 1 case pour 0 billes et 1 dans chaque autre on a aussi 3 possibilités, soit 6 rangements possibles donc \(R(2 ; 3) = 6\).

   2. On choisit une case pour 2 billes (3 possibilités) puis 1 case pour la bille restante (2 possibilités) soit 6 possibilités. Il faut ajouter le cas où il y a une bille par case, et les 3 cas où il y 3 billes dans une case. En listant toutes ces possibilités, on trouve \(R(3 ; 3) = 10\).
   3. Le calcul de \(R(1 ; c)\) revient à placer 1 bille dans \(c\) compartiments. Il y a donc \(c\) possibilités et \(R(1 ; c) = c\).

      Le calcul \(R(b ; 1)\) revient à placer \(b\) billes dans un seul compartiment, il y a donc une seule possibilité et \(R(b ; 1) = 1\).

   4. Pour calculer \(R(b ; 2)\), on peut choisir le nombre de billes à placer dans le premier compartiment (de \(0\) à \(b\) soit \(b + 1\) possibilités), le reste est donc dans le deuxième.

      On peut donc en déduire que \(R(b ; 2) = b + 1\).

2. D'après la question 1)c), on a \(R(1 ; 2025) = 2025\). Si on considère le placement de toutes les billes dans le même compartiment, on peut en déduire que la valeur de \(R(1 ; 2025)\) est inférieure à \(R(b ; 2025)\). Il n'y a donc pas de valeur de \(b\) telle que \(R(b ; 2025) < 2025\).
3. On pose \(c \geqslant 2\).
   1. On considère le rangement de \(b\) billes dans \(c\) compartiments. Pour cela, on peut choisir le nombre \(i\) de billes dans les \((c - 1)\) premiers compartiments. Soit \(i = 0\) à \(b\) et donc \(R(i, c - 1)\) façons de les placer sauf pour le cas \(i = 0\) où il y a une seule façon de faire puisqu'aucune bille n'est à placer. On place ensuite les billes restantes dans le dernier compartiment.

      Ainsi : \[ R(b ; c) = 1 + \sum_{i=1}^{b} R(i ; c-1) \]

   2. Pour compléter le tableau, on utilise :
      • La question 1)c) pour remplir la première colonne et la première ligne.
      • La formule précédente : chaque case est égale à 1 plus la somme des cases dans la colonne juste à gauche jusqu'à la hauteur de la case en question.
      \[ \begin{array}{|c|c|c|c|c|c|} \hline & c = 1 & c = 2 & c = 3 & c = 4 & c = 5 \\ \hline b = 1 & 1 & 2 & 3 & 4 & 5 \\ \hline b = 2 & 1 & 3 & 6 & 10 & 15 \\ \hline b = 3 & 1 & 4 & 10 & 20 & 35 \\ \hline b = 4 & 1 & 5 & 15 & 35 & 70 \\ \hline b = 5 & 1 & 6 & 21 & 56 & 126 \\ \hline \end{array} \]
   3. On peut remarquer que la case que l'on complète \(R(b + 1 ; c)\) est égale à la somme de deux cases, une au-dessus \(R(b ; c - 1)\) et une à gauche \(R(b ; c)\).

      On peut donc conjecturer que \[ R(b ; c) + R(b + 1 ; c - 1) = R(b + 1 ; c) \]

      Pour le démontrer on s'appuie sur la formule obtenue à la question 3)a) :

      \[\begin{aligned} R(b;c) + R(b+1;c-1) &= 1 + \sum_{i=1}^{b} R(i;c-1) + R(b+1;c-1) \\ &= 1 + \sum_{i=1}^{b+1} R(i;c-1) \\ &= R(b+1;c) \end{aligned}\]

   Deuxième Partie

4. Avec \(b=2\) et \(c=3\), il nous faut créer des mots avec 2 B et 2 P.

   On peut faire les mots suivants : \(BBPP\), \(BPBP\), \(BPPB\), \(PBBP\), \(PBPB\), \(PPBB\). De nouveau \(R(2;3)=6\).

5. On doit donc considérer des mots constitués de 2026 lettres, \(b=2\) donc 2 lettres B et \(c=2025\) donc 2024 lettres P. On doit donc ensuite placer les deux lettres B, le reste sera donc rempli par la lettre P.

   {Choix de 2 positions parmi 2026}, ainsi \(R(2;2025) = \binom{2026}{2} = \frac{2026 \times 2025}{2} = 2\,051\,325\).

6. Le dual du rangement avec \(b = 2024\) et \(c = 3\) contient 2024 lettres P et 2 lettres B. Il correspond donc à \(b = 2\) et \(c = 2025\).

   On peut donc en déduire que : \[ R(2024;3) = R(2;2025) = 2\,051\,325 \]