Why can't you use the fact that fₙ = 2fₙ₋₁ + 2fₙ₋₂ because it is the number of ways to tile a 1x7 strip?
-
Why can't you use the fact that \(f(n)=2f(n-1)+2f(n-2))\) because it is the number of ways to tile a \(1 \times 7\) strip using \(\fbox{B}, \fbox{R}, \fbox{W}\fbox{R}, \fbox{W}\fbox{B}?\) You get the recursion \(2, 6, 16, 44, 120, 328, 896,\) and then you divide it by \(2\) because it can end in \(W\) or \(B\) to get \(\fbox{448}\)
-
@spaceblastxy1428 Yes, great! That is also another way to solve this problem. Excellent!
It is clever to think of tiling a \( 1 \times 7 \) strip with \( \fbox{B}, \fbox{R}, \fbox{W}\fbox{R}, \text{ and } \fbox{W}\fbox{B}\) because here we don't have a single white tile; the whites are always stuck next to a non-white, so we are guaranteed to not have two whites side-by-side.
We can make a strip of length \(n\) by adding a \( \fbox{B} \text{ or } \fbox{R}\) to the end of a strip of length \( n-1.\) We don't have to worry about what the last colored bead is, since we aren't adding a white bead.
$$ \ldots \boxed{ n-4^{\text{th}}} , \boxed{ n-3^{\text{rd}}}, \boxed{ n-2^{\text{nd}}}, \boxed{n-1^{\text{st}}}, \fbox{B} $$
$$ \ldots \boxed{ n-4^{\text{th}}} , \boxed{ n-3^{\text{rd}}}, \boxed{ n-2^{\text{nd}}}, \boxed{n-1^{\text{st}}}, \fbox{R} $$
$$ \text{ 2 ways starting from length } n-1 $$
We could also make a strip of length \(n\) by adding a \( \fbox{W}\fbox{R} \text{ or } \fbox{W}\fbox{B}\) to the end of a strip of length \( n -2.\) This strip is \(n-2\) in length instead of \(n-1\) in length because the tile we are adding is \(2\) units long.$$ \ldots \boxed{ n-5^{\text{th}}} , \boxed{ n-4^{\text{th}}} , \boxed{ n-3^{\text{rd}}}, \boxed{ n-2^{\text{nd}}}, \fbox{W}\fbox{R} $$
$$ \ldots \boxed{ n-5^{\text{th}}} , \boxed{ n-4^{\text{th}}} , \boxed{ n-3^{\text{rd}}}, \boxed{ n-2^{\text{nd}}}, \fbox{W}\fbox{B} $$
$$ \text{ 2 ways starting from length } n - 2 $$
This is expressed by the recursive formula
$$ f_n = 2 f_{n-1} + 2f_{n-2} $$
or $$ f_n = 2 \left( f_{n-1} + f_{n-2} \right) $$
where \( f_n = \) ways to make a sequence of \(n\) beads, \( f_{n-1} = \) ways to make a sequence of \( n-1\) beads, and \( f_{n-2} = \) ways to make a sequence of \(n-2\) beads.
Now we just need to find the number of strips for the small cases, since the recursive formula doesn't work for very small \(n.\)
-
For \(n = 1, \text{ a } \text{ } 1 \times 1 \) strip:
There are \(2\) ways: \(\fbox{R} \text{ or } \fbox{B}.\)
-
For \(n = 2, \text{ a } \text{ } 1 \times 2 \) strip:
There are \(6\) ways:
$$ \fbox{R}, \fbox{R} $$
$$ \fbox{R}, \fbox{B} $$
$$ \fbox{B}, \fbox{R} $$
$$ \fbox{B}, \fbox{B} $$
$$ \fbox{W}\fbox{R} $$
$$ \fbox{W}\fbox{B} $$
Now we have enough values to start our recursion.
$$\begin{aligned} f_3 &= 2 \left( f_2 + f_1 \right) \\ &= 2( 2 + 6) \\ &= 16\\ \\ f_4 &= 2 \left( f_3 + f_2 \right) \\ &= 2 (16 + 6) \\ &= 44\\ \\ f_5 &= 2\left( f_4 + f_3 \right) \\ &= 2(44 + 16) \\ &= 120 \\ \\ f_6 &= 2 \left( f_5 + f_4 \right) \\ &= 2 (120 +44 ) \\ &= 328 \\ \\ f_7 &= 2 \left( f_6 + f_5 \right) \\ &= 2(328 + 120) \\ &= 2 \times 448 \\ \\ \end{aligned} $$Thus \(2 \times 448 \) is the number of \(1\times 7\) strips, but we want the number of \(1 \times 6\) strips, so what should we do now? There are some copies that we should throw away. These copies have the same first \(6\) beads as another way, with only the last bead being different.
$$ \ldots \boxed{ S} , \boxed{ A} , \boxed{ M} , \boxed{ E}, \boxed{ \text{ beads} }, \fbox{W} $$
$$ \ldots \boxed{ S} , \boxed{ A} , \boxed{ M} , \boxed{ E}, \boxed{ \text{ beads} }, \fbox{B} $$Removing the last bead of each string would give us the same \(1 \times 6\) beads. There is no restriction on \(W\) or \(B,\) so there are equal numbers of strings ending in \(W,\) and equal numbers of strings ending in \(B.\) Thus we want half of the number of \(1 \times 7\) strips, and the answer is
\( \frac{2 \times 448 }{2} = \boxed{448 \text{ ways }} \) to color 6 beads black, white or red if two whites cannot be next to each other.
-
