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:
Vous 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:
et pour une classe de deux élèves, ce sont:
Avant 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:
Classe de 5 élèves
Voici les 12 bonnes dispositions qu’on obtient pour une classe de 5 élèves:
On 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:
On 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:
2) 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:
b) 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:
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 
Dans le cas d’une rangée de
• 1er cas: Soit la rangée se termine par un garçon, et, dans ce cas, la rangée formée des 
Donc, dans ce cas, le nombre de possibilités est de 
• 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 
et donc, cela donne 
Sous-cas n°2: soit la rangée formée des 
Donc ce sous-cas nous donne 
Au final, puisque tous ces cas sont disjoints, nous avons donc la belle formule suivante:
(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.
Blogdemaths 