tirelire

Problèmes de dénombrement (1)

Pourquoi travailler des problèmes de dénombrement en préparant le CRPE alors qu'il n'y en a pas au concours ?

  • Parce qu'il n'est pas si sûr qu'il n'y en ait pas au concours : il y en avait un magnifique exemple dans les sujets zéro de la version du CRPE dont la dernière session s'est tenue en 2010.
  • Plus fondamentalement parce qu'ils sont très formateurs : généralement on ne dispose pas d'une méthode toute faite pour résoudre le problème, il faut prendre des initiatives, s'organiser, et surtout expliciter les choix que l'on fait…

Tout ceci est fort utile pour résoudre d'autres problèmes, mais également pour enseigner les mathématiques à l'école élémentaire et justifierait une place plus importante des problèmes de dénombrement au concours de recrutement.

drapeau1

Problème 1

On veut fabriquer un drapeau constitué de 4 bandes horizontales superposées, toutes de même largeur, chacune des 4 bandes étant jaune, rouge ou verte.

Il n'est pas possible que deux bandes adjacentes soient de la même couleur.

Deux exemples de drapeaux acceptables sont fournis ci-contre.

Combien de drapeaux différents répondant à ces critères existe-t-il ?

Une idée de base : la partition.

On veut savoir combien il y a de points de couleur sur le dessin ci-contre.

On peut évidemment les compter un à un sans ordre particulier… ce qui est risqué (une erreur d'énumération est probable).

Il est plus prudent de procéder d'une des manières suivantes :

  • Compter les points verts, les rouges et les bleus puis additionner les trois nombres obtenus.
  • Compter les points à l'intérieur de chacune des lignes A,B et C et additionner les trois résultats.
drapeau2

Chacune de ces façons de procéder s'appuie sur une partition de l'ensemble des points dessinés, c'est à dire un partage en plusieurs catégories de telle façon que chaque point appartienne à une catégorie et une seule :

 

Considèrons les trois catégorie suivantes : Les points verts, les points bleus, les points rouges.

Chacun des points de l'ensemble appartient à l'une des catégories et à une seule, il s'agit bien d'une partition. En procédant comme on l'a indiqué plus haut, chaque point est alors compté une fois et une seule, c'est ce qui convient.

 

Les ensembles A, B et C du dessin constituent également une partition de l'ensemble des points.

 

Expliciter la partition utilisée est souvent l'étape cruciale d'un problème de dénombrement… et l'erreur la plus souvent commise consiste à dénombrer une des catégories sans s'assurer qu'on a bien une partition.

Il n'y aurait aucun intérêt à dénombrer les points contenus dans l'ensemble A du dessin ci-dessous :

Les ensembles A B et C ne forment pas une partition puisque certains points ne sont dans aucun de ces trois ensembles et d'autres sont comptés plusieurs fois.

Le premier travail à faire serait donc de modifier A B et C afin d'obtenir une partition.

 

Ce qui parait évident dans ce cas l'est beaucoup moins quand on ne dénombre plus des points dessinés sur une feuille ni des objets matériels mais des êtres mathématiques plus fugaces.

drapeau3

Application de l'idée de partition au problème des drapeaux

 

Voici quelques partitions envisageables de l'ensemble de drapeaux qu'on veut dénombrer :

  • Les drapeaux sans bande jaune / avec une bande jaune / avec deux bandes jaunes.
  • Les drapeaux qui utilisent deux couleurs / ceux qui utilisent trois couleurs.
  • Les drapeaux dont la bande du haut est jaune / verte / rouge.
  • Les drapeaux dont la bande du bas et celle du haut sont de la même couleur / ceux dont la bande du bas et du haut ne sont pas de la même couleur.

Il s'agit bien à chaque fois d'une partition, mais certaines partitions sont plus pratiques que d'autres. Nous allons poursuivre seulement la deuxième et la troisième des idées ci-dessus.

 

Première méthode : dénombrons les drapeaux bicolores puis les drapeaux tricolores

On peut subdiviser la catégorie bicolore en trois sous-catégories selon qu'on utilise le jaune et le vert, le vert et le rouge, ou bien le jaune et le rouge.

Comme deux bandes qui se touchent ne peuvent pas être de la même couleur, les seuls drapeaux jaune et vert possibles sont :

drapeau4

Il y a également deux drapeaux utilisant le rouge et le vert et deux utilisant le rouge et le jaune, soit 6 drapeaux bicolores en tout.

Dans les drapeaux tricolores, l'une des deux couleurs est présente sur trois bandes. cette couleur en double peut être soit le jaune soit le vert, soit le rouge.

Détaillons la catégorie des drapeaux tricolores ayant deux bandes jaunes.

drapeau5

Pour que les deux bandes jaunes ne se touchent pas, elles peuvent être disposées de trois façons, conformément aux schémas ci-dessus.

Pour chacune de ces trois dispositions, les bandes restantes peuvent être remplies soit avec le vert en haut soit avec le rouge en haut.

Il y a donc 6 drapeaux tricolores ayant deux bandes jaunes.

Il y a également 6 drapeaux tricolores ayant deux bandes vertes et 6 ayant deux bandes rouges.

 

Le nombre total de drapeaux possibles est donc 24 : 18 tricolores et 6 bicolores.

 

Deuxième méthode : dénombrons les drapeaux tricolores ayant la bande supérieure jaune.

La deuxième bande en partant du haut peut être choisie de deux façons (rouge ou verte).

pour chacune de ces deux possibilités, la troisième bande peut être choisie de deux façons (chacune des deux couleurs non utilisées à l'étape précédente).

La quatrième bande peut enfin être choisie de deux façons également (chacune des deux couleurs non utilisées pour la troisième bande).

Ces choix successifs peuvent être représentés par l'arbre suivant :

drapeau6

Cet arbre montre qu'il y a 8 drapeaux différents dont la bande supérieure est jaune. Comme il y a également 8 drapeaux dont la bande supérieure est rouge et 8 dont la bande supérieure est verte, il y a en tout 3 x 8 = 24 drapeaux possibles.

Remarque : quand on trouve une arborescence régulière comme celle-ci, c'est bien pratique pour dénombrer, en particulier si on doit généraliser : on voit bien que si le drapeau avait une cinquième bande, il y aurait deux façons de la choisir ce qui doublerait le nombre de drapeaux.

Cependant la découverte d'une telle arborescence régulière n'est ni indispensable (cf première méthode) ni toujours possible.

Une façon de se dispenser d'expliciter une partition.

 

Revenons au décompte des points sur une feuille.

Si les points sont organisés comme ceci le dénombrement ne pose pas de problème particulier, on ne risque guère en suivant une ligne d'oublier un point ou de compter plusieurs fois le même point.

drapeau7
drapeau8

 

Pour dénombrer une collection d'objets, on peut les placer en ligne.

Pour dénombrer une collection de points placés sur une feuille, on peut tracer une ligne passant une seule fois par chaque point.

 

Mais comment placer dans un ordre facile à repérer des objets mathématiques ?

Une solution consiste à nommer les objets en utilisant des chiffres ou des lettres. On utilise ensuite l'ordre numérique ou l'ordre alphabétique pour dénombrer sans oubli ni double comptage les noms des objets à la place des objets eux-mêmes.

 

Application de cette méthode au problème des drapeaux :

Nommons chaque drapeau par 4 lettres (l'initiale de chaque couleur en partant du haut).

Nous ne tenons pas compte pour l'instant de la contrainte sur les couleurs voisines, ainsi nous allons trouver des drapeaux non autorisés que nous supprimerons par la suite.

Nous allons donc écrire tous les "mots" de 4 lettres que l'on peut former avec J R et V.

 

JJJJ JJJR JJJV JJRJ JJRR JJRV JJVJ JJVR JJVV

JRJJ JRJR JRJV JRRJ JRRR JRRV JRVJ JRVR JRVV

JVJJ JVJR JVJV JVRJ JVRR JVRV JVVJ JVVR JVVV

 

RJJJ RJJR RJJV RJRJ RJRR RJRV RJVJ RJVR RJVV

RRJJ RRJR RRJV RRRJ RRRR RRRV RRVJ RRVR RRVV

RVJJ RVJR RVJV RVRJ RVRR RVRV RVVJ RVVR RVVV

 

VJJJ VJJR VJJV VJRJ VJRR VJRV VJVJ VJVR VJVV

VRJJ VRJR VRJV VRRJ VRRR VRRV VRVJ VRVR VRVV

VVJJ VVJR VVJV VVRJ VVRR VVRV VVVJ VVVR VVVV

 

Parmi ces 81 "mots" écrits dans l'ordre alphabétique, quels sont ceux qui correspondent à des drapeaux valides ?

Dire qu'il ne faut pas que deux bandes de même couleur se touchent revient à dire qu'il ne faut pas que deux lettres idendiques se suivent.

Seuls les "mots" en rouge dans la liste suivante correspondent donc à des drapeaux valides : il y en a 24.

 

JJJJ JJJR JJJV JJRJ JJRR JJRV JJVJ JJVR JJVV

JRJJ JRJR JRJV JRRJ JRRR JRRV JRVJ JRVR JRVV

JVJJ JVJR JVJV JVRJ JVRR JVRV JVVJ JVVR JVVV

 

RJJJ RJJR RJJV RJRJ RJRR RJRV RJVJ RJVR RJVV

RRJJ RRJR RRJV RRRJ RRRR RRRV RRVJ RRVR RRVV

RVJJ RVJR RVJV RVRJ RVRR RVRV RVVJ RVVR RVVV

 

VJJJ VJJR VJJV VJRJ VJRR VJRV VJVJ VJVR VJVV

VRJJ VRJR VRJV VRRJ VRRR VRRV VRVJ VRVR VRVV

VVJJ VVJR VVJV VVRJ VVRR VVRV VVVJ VVVR VVVV

 

Pour ce problème cette méthode n'est pas particulièrement avantageuse… encore que rien ne nous oblige à être borné : on peut fort bien commencer la liste et remarquer qu'il y aura autant de drapeaux avec la bande supérieure jaune (c'est à dire de mots commençant par j) qu'avec la bande supérieure rouge ou verte. Le nombre de mots à écrire est alors beaucoup plus raisonnable… mais on a réintroduit l'idée de partition.

 

Problèmes voisins

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

 

Combien peut-on former de drapeaux s'il y a toujours 4 bandes, mais avec 4 couleurs ?

Combien peut-on former de drapeaux s'il y a toujours 3 couleurs mais 5 bandes ?

Combien peut on former de drapeaux s'il y a toujours 3 couleurs et si les zones sont disposées comme indiqué par chaque dessin ci-dessous.

Les réponses sont ici.

drapeau9
drapeau10

Page suivante

 

 

.