The clock hand points to 12. Jack writes a sequence consisting of param 1 symbols, each symbol being plus or minus. After that he gives this sequence to a robot. The robot reads it from right to left. If he sees a plus he turns the clock hand $120^{\circ}$ clockwise and if he sees a minus he turns it $120^{\circ}$ counterclockwise. Find the number of sequences such that after the robot finishes the program the clock hand still points to 12.

| param1 | Answer |
| :---: | :---: |
| 11 | 682 |
| 12 | 1366 |
| 13 | 2730 |
| 14 | 5462 |
| 15 | 10922 |

Condition

The clock hand points to 12. Jack writes a sequence consisting of 11 symbols, each symbol being plus or minus. After that he gives this sequence to a robot. The robot reads it from right to left. If he sees a plus he turns the clock hand $120^{\circ}$ clockwise and if he sees a minus he turns it $120^{\circ}$ counterclockwise. Find the number of sequences such that after the robot finishes the program the clock hand still points to 12.

## Answer.
# Solution

Let $a_{n}$ be the number of sequences of length $n$ that result in the arrow pointing at 12 o'clock, and $b_{n}$ be the number of sequences of length $n$ that result in the arrow pointing at 4 or 8 o'clock. It is not difficult to understand that $a_{n+1}=2 b_{n}, b_{n+1}=a_{n}+b_{n}$. From this, we get that $b_{n+2}=b_{n+1}+2 b_{n}, a_{n+2}=a_{n+1}+2 a_{n}$. Since $a_{0}=1, a_{1}=0$, we can write the formula $a_{n}=\frac{2^{n}+2 \cdot(-1)^{n}}{3} \cdot$ In our case, we get the answer $a_{11}=682$.