tirelire

Problèmes de dénombrement (2)

Page précédente.

cordes

Voici les cordes à sauter de la classe maternelle. Combien y en a-t-il ?

Dans cette situation, il est certainement plus facile de compter les poignées (il y en a dix) et de déduire que puisque chaque corde a deux poignées, il y a 5 cordes.

 

Cette façon de faire est parfois utile pour dénombrer des objets mathématiques.

Il s'agit d'une adaptation du principe d'énumération que l'on respecte dans les méthodes de dénombrement à l'aide d'une partition décrites dans la page précédente.

L'idée est la suivante : s'il n'est pas facile de compter chaque objet une fois et une seule, on peut accepter de compter tous les objets le même nombre de fois. Il suffira à la fin pour obtenir le nombre correct d'objets de diviser par 3 si chaque objet a été compté 3 fois.

Combien un polygone ayant douze sommets a-t-il de diagonales ?

 

Il est nécessaire d'être d'accord sur ce que sont les diagonales d'un polygone : ce sont tous les segments joignant deux sommets du polygone, à l'exclusion des côtés.

Ainsi, tous les segments rouges de la figure ci-dessous sont des diagonales du polygone vert ABCDEFGHIJKL.

diagonales

Faire une partition de l'ensemble des diagonales n'est pas très commode.

La première idée qui vient à l'esprit est souvent celle-ci :

Les diagonales dont A est une extrémité / Les diagonales dont B est une extrémité / Les diagonales dont C est une extrémité…

Il ne s'agit pas d'une partition, en effet, la diagonale [BG] est comptée dans la catégorie "les diagonales dont B est une extrémité", elle est à nouveau comptée dans la catégorie "les diagonales dont G est une extrémité".

La remarque qui précède n'est pas valable seulement pour la diagonale [BG], elle est valable pour toutes les diagonales. Les catégories envisagées restent donc utiles : elles ne constituent pas une partition, mais si on additionne leurs effectifs chaque diagonale sera comptée deux fois… il suffira de diviser cette somme par deux pour obtenir le nombre correct de diagonales.

Il y a 9 diagonales ayant pour extrémité A (l'autre extrémité peut être n'importe lequel des 12 points sauv A, B ou L).

Il y a de même 9 diagonales ayant pour extrémité B, 9 diagonales ayant pour extrémité C…

La somme des effectifs des 12 catégories est donc 12 x 9, et le nombre de diagonales est (12 x 9) / 2 = 54

 

Et si on voulait s'en tenir strictement à l'idée de partition ?

Une première possibilité serait d'adapter les catégories de la méthode précédente pour que chaque diagonale soit dans une catégorie et dans une seule.

On peut par exemple décider d'utiliser les catégories suivantes :

Les diagonales ayant A pour extrémité / Les diagonales ayant B pour extrémité, mais pas A / Les diagonales ayant C pour extrémité, mais ni A ni B /Les diagonales ayant D pour extrémité mais ni A ni B ni C…

On peut alors dénombrer chacune des catégories dont les effectifs sont respectivement 9 9 8 7 6 5 4 3 2 1 0 0 (quand on arrive à K toutes les diagonales ayant K pour extrémité ont déjà été comptée dans une autre catégorie).

Le nombre de diagonales est donc 9 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 54.

 

Une autre partition :

diagonales2

Imaginons que le polygone soit coupé en deux parties, les coupure étant faites aux extrémités d'une diagonale. Parmi les 10 sommets restant du polygone, combien chacune des deux lignes en contient-elle ?
Sur le schéma de gauche, une ligne contient un sommet (bleu) et l'autre 9 (oranges).

Sur le schéma de droite, une ligne contient 4 sommets (bleus) et l'autre 6 (oranges).

 

Cette remarque suggère une partition dont voici les catégories :

  • Les diagonales qui partagent les 10 sommets restant groupes d'effectifs 1 et 9
  • Les diagonales qui partagent les 10 sommets restant groupes d'effectifs 2 et 8
  • Les diagonales qui partagent les 10 sommets restant groupes d'effectifs 3 et 7
  • Les diagonales qui partagent les 10 sommets restant groupes d'effectifs 4 et 6
  • Les diagonales qui partagent les 10 sommets restant groupes d'effectifs 5 et 5

Pour choisir une diagonale de la première catégorie, il suffit de choisir le sommet (bleu) unique, il y a donc 12 diagonales dans cette catégorie.

Pour choisir une diagonale de la deuxième catégorie, il suffit de choisir deux sommets (bleus) consécutifs, il y a donc 12 diagonales dans cette catégorie car les sommets peuvent être choisis en tournant autour du polygone : AB, BC, CD… jusqu'à LA.

Il y a également 12 diagonales dans la troisième catégorie correspondant aux 12 triplets de points, de ABC à LAB.

Il y a également 12 diagonales dans la quatrième catégorie.

Seule la dernière catégorie pose problème : il y a 12 façons de choisir 5 points consécutifs, de ABCDE à LABCD, mais une même diagonale correspond à deux de ces choix, par exemple, la diagonale [AG] correspond aux points consécutifs BCDEF, mais aussi à HIJKL. Il n'y a donc que 6 diagonales dans cette catégorie, et le nombre de diagonales du polygone est 4 x 12 + 6 = 54.

diagonales3

Et si, au lieu d'utiliser ou d'adapter le principe de partition, on l'abandonnait complètement ?

 

Une idée souvent fructueuse en mathématique quand un problème résiste consite à s'attaquer d'abord à un problème du même type mais plus simple.

Dans le cas des diagonales du polygone, on peut voir ce qu'il en est pour des polygones ayant un plus petit nombre de sommets, avec l'espoir que l'observation des exemples les plus simples nous permettra de remarquer une règle qu'il restera à prouver et à appliquer au polygone ayant 12 sommets.

Nombre de sommets

3

4

5

6

Nombre de diagonales

0

2

5

9

Ce travail préparatoire peut aboutir de différente manières :

Il se peut que la réalisation des dessins suffise à faire remarquer qu'on a une diagonale par sommet, puis deux diagonales par sommet puis trois diagonales par sommet…et que cela débouche sur une méthode proche de celle proposée en haut de cette page.

Il se peut aussi qu'on ne remarque rien à l'occasion du dessin et qu'on soit conduit à observer le tableau qui regroupe les résultats obtenus.

On peut chercher à y voir des règles différentes :

  • Une règle qui permettrait de calculer directement le nombre de diagonales à partir du nombre de sommets.
  • Une règle qui permettrait de compléter le tableau vers la droit étape par étape en calculant le nombre de diagonales d'un polygone à partir du nombre de diagonales du polygone ayant un sommet de moins.

 

La première règle ne saute pas aux yeux, en revanche on voit assez facilement que si on se déplace de gauche à droite dans la ligne du bas du tableau, on ajoute 2 puis 3 puis 4.

Plus précisément, quand on passe de 3 sommets à 4 on ajoute deux diagonales, de 4 sommets à 5 on ajoute 3 diagonales, de 5 sommets à 6 on ajoute 4 diagonales…

Il s'agit maintenant de savoir si ce que nous venons d'observer est une pure coïncidence, ou s'il s'agit d'une propriété généralisable.

Observons ce qui se passe quand on transforme un polygone à 6 côtés en un polygone à 7 côtés :

Quand on rajoute un 7ème sommet, on ajoute 4 diagonales rouges (joignant le nouveau sommet à tous les anciens, à l'exception de ses deux voisins).

De plus, l'ancien côté qui a été supprimé est devenu une diagonale.

Le nombre de diagonales créées est donc égal à 6 - 2 + 1 = 5

diagonales4

Si on rajoute un sommet à un polygone qui en a n, on créera n-2 diagonales rouges (joignant le nouveau sommet à tous les anciens, à l'exception de ses deux voisins) et une noire (l'ancien côté). Le nombre de nouvelles diagonales est donc égal à n - 2 + 1  = n - 1.

La remarque faite plus haut n'est donc pas une coïncidence, il s'agit d'une propriété générale qu'on peut utiliser pour compléter le tableau. de proche en proche.

Sommets

6

7

8

9

10

11

12

Diagonales

9

14

20

27

35

44

54

Si nous cherchions le nombre de diagonales d'un polygone ayant un très grand nombre de sommets, compléter ainsi de proche en proche ne serait pas très commode.

Maintenant que nous disposons d'un tableau un peu plus étoffé, peut-être pouvons nous y découvrir une règle permettant de calculer directement le nombre de diagonales à partir du nombre de sommets.

On peut remarquer que le nombre de diagonales est parfois un multiple du nombre de sommets. Quand ce n'est pas le cas, il suffirait de doubler le nombre de diagonales pour obtenir un multiple du nombre de sommets. En poursuivant ces observations, on peut finir par remarquer que le nombre de diagonales (D) s'obtient toujours à partir du nombre de sommets (S) par la formule suivante : D = S (S - 3) / 2

Il resterait à prouver que cette formule est toujours vraie, ce qui ne sera pas difficile car elle ne fait que décrire en la généralisant la toute première méthode utilisée en haut de cette page pour calculer le nombre de diagonales du polygone à 12 sommets :

Si S est le nombre de sommets, S - 3 est le nombre de diagonales issues d'un même sommet.

S (S - 3) est donc le double du nombre de diagonales puisque chacune est comptée 2 fois.

Le nombre de diagonales est alors D = S (S - 3) / 2

diagonales5

 

Problèmes voisins

Si vous avez compris les diverses solutions de ce problème, vous devriez pouvoir résoudre les problèmes suivants :

Le solide ci-contre est un dodécaèdre régulier : il a 12 faces qui sont toutes des pentagones réguliers.

  • Combien a-t-il de sommets ?
  • Combien a-t-il de diagonales ? (une diagonale est un segment qui joint deux sommets mais qui n'est pas située sur une face).

On considère 12 points alignés et un point S situé hors de la droite qui porte les 12 autres points.

Combien peut-on tracer de triangles ayant pour sommets le point S et deux des 12 points alignés ?

Les triangles bleu et orange de l'illustration sont deux exemples des triangles à dénombrer.

 

Les réponses sont ici.

 

 

.

diagonales6