José wants to fill the cells of a $2 \times n$ board with zeros and ones in such a way that two adjacent identical numbers in the same row prevent the corresponding cells in the other row from also being filled with identical numbers. For example, in the diagram below, the values of $A$ and $B$ cannot be the same.

| 0 | 1 | 0 | $\cdots$ | 1 | 1 | $\cdots$ |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- |
| 1 | 1 | 0 | $\cdots$ | $A$ | $B$ | $\cdots$ |

a) Find all possible fillings of the board below:

| 0 | 0 | 1 |
| :--- | :--- | :--- |
| 1 |  |  |

b) In the board, all columns are already filled except the last two. In how many ways can the numbers in cells $A$ and $B$ be chosen?

| $\cdots$ | 0 | $A$ |
| :--- | :--- | :--- |
| $\cdots$ | 1 | $B$ |

c) In how many ways can José fill the board if $n=2020$?
Solution

a) We have the fillings:

| 0 | 0 | 1 |
| :--- | :--- | :--- |
| 1 | 0 | 0 |


| 0 | 0 | 0 |
| :--- | :--- | :--- |
| 1 | 0 | 1 |


| 0 | 0 | 1 |
| :--- | :--- | :--- |
| 1 | 0 | 1 |

b) Initially, there are 2 possible choices for $A$ and 2 possible choices for $B$. Only the choice $A=0$ and $B=1$ is forbidden. Therefore, there are 2.2-1 = 3 possible choices.
c) Starting to fill from left to right, there are 4 possible types of columns, and the rules boil down to not filling a certain column with the same configuration as the immediately preceding column. Thus, once José has chosen the numbers for a column, he has 3 options for filling the next one. At the beginning, we can freely choose how to fill the leftmost column and then continue choosing the others from left to right. By the Multiplication Principle, the total number of fillings is:

$$
4 \cdot 3 \cdot 3 \cdots \cdots 3=4 \cdot 3^{2019}
$$