Bad Neighbors
THE CHALLENGE
There are a group of people who cannot live next door to each other in houses along a street. If there are 10 houses, in how many ways can some of these people live in these houses so that no two neighboring houses have these people in them? Count having all the houses empty as one of the possibilities.
EXPLORATION
How many ways are there if there are 15 houses? Find a pattern that will help you quickly calculate how many different ways for larger numbers of houses.
Notes
THE CHALLENGE & EXPLORATION
As with so many puzzles, the best way to learn about this is by doing simple examples looking for patterns. Use E for empty and B for a bad neighbor.
- 1 house – 2 ways: E or B
- 2 houses – 3 ways: EE, BE, EB
- 3 houses – 5 ways: EEE, BEE, EBE, EEB, BEB
- 4 houses – 8 ways: EEEE, BEEE, EBEE, EEBE, EEEB, BEBE, BEEB, EBEB
It looks like they are the Fibonacci Numbers. Let’s find a good reason why that should be.
To find the number of ways to fill n houses, start with either an E or a B.
- If you start with an E, then the next n-1 houses can be filled ignoring that first house.
- If you start with a B, then the next house must be an E. After those two, the next n-2 houses can be filled ignoring the first two houses.
Therefore, the number of ways of filling n houses equals the number of ways of filling n-1 houses plus the number of ways of filling n-2 houses. This is exactly the rule for calculating the Fibonacci Numbers. Because we start with 2 and 3, the rule will force the rest of the numbers to be the same after that.
The numbers will be: 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 for the first ten.