4. Each cell of a $2 \times 13$ table is to be colored with exactly one of four colors. In how many ways can this be done so that no two adjacent cells are colored the same? (We consider two cells to be adjacent if they share a common side.)

(Jaroslav Švrček)
SOLUTION. The cells of the first column of the table can be colored in $4 \cdot 3=12$ ways under the given conditions. The adjacent column can then be colored in $3^{2}-2$ ways according to the problem statement, because each cell in it can be colored with one of the three remaining colors with respect to the adjacent column, from the total number of $3^{2}$ possibilities, we must subtract the two cases where we would have two identically colored cells one below the other in this column (these are precisely the two colors not used in the first column).

Analogously, we can continue to color the subsequent columns, with each of them again having $3^{2}-2$ possibilities. We then multiply the number of possibilities for each column to get the total number of ways to color the entire table as required.

Conclusion. In total, there are $12 \cdot\left(3^{2}-2\right)^{13-1}=12 \cdot 7^{12}$ ways to color the cells of the $2 \times 13$ table in the required manner.

## GUIDING AND ADDITIONAL PROBLEMS:

N1. In how many ways can the cells of a $2 \times 3$ table be colored using two different colors such that each cell is colored with one color? [For each cell in the table, there are always 2 coloring options, so for the entire table, we have $2^{6}=64$ possibilities.]

N2. Each cell of a $13 \times 13$ table is to be colored with one of two colors. In how many ways can this be done so that no two adjacent cells are colored the same? [2 possibilities.]

N3. Each cell of a $2 \times 2$ table is to be colored with one of three colors. In how many ways can this be done so that no two adjacent cells are colored the same? [For coloring the first two adjacent cells, we have 6 possibilities, and for the remaining cells, we have 3 possibilities, making a total of $6 \cdot 3=18$ possibilities.]

D1. Determine in how many ways the cells of a $3 \times 3$ table can be colored with three different colors (each cell with one color) such that all three colors are used in each row and each column. [There are 12 possibilities. The first column can be colored in $3 \cdot 2=6$ ways, for the second column, we have only 2 possibilities given the conditions of the problem. The coloring of the cells in the last, third column is then uniquely determined. Thus, we have $3 \cdot 2 \cdot 2=12$ possibilities in total.]