Question 36
José wants to fill a $2\times n$ board with zeros and ones so that if two adjacent entries in one row are equal, the corresponding two entries in the other row cannot also be equal. For example, in the diagram below, $A$ and $B$ cannot be equal.
| 0 | 1 | 0 | $\cdots$ | 1 | 1 | $\cdots$ |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- |
| 1 | 1 | 0 | $\cdots$ | $A$ | $B$ | $\cdots$ |
a) Find all fillings of the following board:
| 0 | 0 | 1 |
| :--- | :--- | :--- |
| 1 | | |
b) All columns of the board have already been filled except the last two. In how many ways can the entries in squares $A$ and $B$ be chosen?
| $\cdots$ | 0 | $A$ |
| :--- | :--- | :--- |
| $\cdots$ | 1 | $B$ |
c) In how many ways can José fill the board if $n=2020$?
| 0 | 1 | 0 | $\cdots$ | 1 | 1 | $\cdots$ |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- |
| 1 | 1 | 0 | $\cdots$ | $A$ | $B$ | $\cdots$ |
a) Find all fillings of the following board:
| 0 | 0 | 1 |
| :--- | :--- | :--- |
| 1 | | |
b) All columns of the board have already been filled except the last two. In how many ways can the entries in squares $A$ and $B$ be chosen?
| $\cdots$ | 0 | $A$ |
| :--- | :--- | :--- |
| $\cdots$ | 1 | $B$ |
c) In how many ways can José fill the board if $n=2020$?