Any Solution $?$

So far I have an upper bound of $n = 25$, color cell $C(i, j)$ with color $i$. I’m trying to prove this inductively, with a $k \times k$ board instead. I’m trying to prove that this is the lower bound.

Anyone??

We show that $n=13$ colors are necessary and sufficient. 13 colors are sufficient: Use the residual classes $0,\ldots,12$ modulo $13$ as colors. Cell $C(i,s)$ receives the color $\lfloor\frac12(i+s)\rfloor$ modulo $13$, where $\lfloor x\rfloor$ denotes the largest integer less or equal $x$. (Note that the color classes form diagonal stripes.) Suppose for the sake of contradiction that for some $1\le i<j\le25$ and $1\le s<t\le25$ the three cells $C(i,s)$, $C(j,s)$, $C(j,t)$ all would receive the same color. Here are two easy observations: (1) Since $\lfloor\frac12(i+s)\rfloor=\lfloor\frac12(j+s)\rfloor$ modulo $13$, and since $0<\frac12(j-i)\le12$, we get $\lfloor\frac12(i+s)\rfloor=\lfloor\frac12(j+s)\rfloor$. (2) An analogous argument yields $\lfloor\frac12(j+s)\rfloor=\lfloor\frac12(j+t)\rfloor$. These two observations imply $\lfloor\frac12(i+s)\rfloor=\lfloor\frac12(j+t)\rfloor$. But $i+1\le j$ and $s+1\le t$ yield $\lfloor\frac12(i+s)\rfloor<\lfloor\frac12(j+t)\rfloor$, the desired contradiction. 13 colors are necessary: We argue that no color can occur in more than $50$ cells. Then the total number of colors is at least $25^2/50>12$, and we are done. Hence fix an arbitrary color (say blue) in an arbitrary coloring of the desired form, and let $b$ denote the total number of blue cells. Consider a row $r$ that contains at least two blue cells, and let $i_1<i_2<\cdots<i_{\ell}$ denote the column indices of these blue cells. For $p=1,\ldots,\ell-1$ draw a horizontal arrow from cell $C(r,i_p)$ to cell $C(r,i_{p+1})$. Similarly put vertical arrows between consecutive blue cells in columns with at least two blue cells, but orient them from larger indices towards smaller indices. Note that no blue cell has two or more out-going arrows, since otherwise the forbidden configuration would occur. Therefore the total number $a$ of arrows satisfies $a\le b$. Denote by $r_k$ (respectively $c_k$) the number of blue cells in the $k$th row (respectively $k$th column). Then $b=\sum_{k=1}^{25}r_k=\sum_{k=1}^{25}c_k$. Note that the $k$th row contains at least $r_k-1$ arrows, and hence the total number of arrows in all rows is at least $\sum_{k=1}^{25}(r_k-1)$. Similarly, the total number of arrows in all columns is at least $\sum_{k=1}^{25}(c_k-1)$. This implies $$ b ~\ge~ a ~\ge~ \sum_{k=1}^{25}(r_k-1) + \sum_{k=1}^{25}(c_k-1) ~=~ 2b-50,$$which yields the desired bound $b\le50$.

But there can be a color that occured in more than 50 cells due to your construction (since 12*50=600<25^2)

I don't think the construction wprks though, try i=1,j=25,s=3,t=4

take modulo 13 and your proof and construction shows that the answer is 13(?)

Yes the answer in the official solution is also $13$.