Slechte Buren
DE UITDAGING
Er is een groep mensen die niet naast elkaar kunnen wonen in huizen aan een straat. Als er 10 huizen zijn, op hoeveel manieren kunnen sommige van deze mensen in deze huizen wonen, zodat er geen twee aangrenzende huizen zijn waar deze mensen wonen? Tel het feit dat alle huizen leeg staan mee als één van de mogelijkheden.

EXPLORATION
Op hoeveel manieren zijn er als er 15 huizen zijn? Zoek een patroon waarmee je snel kunt berekenen hoeveel verschillende manieren er zijn voor grotere aantallen huizen.
Notes
DE UITDAGING & VERKENNING
Zoals bij zoveel puzzels is de beste manier om dit te leren door eenvoudige voorbeelden te bekijken en naar patronen te zoeken. Gebruik E voor leeg en B voor een slechte buur.
- 1 huis – 2 mogelijkheden: Oost of Blauw
- 2 huizen – 3 manieren: EE, BE, EB
- 3 huizen – 5 manieren: EEE, BEE, EBE, EEB, BEB
- 4 huizen – 8 manieren: EEEE, BEEE, EBEE, EEBE, EEEB, BEBE, BEEB, EBEB
Het lijkt erop dat dit de Fibonacci-getallen zijn. Laten we eens kijken waarom dat zo zou zijn.
Om het aantal manieren te vinden waarop n huizen gevuld kunnen worden, begin je met een E of een B.
- Als je begint met een E, dan kunnen de volgende n-1 huizen worden gevuld, waarbij het eerste huis wordt genegeerd.
- Als je begint met een B, dan moet het volgende huis een E zijn. Na die twee kunnen de volgende n-2 huizen worden ingevuld, waarbij de eerste twee huizen worden genegeerd.
Het aantal manieren om n huizen te vullen is dus gelijk aan het aantal manieren om n-1 huizen te vullen plus het aantal manieren om n-2 huizen te vullen. Dit is precies de regel voor het berekenen van de Fibonacci-getallen. Omdat we beginnen met 2 en 3, zorgt de regel ervoor dat de rest van de getallen daarna gelijk zijn.
De getallen zijn: 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 voor de eerste tien.