1

I got this question:

In the famous Atlantis city BlackWhite the houses have five levels and each level is painted either by black or by white paint, but two adjacent floors can’t be both black or they would anger the gods.
(It is allowed to have adjacent white stories.)
a) How many different ways are there to paint a house in BlackWhite?
b) Try and find the different permutations for a certain number of levels per house.
Do you spot a pattern?
c) Explain why this pattern exists.

a) and b) are quite simple -- a) requires a simple tree diagram and b) requires a little bit of thinking:

1)      B               W                   2
        |              / \
        |             /   \
        |            /     \
        |           /       \
        |          |         \
        |          |          \
        |          |           \
        |          |            |
2)      W          B            W           3
       / \         |            |
      /   \        |           / \
     |     |       |          /   \
     |     |       |         /     \
3)   B     W       W        B       W       5
     |    / \     / \       |      / \
4)   W   B   W   B   W      W     B   W     8
    / \  |  / \  |  / \    / \    |  / \
5) B   W W B   W W B   W  B   W   W B   W   13

You can trace the lines for a), and find the pattern for b): 2, 3, 5, 8, 13. It's the Fibonacci sequence! You can generalise how many possibilities there are per story if s is the number of stories with the Binet formula: $$\frac {(\phi)^{s+2} - (\frac {-1}{\phi})^{s+2}}{\sqrt 5}$$ But I still can't see why this house problem, along with other problems I've seen like the rabbit problem, or Dudeney's cows all link to the Fibonacci sequence!

DanielWainfleet
  • 57,985
Leo
  • 89
  • 4
    Think about this: every time you have a black floor, you need a white floor next. So, you can either add a white floor, or a tuple of black, white floor. So, this is similar to the problem, you have an $n$-length chocolate bar, and you can take bites of length $1$ or $2$ every time. How many ways are there to eat the bar? If you write the recursion for this problem, you'll see it's that of the Fibonacci sequence. – Rushabh Mehta Jan 25 '21 at 14:37
  • We have this question many times on the site but I can't find it. It is usually presented as tiling as Don Thousand presents it. – Ross Millikan Jan 25 '21 at 15:12
  • Yes -- it's true! – Leo Jan 25 '21 at 15:50
  • My edit was to correct the Binet formula. I think you merely made a typo. – DanielWainfleet Jan 25 '21 at 17:29
  • thanks! It was a typo :-) – Leo Jan 25 '21 at 18:13

1 Answers1

2

We are going to define three sequences, $(B_n), (W_n), (C_n)$, counting respectively the number of ways to colour the $n$ first level with the last one being coloured in Black, in White, or as we want.

We clearly have $B_n + W_n = C_n$

Now, notice that we have some equalities:

  • $B_n = W_{n-1}$ (because you must have a White level before a Black one, and you can always a Black one on top of a White one).
  • $W_n = B_{n-1} + W_{n-1}$ (simply counting them by splitting your $n$-levels colouring in two groups, depending on whether the $n-1$-th level was Black or White)
  • $W_n = C_{n-1}$ This is because you have no restriction on what comes before or after a White level.

Combining those equations, we get (using them in order):

$C_n = B_n + W_n = W_{n-1} + W_n = W_{n-1} + (B_{n-1} + W_{n-1}) = W_{n-1} + (B_{n-1} + C_{n-2}) = C_{n-1} + C_{n-2}$

This is the equation defining the Fibonnaci sequence. It is easy to compute $C_0, C_1$ and see how they are related !

Numbra
  • 995
  • 4
  • 10