Combinatoire et légende arthurienne
Le roi Arthur a des grands projets pour le joli moi de Mai.
Il dit à ses chevaliers :- Nous avons $31$ jours sans obligations particulières et nous allons en profiter pour organiser des tournois d'escrimes $\textbf{(fencing days)}$ et de lancers de javelots $\textbf{(javelin days)}$. Chacune de ces compétitions durera $2$ jours pas nécessairement consécutifs et puisque je sais qu'aucun des participants n'est impliqué dans les deux disciplines à la fois, les tournois pourront s'effectuer sur plusieurs jours ou bien le même jour.
Le roi Arthur se tourne alors vers sir Gauvain :- En combien de jours pouvez-vous réaliser le calendrier de ces évènements ?
- N'oubliez pas qu'après les compétitions, nous organisons un festin $\textbf{(celebration day)}$ et qu'il doit avoir lieu $\textbf{avant}$ la fin du mois- dit la reine Guenièvre.
Après un instant de réflexion, sir Gauvain déclare: "Si nous avons notre jour de célébration le $31$ mai, il y a $\binom{30}{2}$ possibilités pour l'escrime et, indépendamment, $\binom{30}{2}$ possibilités pour le javelot, soit $\binom{30}{2}^2$ possibilités.
Si nous organisons les célébrations le $30$ mai, nous aurons $\binom{29}{2}^2$ possibilités. Si le jour des célébrations est le $29$...
- Allez-vous recommencer ce rituel 30 fois ?- s'impatiente le fils du roi.
- Non-intervient Lancelot- le jour des célébrations ne pouvant se tenir avant le $3$ mai, la somme sera $$
\sum_{k=2}^{30} \binom{k}{2}^2
$$ - Ne serait-il pas plus simple de considérer les $3$ cas suivants ? dit Merlin.
$\textbf{(a)}$ Les évènements $F$ (fencing), $J$ (javelin) et $C$ (celebration) durent tous ensembles $5$ jours.
$\textbf{(b)}$ Les évènements durent $4$ jours.
$\textbf{(c)}$ Les évènements durent $3$ jours.
Dans le cas $\textbf{(a)}$, il y a bien sûr $\binom{31}{5}$ choix possibles pour les jours de compétitions.
Mais il faut multiplier cette quantité par $\binom{4}{2}=6$.
Or, je ne saisis pas très bien la signification combinatoire de ce facteur $6$.
À quels choix correspond-il ?
Avez-vous une idée, sans rentrer dans les détails des calculs, sur la manière de généraliser ce problème dans le cas où une compétition durerait $p$ jours, la deuxième $q \geq p$ jours, avec au total $n+1$ jours consacrés aux deux compétitions et à la célébration ?
En vous remerciant pour d'éventuelles suggestions.
PS: message corrigé suite à l'indication de @GaBuZoMeu. Merci !
...
Il dit à ses chevaliers :- Nous avons $31$ jours sans obligations particulières et nous allons en profiter pour organiser des tournois d'escrimes $\textbf{(fencing days)}$ et de lancers de javelots $\textbf{(javelin days)}$. Chacune de ces compétitions durera $2$ jours pas nécessairement consécutifs et puisque je sais qu'aucun des participants n'est impliqué dans les deux disciplines à la fois, les tournois pourront s'effectuer sur plusieurs jours ou bien le même jour.
Le roi Arthur se tourne alors vers sir Gauvain :- En combien de jours pouvez-vous réaliser le calendrier de ces évènements ?
- N'oubliez pas qu'après les compétitions, nous organisons un festin $\textbf{(celebration day)}$ et qu'il doit avoir lieu $\textbf{avant}$ la fin du mois- dit la reine Guenièvre.
Après un instant de réflexion, sir Gauvain déclare: "Si nous avons notre jour de célébration le $31$ mai, il y a $\binom{30}{2}$ possibilités pour l'escrime et, indépendamment, $\binom{30}{2}$ possibilités pour le javelot, soit $\binom{30}{2}^2$ possibilités.
Si nous organisons les célébrations le $30$ mai, nous aurons $\binom{29}{2}^2$ possibilités. Si le jour des célébrations est le $29$...
- Allez-vous recommencer ce rituel 30 fois ?- s'impatiente le fils du roi.
- Non-intervient Lancelot- le jour des célébrations ne pouvant se tenir avant le $3$ mai, la somme sera $$
\sum_{k=2}^{30} \binom{k}{2}^2
$$ - Ne serait-il pas plus simple de considérer les $3$ cas suivants ? dit Merlin.
$\textbf{(a)}$ Les évènements $F$ (fencing), $J$ (javelin) et $C$ (celebration) durent tous ensembles $5$ jours.
$\textbf{(b)}$ Les évènements durent $4$ jours.
$\textbf{(c)}$ Les évènements durent $3$ jours.
Dans le cas $\textbf{(a)}$, il y a bien sûr $\binom{31}{5}$ choix possibles pour les jours de compétitions.
Mais il faut multiplier cette quantité par $\binom{4}{2}=6$.
Or, je ne saisis pas très bien la signification combinatoire de ce facteur $6$.
À quels choix correspond-il ?
Avez-vous une idée, sans rentrer dans les détails des calculs, sur la manière de généraliser ce problème dans le cas où une compétition durerait $p$ jours, la deuxième $q \geq p$ jours, avec au total $n+1$ jours consacrés aux deux compétitions et à la célébration ?
En vous remerciant pour d'éventuelles suggestions.
PS: message corrigé suite à l'indication de @GaBuZoMeu. Merci !
...
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Si on avait une compétition de $p$, et une de $q \geq p$ jours à imposer avant le jour $n+1$, le coefficient $\binom{30}{2}^2$ doit simplement être remplacé par $\binom{n}{p} \times \binom{n}{q}$. Si ça doit se passer avant le jour $n$, on aura $\binom{n-1}{p} \times \binom{n-1}{q}$ (à condition que $p+q \leq n-1$), etc.
Donc, une fois que les 5 jours sont choisis parmi les 31 (tu as dû mal transcrire, vérifie, la bonne façon de compter le nombre de choix possibles pour ces 5 jours est forcément $\binom{31}{5}$), le seul choix qui reste à faire pour fixer totalement le calendrier est le choix des 2 jours de $F$ parmi les 4 premiers jours des 5.
J'avais omis ma propre indication, à savoir que $F$ et $J$ peuvent être menés simultanément !
Donc en suivant la "méthode Merlin", pour le cas $\textbf{(b)}$, on a $4$ choix possibles sur $31$, le dernier étant consacré à $C$.
Il y a $3$ manières de choisir le jour où $F$ et $J$ auront lieu conjointement et deux façons de répartir $F$ et $J$ sur les deux jours restants.
Finalement, le total des choix est
\begin{equation}
\displaystyle 6\binom{31}{5}+6 \binom{31}{4}+ \binom{31}{3}
\end{equation}
...
...