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 !
...
Réponses
-
Il faut multiplier par $\binom{4}{2}$ car sur les $4$ jours consacrés à l'escrime et au javelot conjointement, il faut encore choisir les $2$ durant lesquels auront lieu les tournois d'escrime (ou de javelot, c'est pareil par symétrie des coefficients binomiaux).
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. -
Si les événements $F,J,C$ s'étalent sur 5 jours, on sait que le dernier jour est consacré à $C$, que 2 des 4 restants sont consacrés à $F$ et les deux derniers à $J$.
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. -
C'est très clair. Merci beaucoup !
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}
... -
Le dernier cas est le plus simple. Puisque $F, J, C$ s'étalent sur $3$ jours seulement, il faut choisir $1$ jour pour $C$, un deuxième jour pour $F$ $\textbf{et}$ $J$, un troisième jour pour $F$ $\textbf{et}$ $J$ à nouveau.
...
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.8K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
Qui est en ligne 41
+34 Invités