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

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.

• If you have $n$ pairs of shaded squares and $21-2n$ unshaded squares, you can arrange them in ${21 - n \choose n}$ different ways on the strip. Then add these numbers up from $n=0$ to $n=10$. – Henry Apr 30 '14 at 22:27
• What? Sorry, I don't exactly understand what you mean. And by the way, the game has to be finished just in case I didn't make sense, so no two adjacent squares unshaded. – Parker Apr 30 '14 at 22:31
• Your second comment really ought to be edited into the question, as the solution is no longer Fibonacci numbers with $f(n)=f(n-1)+f(n-2)$ but essentially the Padovan numbers $f(n)=f(n-2)+f(n-3)$ – Henry Apr 30 '14 at 22:36

## 3 Answers

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

• Wow, I'm pretty sure that is correct because I did a few low numbers just to check. Thank you so much for all of your guy's help walking me through this! :) I don't know how you guys know all of this so quickly haha. – Parker Apr 30 '14 at 22:51

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$.

• I'm probably just not understanding something correctly, but think of 3 for example, wouldn't there only be two solutions? XXO And OXX ? Then for 4 squares there would be XXXX OXXO ? – Parker Apr 30 '14 at 22:38
• Use U for unshaded and S for shaded. For $3$, we have UUU, USS, and SSU. For $4$ there are UUUU, UUSS, USSU, SSUU, and SSSS. – André Nicolas Apr 30 '14 at 22:43
• With the changed question [no adjacent Us], UUU, UUUU, UUSS and SSUU would not be allowed. – Henry Apr 30 '14 at 22:47
• True, I answered the original question. The modified question yields to basically the same technique, and you have answered it, there is no reason for me to do so. – André Nicolas Apr 30 '14 at 22:54

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$.