A board of size $2013 \times 5$ (i.e., with 2013 rows and 5 columns) must be painted with the colors $A, B, C, D$. Some squares in the first row have already been painted, as shown in the figure below (the squares not represented in the figure have not been painted yet). To continue painting the board, we must follow this rule: adjacent squares (those that share a side or a vertex) cannot have the same color.

![](https://cdn.mathpix.com/cropped/2024_05_01_27f67f4520ebb8354fb2g-10.jpg?height=913&width=1053&top_left_y=697&top_left_x=410)

a) Describe the ways we can complete the painting of the first two rows.

b) In how many ways can we paint the entire board?

c) Describe the possible paintings for the 2013th row.
Solution

a) The house that is missing painting in the first row has neighbors painted with $B$ and $C$. Therefore, it can only be painted with $A$ or $D$. Let's analyze the case where it is painted with $A$, as shown in the figure below.

![](https://cdn.mathpix.com/cropped/2024_05_01_27f67f4520ebb8354fb2g-36.jpg?height=197&width=688&top_left_y=1626&top_left_x=587)

In this case, the house directly below the one we painted with $A$ can only be painted with $D$, as it has neighboring houses of colors $A, B$, and $C$. Painting it with $D$, we arrive at:

![](https://cdn.mathpix.com/cropped/2024_05_01_27f67f4520ebb8354fb2g-36.jpg?height=197&width=688&top_left_y=2057&top_left_x=587)

The house to the left of the house we painted with $D$, having neighbors of colors $B, A$, and $D$, can only be painted with $C$. The house to the right can only be painted with $B$. Thus, we arrive at:

1st row

2nd row

| $\mathrm{A}$ | $\mathrm{B}$ | $\mathrm{A}$ | $\mathrm{C}$ | $\mathrm{D}$ |
| :--- | :--- | :--- | :--- | :--- |
|  | $\mathrm{C}$ | $\mathrm{D}$ | $\mathrm{B}$ |  |

Finally, painting the remaining houses, we arrive at the painting:

1st row

2nd row

| $A$ | $B$ | $A$ | $C$ | $D$ |
| :---: | :---: | :---: | :---: | :---: |
| $D$ | $C$ | $D$ | $B$ | $A$ |

And if we had started with the color $D$ in the first house we painted? In that case, we would have arrived at

| 1st row | A | B | D | C | D |
| :--- | :---: | :---: | :---: | :---: | :---: |
| 2nd row | D | C | A | B | A |
|  |  |  |  |  |  |

Thus, these are the two possible paintings of the first two rows.

b) Continuing the painting we started in the previous item, we arrive at the two paintings for the first eight rows:

| 1st row | $\mathrm{A}$ | B | $\mathrm{D}$ | C | $\mathrm{D}$ | 1st row | A | $B$ | $A$ | $\mathrm{C}$ | $\mathrm{D}$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| 2nd row | $\mathrm{D}$ | $\mathrm{C}$ | A | B | A | 2nd row | $D$ | C | $\mathrm{D}$ | $\mathrm{B}$ | A |
| 3rd row | $\mathrm{A}$ | B | $\mathrm{D}$ | C | $\mathrm{D}$ | 3rd row | A | $B$ | A | $\mathrm{C}$ | $\mathrm{D}$ |
| 4th row | $\mathrm{D}$ | c | A | B | A | 4th row | $D$ | C | $D$ | $\mathrm{~B}$ | A |
| 5th row | $\mathrm{A}$ | B | $\mathrm{D}$ | C | $\mathrm{D}$ | 5th row | A | $B$ | A | $\mathrm{c}$ | $D$ |
| 6th row | $\mathrm{D}$ | $\mathrm{c}$ | A | B | A | 6th row | $\mathrm{D}$ | C | $\mathrm{D}$ | B | A |
| 7th row | $\mathrm{A}$ | B | $\mathrm{D}$ | C | $\mathrm{D}$ | 7th row | A | $B$ | A | C | $\mathrm{D}$ |
| 8th row | $\mathrm{D}$ | c | A | B | A | 8th row | $D$ | C | $\mathrm{D}$ | $\mathrm{B}$ | A |

Note that the pattern repeats every two rows. Following each of the cases, we conclude that there are only two possible paintings for the entire board.

c) As mentioned in the previous item, in each of the two possible cases, the painting of the rows repeats every two rows. Therefore, dividing 2013 by 2, we get $2013 = 1006 \times 2 + 1$. Thus, we conclude that the painting of the 2013th row is the same as the painting of the first row. Therefore, the two paintings that can appear in the 2013th row are:

![](https://cdn.mathpix.com/cropped/2024_05_01_27f67f4520ebb8354fb2g-37.jpg?height=106&width=443&top_left_y=2351&top_left_x=909)

and

![](https://cdn.mathpix.com/cropped/2024_05_01_27f67f4520ebb8354fb2g-37.jpg?height=109&width=451&top_left_y=2584&top_left_x=905)