5. Let $p$ be a prime number. How many colors are needed at minimum to place tokens on a square $p \times p$ board, each token being colored with one of these colors, so that each field of the board has exactly one token and there are no two tokens of the same color that attack each other? Two tokens attack each other if they are on the same row, column, or if the line connecting them is parallel to one of the diagonals of the square.
Solution. It is not hard to check that for $p=2$ the solution is 4, and for $p=3$, the solution is 5. Let $p>3$. To each cell of the board, we will assign coordinates $(i, j)$, which means that the cell is in the $i$-th row, counting rows from top to bottom, and in the $j$-th column, counting columns from left to right. The cells with coordinates $(i, i)$ will be said to form the main diagonal of the board, and the other diagonal will be called the secondary diagonal. On each of the cells $(i, i)$ of the main diagonal, we will place tokens of $p$ different colors numbered $0,1,2, \ldots, p-1$ - the possible remainders upon division by $p$. Then, in each row, we fill in the cells cyclically, placing in each next cell a number that is 2 greater than the number in the previous cell. In this way, after $p-2$ come $0,2,4, \ldots$, and after $p-1$ come $1,3, \ldots$.

Thus, in the cell with coordinates $(i, j)$, we place a token whose color is marked by the number which is the remainder upon division of the number $i+2(j-i)=2j-i$ by the number $p$. Since $p$ is a prime number greater than 3, it is odd, so it is clear that in each row, $p$ colors will be represented, meaning that tokens of the same color will not be present.

If in column $j$ two tokens of the same color are encountered, for example in rows $m$ and $n (m>n)$, then the numbers $2j-m$ and $2j-n$ give the same remainder upon division by $p$, so their difference will be divisible by $p$. It follows that $m-n$ is divisible by $p$, which is not possible since $m$ and $n$ are less than $p$. Therefore, in no column can two tokens of the same color be encountered.

From the placement of the tokens, it is obvious that in diagonals parallel to the main diagonal, it is not possible for two tokens of the same color to be present.

If two cells are on the secondary diagonal or on a diagonal parallel to the secondary diagonal, then the sums of their coordinates are mutually equal. Assuming that on the cells with coordinates $(m, k-m)$ and $(n, k-n)$ there are tokens of the same color, it follows that the numbers $2(k-m)-m$ and $2(k-n)-n$ give the same remainder upon division by $p$. This means that $2k-3m$ and $2k-3n$ give the same remainder upon division by $p$, from which it follows that $3(m-n)$ is divisible by $p$. However, $p$ is coprime with both 3 and $m-n$, so it is not possible for $3(m-n)$ to be divisible by $p$.

Finally, it follows that if $p>3$, then there is an arrangement of tokens of $p$ colors that satisfies the condition of the problem, so $p$ is the smallest number of colors.