Mediterranean Mathematical Competition

The forbidden configuration is given by

For a $3 \times 3$ chessboard, the minimum number is given by 2. Indeed:

If we deal with a $5 \times 5$ chessboard, it is sufficient to consider 3 colours:

It seems that $m_n = \frac{n-1}{2}$ colours is sufficient for an $n \times n$ chessboard for any odd $n$. So we will prove that 13 colours are sufficient for the $25 \times 25$ chessboard. We consider the colours $\{1, 2, 3, \dots, 11, 12, 0\}$ and the chessboard coloured as:

which satisfies the condition at first sight. In fact, it is easy that $C[i, j] = \lfloor \frac{i+j}{2} \rfloor \pmod{13}$ for any $1 \le i, j \le 25$. So if the condition fails, then $C[i, s] = C[j, s] = C[j, t]$ for some $1 \le i < j \le 25$ and $1 \le s < t \le 25$, which implies that
$$\left\lfloor \frac{i+s}{2} \right\rfloor \pmod{13} = \left\lfloor \frac{j+s}{2} \right\rfloor \pmod{13} = \left\lfloor \frac{j+t}{2} \right\rfloor \pmod{13}.$$
From $C[i, s] = C[j, s]$ it is clear that $\left\lfloor \frac{j+s}{2} \right\rfloor = \left\lfloor \frac{i+s}{2} \right\rfloor$ since $0 \le \left\lfloor \frac{j+s}{2} \right\rfloor - \left\lfloor \frac{i+s}{2} \right\rfloor < \frac{j+s}{2} - \left(\frac{i+s}{2} - 1\right) = \frac{j-i}{2} + 1 \le \frac{24}{2} + 1 = 13$, so $\left\lfloor \frac{i+s}{2} \right\rfloor - \left\lfloor \frac{j+s}{2} \right\rfloor \le 12$ and the remainders must coincide. Analogously, from $C[j, s] = C[j, t]$ we have that $[\frac{j+s}{2}] = [\frac{j+t}{2}]$, so we conclude that $[\frac{i+s}{2}] = [\frac{i+t}{2}]$, which is impossible since
$$\left[ \frac{i+s}{2} \right] \le \frac{i+s}{2} \le \frac{j+t}{2} - 1 < \left[ \frac{j+t}{2} \right].$$

Now we prove that 13 colours are necessary. Fix a $25 \times 25$ chessboard with a configuration satisfying the condition. We fix any colour, for instance colour number 2. We will call 2-cells that ones which are coloured with colour number 2. The total number of 2-cells will be denoted by $c_2$. We delete all the colours and only remain 2-cells. From any 2-cell, we draw horizontal arrows from left to right and vertical arrows from down to up joining consecutive 2-cells. These arrows will be called 2-arrows.

Any 2-cell cannot have two or more out-going 2-arrows since otherwise the forbidden configuration would occur:

Therefore, the total number of 2-arrows $a_2$ satisfies $c_2 \ge a_2$. It is clear that in any row, if there are $k$ 2-cells, then there are $k-1$ 2-arrows in that row, so the total number of horizontal 2-arrows equals to $c_2 - 25$ because there are 25 rows. Analogously, looking at the columns, the total number of vertical 2-arrows also equals to $c_2 - 25$. So the total number of 2-arrows is $a_2 = 2(c_2 - 25)$ and we obtain $c_2 \ge a_2 \ge 2c_2 - 50$, so $c_2 \le 50$. Since there are $25 \times 25 = 625$ cells and $625/50 > 12$, we need at least 13 colours to get the configuration.