Donne-moi ta main et prends la mienne…

Les filles, ça n’aime pas la garçons. Ça tire les cheveux et ça met des coups de pieds, un garçon. C’est nul un garçon. Les filles, ça préfère rester entre filles !

Les garçons, ça n’aime pas les filles. Ça pleure tout le temps, une fille. C’est nul une fille.

En rang !

Ce matin, la maîtresse a demandé à toute la classe de se mettre sur une seule rangée dans la cour et de se donner la main. Chaque fille a donné la main à au moins une autre fille, pour ne pas être entourée de deux garçons. S’il y a 30 élèves dans cette classe et qu’on ne sait pas a priori combien il y a de filles et de garçons, combien de dispositions différentes a-t-il pu y avoir de cette rangée ? Par disposition, on entend une suite du type

‘Fille-Fille-Garçon-Fille-Fille-Fille- … – Garçon’

Par exemple, s’il y a 3 élèves dans cette classe, voici les quatre dispositions possibles:

Dispositions_possibles_classe_de_3_elevesVous voyez donc, qu’à chaque fois, chaque fille donne bien la main à au moins une autre fille.

Remarque: pour une classe comptant un élève la seule bonne disposition est:

Dispositions_possibles_classe_de_1_eleveet pour une classe de deux élèves, ce sont:Dispositions_possibles_classe_de_2_elevesAvant de lire la suite, essayez vous-même de dessiner toutes les dispositions possibles pour des classes de 4, 5 ou 6 élèves. Vous savez tous dessiner des petits bonhommes, n’est-ce pas ?

Classe de 4 élèves

Lorsque la classe compte 4 élèves, il y a cette fois-ci 7 bonnes dispositions possibles:

Dispositions_possibles_classe_de_4_elevesClasse de 5 élèves

Voici les 12 bonnes dispositions qu’on obtient pour une classe de 5 élèves:

Dispositions_possibles_classe_de_5_elevesOn ne va pas tout le temps énumérer toutes les dispositions possibles… non, ce serait trop long (et les élèves seront de toute façon partis dès que la cloche aura sonné  !). On va plutôt essayer d’analyser les dispositions obtenues et voir comment on peut se ramener astucieusement aux cas précédents.

Pour cela, reprenons les 12 dispositions possibles pour une classe de 5 élèves. Si on observe bien, on peut les regrouper de la façon suivante:

Dispositions_possibles_classe_de_5_eleves_regroupementOn voit qu’il y a deux types de dispositions:

1)Les dispositions qui se terminent par un garçon (dans le cadre en rouge). On voit dans ce cas que les 4 premiers élèves forment une bonne disposition d’ordre 4:

Dispositions_possibles_classe_de_5_eleves_regroupement_1er_cas2) Les dispositions qui se terminent par deux filles (dans le cadre en bleu) . Ces dispositions sont de deux types:

a) Celles dont les trois premiers élèves (avant les deux dernières filles) forment une bonne disposition d’ordre 3. Il s’agit du cadre bleu du haut:

Dispositions_possibles_classe_de_5_eleves_regroupement_2eme_cas_1er_sous_casb) Celle dont les trois premiers élèves ne forment pas une bonne disposition (cadre bleu du bas). Dans ce cas, les deux derniers de ces trois premiers élèves sont Garçon-Fille:

Dispositions_possibles_classe_de_5_eleves_regroupement_2eme_cas_2eme_sous_cas Et avant ce couple Garçon-Fille, on a un garçon tout seul qui lui, forme une bonne disposition d’ordre 1 !

Au final, pour trouver les bonnes dispositions d’ordre 5, il nous a fallu trouver les bonnes dispositions d’ordre 4, 3 et 1, qui sont respectivement au nombre de 7, 4 et 1. Et là, on voit que 7+4+1=12, ce qui est bien notre nombre de bonnes dispositions d’ordre 5. C’est cette idée que nous allons reprendre dans le cas général.

Cas général

Soit n un entier plus grand que 5 et on considère une rangée de n élèves telle que chaque fille donne la main à au moins une autre fille (comme précédemment, une telle rangée est appelée une bonne disposition). On note d_n le nombre de bonnes dispositions pour une rangée de n élèves. On a vu que d_1=1, d_2 = 2, d_3=4, d_4=7 et d_5=12.

Dans le cas d’une rangée de n élèves, il y a deux cas disjoints possibles:

• 1er cas: Soit la rangée se termine par un garçon,  et, dans ce cas, la rangée formée des  n-1 premiers élèves est donc elle-même une bonne disposition (on peut aussi voir ça en disant que si on a une bonne disposition avec n-1 élèves alors, en ajoutant un garçon à la fin, chaque fille donnera toujours la main à au moins une autre fille).

Dispositions_possibles_cas_general_1er_casDonc, dans ce cas, le nombre de possibilités est de d_{n-1}.

• 2ème cas: Soit la rangée se termine par au moins deux filles et alors il faut réfléchir un peu… car il y a deux sous-cas:

Sous-cas n°1: soit la rangée formée des n-2 premiers élèves est une bonne disposition:

Dispositions_possibles_cas_general_2eme_cas_1er_sous-cas_et donc, cela donne d_{n-2} possibilités.

Sous-cas n°2: soit la rangée formée des n-2 premiers élèves n’est pas une bonne disposition. Et si ce n’est pas une bonne disposition, c’est qu’une fille est toute seule. Mais comme la rangée initiale de n élèves était une bonne disposition, s’il y a une fille seule après avoir coupé la rangée, c’est nécessairement la fille qui est située à la position n-3. Comme elle est seule, c’est qu’avant il y a un garçon. Et avant ce garçon, il y a donc une bonne disposition (d’ordre n-4):Dispositions_possibles_cas_general_2eme_cas_2eme_sous-casDonc ce sous-cas nous donne d_{n-4} possibilités.

Au final, puisque tous ces cas sont disjoints, nous avons donc la belle formule suivante:

\boxed{ \vphantom{\dfrac{a}{b}} d_n = d_{n-1} + d_{n-2} + d_{n-4} }

(Qu’est-ce qu’il peut y avoir comme belles formules dans ce blog… ou alors c’est moi qui trouve tout beau dans les maths…)

Classe de 30 élèves

Pour répondre au problème initial, il suffit maintenant d’écrire un programme  (ou bien de se taper les calculs à la main, ce qui n’est pas si long) qui utilise la relation de récurrence précédente. Pour une classe de 30 élèves, on obtient 15 346 786 façons de disposer les enfants en ligne de sorte que chaque fille donne la main à une autre fille. De toute façon, la maîtresse n’a pas eu à choisir parmi toutes ces possibilités puisqu’elle a finalement décidé de les aligner par ordre alphabétique.

Sources:

Binary sequences without isolated ones, Richard AUSTIN & Richard GUY

– L’idée d’appliquer cela à des élèves qui se donnent la main se trouve dans le livre The Book of Numbers de John Conway et Richard Guy.

Publicités
Cet article, publié dans Dénombrement, est tagué , , , . Ajoutez ce permalien à vos favoris.

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s