@The-Blade-Dancer Sure!
Let's take a quick look at the question statement again. 🙂
We're trying to create a line of \(6\) beads, either black or white, and the only constraint is that we can have at most two consecutive white beads.
M3W3D11-y-part-4-xiao-ma-forum-ok-not-ok.png
Earlier, in Parts 1 through 3, Prof. Loh showed us a solution using recursion (building upon a smaller line of beads in order to get the next bigger string). In Part 4, he's going to resurrect a method that he introduced in Day 10, tiling. It's a remarkably different but totally valid way of doing this problem. Pretend you had a set of tiles which consisted of three types: 1.) a single black square; 2.) a white square followed by a black square; and 3.) two white squares followed by a black square. Pretend that they have letters on them to denote which way is up, so that, when placed down, the white square is always to the left of the black square.
M3W3D11-y-part-4-xiao-ma-forum-tiles-rotated.png
When arranged in a line right-side-up, the tiles magically produce a string of black and white "beads" which obey the rules of the problem which we are trying to solve!
M3W3D11-y-part-4-xiao-ma-forum-one-way.png
...but is this any easier, though, than what we did before?
....well, the answer is yes! 🙂
You see, these tiles above are colored black and white, but we actually don't have to color them black and white. We can think of them as "blind" tiles. Or, rather, that we are blind to the tiles. This is because only the length of the tile really matters. The single square is always black. The \(2\)-length rectangle always has white on the left, black on the right. And the \(3\)-length rectangle always has two whites on the left with one black on the right.
M3W3D11-y-part-4-xiao-ma-forum-blind-tiles.png
$$ \text{ Blind tiles. } $$
Okay, we're in good shape now! Now we don't even have colors anymore! Amazing; how did that happen? Now all we have to worry about is the length of the tiles and how to assemble \(6\) of them in a line.
In order to make a \(6\)-length line, we can start with a \(5\)-length line and add a \(1 \times 1\) square, we can start with a \(4\)-length line and add a \(1 \times 2\)-rectangle, or we can start with a \(3\)-length line and add a \(1 \times 3\)-rectangle.
Remember this? 🙂 This recursion illustration hopefully looks familiar by now.
M3W3D11-y-part-4-recursion-with-tiles.svg.png
We're still not caring anymore about whether the individual squares (beads, in reality) plastered together inside the rectangular tiles are black or white. We just think of them as \(1 \times 1\) tiles, \(1 \times 2\) tiles, and \(1 \times 3\) tiles.
In general, the formula for the number of ways to make a line of length \(n\), for this problem, is
$$ a_n = a_{n-1} + a_{n-2} + a_{n-3} $$
which, again, isn't Fibonacci either, but it's very similar!
From there, you can calculate the ways to make a string of length \(n\) if \(n\) is very small, and then use the recursion to work your way up to finding \(a_6\) for a string of length \(6.\)
🙂
