4. Given a board $2016 \times 2016$. For what smallest $k$ can the cells of the board be colored in $k$ colors such that
1) one of the diagonals is painted in the first color;
2) cells symmetric with respect to this diagonal are painted in the same color;
3) any two cells located in the same row on opposite sides of the cell of the first color are painted in different colors (the cells do not necessarily have to be adjacent to the cell of the first color).
Answer: 11.

Solution. Let the cells of the diagonal running from the top left corner to the bottom right corner be painted in the first color. Denote by $C_{i}$ the set of colors in which the cells of the $i$-th row, located to the left of the diagonal of a single color, are painted. We will prove that $C_{i} \neq C_{j}$ for $i<j$. Indeed, the cell located in the $i$-th row and $j$-th column has a color not included in $C_{i}$. But the cell located in the $j$-th row and $i$-th column is painted in the same color, and its color is included in $C_{j}$. Thus, the sets $C_{1}, C_{2}, \ldots, C_{2016}$ are different subsets of the set $\{1,2, \ldots, k\}$. Then there are no more than $2^{k}$ of them. Therefore, $k \geqslant 11$.

By induction, we will show how to paint the board $2^{k} \times 2^{k}$ in $k$ colors as required. This will be sufficient, since by leaving only the rows from 1 to 2016 and the columns from 1 to 2016, we will obtain a $2016 \times 2016$ board with the required coloring.

Base case $k=1$ is obvious, since a $2 \times 2$ board can be painted in one color. Inductive step from $k$ to $k+1$. If we already know how to paint a $2^{k} \times 2^{k}$ board as required, then we will paint a $2^{k+1} \times 2^{k+1}$ board as follows: place two copies of the $2^{k} \times 2^{k}$ board, one in the top left corner and the other in the bottom right corner, and paint the remaining cells in the $(k+1)$-th color.