National Olympiad of Argentina

For an admissible coloring let the 13-cell shape shown in the figure be entirely inside the table. Observe that the central row of 5 represents all 5 colors, as well as the central column of 5. Assume on the contrary that the central row misses color 1. Since the crosses centered at a, b, c contain color 1, this color occurs 3 times in the union of the two rows of 3 above and under abc. This union is covered by the two crosses centered at the cells • adjacent to b. However these crosses combined represent each color at most twice. The claim is proven.



We argue for a general $n\times n$ square where $n>5$. Every 5 consecutive cells in rows 3, 4, ..., $n-2$ form the central row of 5 in a shape like above, so they represent all 5 colors. The same holds for every 5 consecutive cells in columns 3, 4, ..., $n-2$. Hence the coloring of the rows and columns mentioned is periodic with period 5. Write $a_{ij}$ for the cell in row $i$ and column $j$, "cross $a_{ij}$" for the cross centered at $a_{ij}$ and $a_{ij}=c$ if $a_{ij}$ has color $c$. Note that any two adjacent cells not at the border of the table are contained in some cross, so they are colored differently.

Fix the colors of the first 5 cells in row 3 and the second cell in row 2. Cells $a_{31},a_{32},a_{33},a_{34},a_{35}$ have different colors, label them 1, 2, 3, 4, 5. The color of $a_{22}$ is not arbitrary: one infers from

cross $a_{32}$ that $\{a_{22},a_{42}\}=\{4,5\}$. Let $a_{22}=4$, $a_{42}=5$, the case $a_{22}=5$, $a_{42}=4$ is analogous. We show that then the entire coloring is determined apart from the colors of 3 cells at each corner: the vertex cell and its two neighbors by side. Call $F$ the figure obtained by ignoring these 12 cells. The coloring of row 3 is determined: $1,2,3,4,5,1,2,3,4,5,\dots$. By considering cross $a_{33}$ we find $\{a_{23},a_{43}\}=\{1,5\}$; since $a_{42}=5$ and $a_{42}\ne a_{43}$, it follows that $a_{23}=5$, $a_{43}=1$. The same argument for crosses $a_{34}$ and $a_{35}$ shows that $a_{24}=1$, $a_{44}=2$, $a_{25}=2$, $a_{45}=3$. The colors of 4 consecutive cells in row 4 are known now, from the second to the fifth, so row 4 has coloring $4,5,1,2,3,4,5,1,2,3,\dots$. The remaining crosses centered in row 3 determine the colors in row 2 without its first and last cell: $4,5,1,2,3,4,5,1,2,3,\dots$. After this consider the crosses centered at row 2 except $a_{22}$ and $a_{2,n-1}$. They determine the colors in row 1 without its first two and last two cells: $2,3,4,5,1,2,3,4,5,1,\dots$. Once the coloring of row 4 is known, we proceed analogously to rows $5,\dots ,n-2$ to achieve the same. For the next-to-last row $n-1$ the colors are determined uniquely except for the first and the last cell. For the last row $n$ we use the crosses in row $n-1$ different from $a_{n-1,2}$ and $a_{n-1,n-1}$. This yields the colors in row $n$ apart from the ones of the first two and the last two cells. Thus the coloring of figure $F$ is indeed completely determined. There remain the three cells at each corner. We infer from cross $a_{22}$ that $\{a_{12},a_{21}\}=\{1,3\}$, and the two possibilities for $a_{12}$ and $a_{21}$ are feasible as there are no more restrictions on their colors. Likewise there are 2 possibilities for the colors of the analogous pairs at the other three corners. As for the colors of the 4 vertex cells, there are no restrictions at all. Initially we fixed the colors of $a_{31},a_{32},a_{33},a_{34},a_{35}$ and $a_{22}$ which can be done in $5!\cdot 2$ ways. Then there are 2 choices for the coloring of the pair $a_{12},a_{21}$ and 2 choices for each analogous pair at the corners. Last, there are 5 choices for the color of each vertex cell. Every combination of the choices described yields a coloring with the stated property. Therefore the number of admissible colorings is $5!\cdot 2\cdot 2^4\cdot 5^4=4!\cdot 10^5=2400000$.