11.6. On a grid board of size $2 \times n$ cells, some cells are painted black. A coloring is called correct if there are no two adjacent cells among the painted ones. (Adjacent are cells that share a common side.) A coloring in which no cell is painted is also considered correct.

Let $A_{n}$ be the number of correct colorings with an even number of painted cells, and $B_{n}$ be the number of correct colorings with an odd number of painted cells. Find all possible values of $A_{n}-B_{n}$.
Answer: $\pm 1$.

Solution. Consider two types of grid boards: a regular board $F_{n}$ of size $2 \times n$, and a board $G_{n}$ of size $2 \times n$ with one corner cell removed. In addition to the quantities $A_{n}$ and $B_{n}$, introduce the quantities $C_{n}$ and $D_{n}$ - the number of correct colorings of the board $G_{n}$ with an even and odd number of colored cells, respectively.

Cells will be numbered as in chess: $a_{i}, b_{i}$, where $a, b$ are letters corresponding to rows, and $i \in\{1, \ldots, n\}$ are column numbers. Suppose on the board $F_{n}(n \geq 2)$ an even number of cells are correctly colored. The set of such colorings is divided into three subsets: 1) cell $a_{n}$ is colored, 2) cell $b_{n}$ is colored, 3) neither of the cells $a_{n}, b_{n}$ is colored.

If cell $a_{n}$ is colored, then cells $a_{n-1}$ and $b_{n}$ must be uncolored, and among the remaining cells, an odd number must be correctly colored. Thus, the number of colorings corresponding to case 1) (and also case 2)) is $D_{n-1}$.

If neither of the cells $a_{n}, b_{n}$ is colored, then among the remaining cells, an even number must be correctly colored. The number of such colorings is $A_{n-1}$. In the end, we get

$$
A_{n}=A_{n-1}+2 D_{n-1}
$$

By similar reasoning, we get

$$
\begin{gathered}
B_{n}=B_{n-1}+2 C_{n-1} \\
C_{n}=A_{n-1}+D_{n-1} \\
D_{n}=B_{n-1}+C_{n-1}
\end{gathered}
$$

Let $P_{n}=A_{n}-B_{n}, Q_{n}=C_{n}-D_{n}$. Then, by subtracting the above equations, we get

$$
P_{n}=P_{n-1}-2 Q_{n-1}, \quad Q_{n}=P_{n-1}-Q_{n-1}
$$

Calculating the initial values $P_{1}=-1, Q_{1}=0$, we find sequentially

$$
\begin{array}{lrrrlr}
i & 1 & 2 & 3 & 4 & 5 \\
P_{i} & -1 & -1 & 1 & 1 & -1 \\
Q_{i} & 0 & -1 & 0 & 1 & 0 .
\end{array}
$$

From this point on, the sequence becomes periodic. From this, it is clear that the desired quantity $P_{n}$ takes only the values $\pm 1$.

## Criteria.

(-.) Correct answer based on several examples.

$(-/+)$ Correct answer with errors in the justification of the recursion.

(+/2) Correct answer with noticeable gaps in the justification of the recursion.

$(+/-)$ Correct answer (or $\{0,-2\})$ with minor flaws in the justification of the recursion.

(+.) The empty coloring is forgotten, resulting in the answer $\{0,-2\}$, otherwise everything is correct.

$(+)$ Correct answer with full justification.