Exercices corrigés
Cette page contient 12 exercices.
| Exercice 1. On se donne {n} points du plan, trois à trois non alignés. Combien existe-t-il de polygones à {p} cotés dont les sommets soient {p} de ces points?. |
Il y a pour cela {\dbinom{n}{p}} possibilités.
Si on fixe un de ces sommets comme origine, on doit alors alors choisir une permutation des {n-1} autres sommets, ce qui laisse {(p-1)!} choix possibles. Mais compte tenu des deux sens de parcours possibles, un même polygone est alors comptabilisé deux fois.
Par exemple si {p=4} et si les quatre points choisis sont {A,B,C,D}, et en fixant {A} comme origine, il y a {3} quadrilatères possibles : {ABCD}, {ABDC} et {ACBD} (les solutions {ACDB}, {ADBC} et {ADCB} donnent en effet les trois mêmes quadrilatères que précédemment, au sens de parcours près, qui est ici sans importance).
Conclusion : le nombre de polygones est :{\dfrac12\,(p-1)!\,\dbinom{n}{p}=\dfrac{n!}{2p(n-p)!}}
| Exercice 2. Quel est le nombre de diagonales d’un polygone strictement convexe de {n} cotés? En combien de points intérieurs au polygone ces diagonales se coupent-elles? (on supposera que le polygone est dans sa forme la plus générale, c’est-à-dire que les points d’intersection considérés sont distincts deux à deux). On pourra proposer plusieurs démonstrations. |
-
Une diagonale « orientée » est définie par un sommet de départ {A} (choisi parmi {n}) et un sommet d’arrivée choisi parmi les {n-3} sommets distincts et non contigus à {A} (un coté n’est pas une diagonale…).
Mais chaque diagonale est alors comptée deux fois, car on ne doit pas considérer l’orientation.
Le polygone comporte donc {\dfrac12n(n-3)} diagonales distinctes.
-
Notons {p_n} le nombre de points d’intersection des diagonales du polygone convexe {\mathcal{P}_n} à {n} sommets (rappelons qu’on ne considère que des points intérieurs à {\mathcal{P}_n}).
Notons {A_1,A_2,\ldots,A_{n-1},A_n} les sommets successifs de {{\mathcal P}_n}, et {D_{i,j}} la diagonale {A_iA_j}.
On va procéder à un dénombrement des {p_n} points d’intersection des diagonales.
- Il y a d’abord les {p_{n-1}} points d’intersection des diagonales de {\mathcal{P}_{n-1}=A_1,A_2,\ldots,A_{n-1}}.
-
Soit {k} un entier compris entre {2} et {n-2}.
{D_{n,k}} rencontre les {(k-1)(n-1-k)} diagonales {D_{i,j}} ({1\le i\lt k\lt j\lt n})
On a donc l’égalité {p_n=p_{n-1}+ \displaystyle\sum_{k=2}^{n-2}(k-1)(n-1-k)}On en déduit :{\begin{array}{rl}p_n&=p_{n-1}+\displaystyle\sum_{k=1}^{n-3}k(n-2-k)\\[9pts]&=p_{n-1}+(n-2) \displaystyle\sum_{k=1}^{n-3}k- \displaystyle\sum_{k=1}^{n-3}k^2\\\\&=p_{n-1}+(n\!-\!2)\dfrac{(n\!-\!3)(n\!-\!2)}2\\[9pts]&\quad-\dfrac16(n\!-\!3)(n\!-\!2)(2n\!-\!5)\\\\&=p_{n-1}+\dfrac16(n-1)(n-2)(n-3)\end{array}}Cette égalité est valable à partir de {n=4}, et on a bien sûr {p_3=0}.
On en déduit, par addition de {4} à {n} : {p_n=\dfrac16 \displaystyle\sum_{m=4}^{n}(m-1)(m-2)(m-3)}Posons {v_m=(m-1)(m-2)(m-3)(m-4)}
On a alors : {\begin{array}{rl}v_{m+1}-v_m&=m(m-1)(m-2)(m-3)\\\\&\quad-(m-1)(m-2)(m-3)(m-4)\\\\&=4(m-1)(m-2)(m-3)\end{array}}On en déduit :{\begin{array}{rl}p_n&=\dfrac1{24} \displaystyle\sum_{m=4}^{n}(v_{m+1}-v_{m})\\\\&=\dfrac1{24}(v_{n+1}-v_4)=\dfrac1{24}v_{n+1}\\\\&=\dfrac1{24}n(n-1)(n-2)(n-3)\end{array}}
-
On remarque que {p_n=p_{n-1}+\dbinom{n-1}{3}}.
On aurait pu obtenir ce résultat plus rapidement avec le raisonnement suivant :
La différence {p_n-p_{n-1}} est l’augmentation du nombre de points d’intersection des diagonales quand on passe du polygone {\mathcal{P}_{n-1}=A_1A_2\ldots A_{n-1}} au polygone {\mathcal{P}_{n}=A_1A_2\ldots A_{n-1}A_n}.
Mais il y a autant de nouveaux points d’intersection qu’il y a de façons de choisir trois points distincts parmi les {n-1} points {A_1,A_2,\ldots,A_{n-1}}.
En effet le choix des trois points {A_i,A_j,A_k}, avec par exemple {1\le i\lt j\lt k\le n-1}, définit le point d’intersection de la diagonale {A_jA_n} avec la diagonale {A_iA_k}.
-
On remarque que le résultat final est {p_n=\dbinom{n}{4}}.
Cela se déduisait de l’égalité {p_n=p_{n-1}+\dbinom{n-1}{3}}.
En effet (triangle de Pascal) : {p_n=p_{n-1}+\dbinom{n-1}{3}=p_{n-1}+\dbinom{n}{4}-\dbinom{n-1}{4}}Cela signifie que {n\mapsto p_n-\dbinom{n}{4}} est constante.
Or {p_4=\dbinom{4}{4}=1}. Il en résulte l’égalité {p_n=\dbinom{n}{4}}.
-
La simplicité du résultat final laisse entrevoir qu’il existe sans doute une autre méthode.
Effectivement, et il faut bien dire que cela ruine un peu tout ce qui précède!
Un point d’intersection intérieur au polygone {\mathcal{P}_n} est en effet défini de façon biunivoque par la donnée de quatre points de {\mathcal{P}_n}.
Plus précisément, si on note {A_r,A_s,A_t,A_u} ces quatre points (avec {1\le r\lt s\lt t\lt u\le n}, donc parcourus dans cet ordre sur {P_n}) alors les diagonales {A_rA_t} et {A_sA_u} se coupent en un point intérieur à {\mathcal{P}_n} (les autres diagonales se coupant peut-être, mais à l’extérieur de {\mathcal{P}_n} : c’est là qu’intervient la convexité du polygone).
Il y a donc autant de points d’intersection intérieurs qu’il y a de façons de choisir {4} des {n} sommets de {\mathcal{P}_n}, ce qui donne effectivement {p_n=\dbinom{n}{4}}.
| Exercice 3. Combien y-a-t-il de dominos dans un jeu complet? (On pourra donner plusieurs démonstrations). |
- On peut identifier un domino à un singleton de {\{0,1\ldots,6\}} (dans le cas d’un « double ») et il y a {7} possibilités, ou à une paire de {\{0,1\ldots,6\}} (dans les autres cas) et il y a alors {\dbinom{7}{2}=21} possibilités. Le nombre de dominos différents est donc {28}.
-
Un domino « orienté » est un couple {(a,b)} de {\{0,1,\ldots,6\}^2}. Il y en a {7^2}.
Dans ce lot, il y a {7} dominos doubles (qui ne sont comptés qu’une fois).
Les autres sont comptés deux fois puisqu’on ne doit pas considérer l’orientation.
Dans un jeu complet, il y a donc {7+\dfrac12(7^2-7)=28} dominos différents.
-
On peut également considérer qu’un domino est une application croissante {f} de {\{1,2\}} vers {\{0,1,\ldots,6\}} : {f(1)} est le chiffre minimum du domino et {f(2)} est son chiffre maximum.
Pour chaque valeur {k} de {f(1)}, il y a {7-k} possibilités pour {f(2)}.
Le nombre de dominos est donc : {\displaystyle\sum_{k=0}^{6}(7-k)=\displaystyle\sum_{k=1}^{7}k=\dfrac12\,7\cdot8=28}
-
On peut aussi identifier un domino à un mot de {8} lettres comportant une fois chaque entier de {0} à {6} et deux fois le symbole {\vert}. Par exemple :
- {1\vert234\vert56} représente le domino {\fbox{1}\fbox{4}}
- {\vert123456\vert} représente le domino {\fbox{\phantom{0}}\fbox{6}}
- {\vert\vert123456} représente {\fbox{\phantom{0}}\fbox{\phantom{0}}} et {123456\vert\vert} représente {\fbox{6}\fbox{6}}
Il y a {\dbinom{8}{2}=28} manières de former un tel mot, et donc autant de dominos.
-
On peut enfin considérer que les dominos résultent du tirage simultané de {2} jetons parmi {8}, ces {8} jetons comportant respectivement les symboles {0,1,\ldots,6} et le symbole {*}. Ce dernier jeton est en fait un « joker » prenant la valeur de l’autre jeton issu du tirage.
Il y a {\dbinom{8}{2}=28} tirages possibles donc {28} dominos.
Cette page contient 12 exercices. La suite est réservée aux abonnés.
- avoir une souscription active sur mathprepa
- et être connecté au site
Pour poursuivre votre exploration, vous pouvez :
- revenir à la page d’accueil
- ou tester la page d’extraits libres