Game With 21 Squares, How Many Possible Answers? Function Building

Question

We played this game in our math class, okay, I'll explain how it's played. There are 21 squares in a straight line across, the first person shades in 2 adjacent squares. The next player shades in 2 more adjacent squares. They continue taking turns until there are no more adjacent squares to shade in. The last player to play wins. That's how you play, but the question we got after was how many possible combinations of shaded and unshaded squares are there? He then introduced what he calls "function building" which is basically taking a more simple problem and keep adding onto it until you can find a function for it. I really would appreciate any help, and I hope I can learn from this!

Edit: I guess I forgot to include that for a solution to be considered a solution, it has to be a finished game, so no two adjacent squares are left unshaded.

Answer 1

With your requirement "the game has to be finished just in case I didn't make sense, so no two adjacent squares unshaded" then a long permitted sequence ends either

• with a permitted sequence followed by a shaded pair or
• with a permitted sequence followed by a shaded pair and an unshaded square

giving the recurrence $$a_n=a_{n-2}+a_{n-3}$$

Since it starts $1,1,2,\ldots$, this is the Padovan sequence, offset

Answer 2

Edit: Below is the answer to the original question, which has since been modified.

Let $a_n$ be the total number of patterns of shaded and unshaded squares, where the total number of squares is $n$.

We express $a_{n+1}$ in terms of previous $a_k$.

A pattern of length $n+1$ either (i) ends with an unshaded square or (ii) ends with $2$ shaded squares. There are $a_n$ patterns of type (i), and $a_{n-1}$ patterns of type (ii). It follows that $$a_{n+1}=a_n+a_{n-1}.$$ This is a very famous recurrence, the Fibonacci recurrence.

Note that $a_1=1$ and $a_2=2$. So $a_3=3$, $a_4=5$, $a_5=8$, and so on: We get the Fibonacci numbers. For details, please see the [Wikipedia article.] (http://en.wikipedia.org/wiki/Fibonacci_number) There is even an explicit formula for the number of patterns as a function of $n$.

Answer 3

You want the posibilities of having adyacent squares shaded, but no adyacent non-shaded squares (end positions of the game). Call the number of end positions when there are $n$ squares $e_n$. Clearly $e_1 = e_2 = 1$ and $e_3 = 2$.

Consider how you can make an end position for $n$ squares out of smaller ones. If the last square is shaded, it means $n$ and $n - 1$ are shaded, and before that comes a legal end position for $n - 2$. If the last is not shaded, then $n - 1$ and $n - 2$ are shaded, and before that comes a legal end position for $n - 3$. Adjusting indices for tidiness: $$ e_{n + 3} = e_{n + 1} + e_n \qquad e_1 = e_2 = 1, e_3 = 2 $$ Thus: $$ 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, ... $$ In particular, $e_{21} = 256$.