Mauvais voisins
LE DÉFI
Dans une rue comportant 10 maisons, un groupe de personnes ne peut pas habiter côte à côte. De combien de façons ces personnes peuvent-elles y vivre de sorte qu'aucune de leurs maisons voisines ne soit occupée par l'une d'elles ? On compte parmi les possibilités le cas où toutes les maisons sont vides.

EXPLORATION
Combien y a-t-il de façons de construire 15 maisons ? Trouvez une régularité qui vous permettra de calculer rapidement le nombre de façons différentes pour un plus grand nombre de maisons.
Remarques
LE DÉFI ET L'EXPLORATION
Comme pour beaucoup d'énigmes, le meilleur moyen d'apprendre est de faire des exemples simples en cherchant des régularités. Utilisez E pour case vide et B pour case voisine indésirable.
- 1 maison – 2 voies : E ou B
- 2 maisons – 3 voies : EE, BE, EB
- 3 maisons – 5 façons : EEE, BEE, EBE, EEB, BEB
- 4 maisons – 8 voies : EEEE, BEEE, EBEE, EEBE, EEEB, BEBE, BEEB, EBEB
Il semblerait qu'il s'agisse des nombres de Fibonacci. Essayons de trouver une bonne raison à cela.
Pour trouver le nombre de façons de remplir n maisons, commencez par un E ou un B.
- Si vous commencez par un E, alors les n-1 maisons suivantes peuvent être remplies en ignorant cette première maison.
- Si vous commencez par un B, la maison suivante doit être un E. Après ces deux-là, les n-2 maisons suivantes peuvent être remplies en ignorant les deux premières.
Par conséquent, le nombre de façons de remplir n maisons est égal au nombre de façons de remplir n-1 maisons plus le nombre de façons de remplir n-2 maisons. C'est précisément la règle pour calculer la suite de Fibonacci. Puisque nous commençons par 2 et 3, cette règle garantit que tous les nombres suivants sont identiques.
Les nombres seront : 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 pour les dix premiers.