SAUDI ARABIAN MATHEMATICAL COMPETITIONS

1) We will count value $S$, the number of the tuples $(A,B,C)$ with column $A,B$ and row $C$ in relation $A-C,B-C$ intersect at the colored cell.

First way, denote $x_i$ as the number of colored cells on the $i$th row, then $$S=\sum _{i=1}^{p^2+p+1}\left(\genfrac{}{}{0ex}{}{x_i}{2}\right).$$

Second way, choose two columns among $p^2+p+1$ columns, we have $\left(\genfrac{}{}{0ex}{}{p^2+p+1}{2}\right)$ ways. And then, we have at most 1 row $C$ that cuts $A,B$ at two colored cells (since there are no rectangle), then $$S\le \left(\genfrac{}{}{0ex}{}{p^2+p+1}{2}\right).$$

Notice that ${\sum }_{i=1}^{p^2+p+1}{x}_i=k$. Hence, we have $$\left(\genfrac{}{}{0ex}{}{p^2+p+1}{2}\right)\ge \sum _{i=1}^{p^2+p+1}\left(\genfrac{}{}{0ex}{}{x_i}{2}\right)\ge \frac{1}{2}\left(\frac{1}{p^2+p+1}{k}^2-k\right)$$ or $k\le (p+1)(p^2+p+1)$.

2) Consider the tuples $(a,b,c)$ in which $0\le a,b,c\le p-1$ and $a+b+c>0$, then we have $p^3-1$ tuples in total.

Since two tuples $(a,b,c)$ and $(d,e,f)$ are considered to belong to the same set if and only if $\exists k\in \{1,2,3,\dots ,p-1\}$ such that $a\equiv kd,b\equiv ke,c\equiv kf(\mathrm{mod}p)$. We have $p-1$ ways to choose $k$, then $\frac{p^3-1}{p-1}=p^2+p+1$ sets satisfy the given condition.

3) From the way to color the table, one can check that on each row, there are exactly $p+1$ colored cells. Indeed, we need to prove that $ax+by+cz\equiv 0(\mathrm{mod}p)$ has exactly $p+1$ solutions that do not belong to the same set $S_1,S_2,\dots ,S_{p^2+p+1}$.

There are $p^2-1$ pairs $(x,y)$ and for each pair, there is a unique number $z$ such that $ax+by+cz$ is divisible by $p$. Each set has $p-1$ solutions, then there are $p+1$ solutions that do not belong to the same set. Multiply this number with the number of columns, we have verified that there are $(p+1)(p^2+p+1)$ colored cells on the table.

Then, we shall prove that there are no rectangles. For two tuples $(a,b,c)$ and $(d,e,f)$ that do not belong to the same set, we need to prove that the following system of equations has no more than one solution: $$\{\begin{array}{ll}ax+by+cz\equiv 0& (\mathrm{mod}p)\\ dx+ey+fz\equiv 0& (\mathrm{mod}p)\end{array}$$ Without loss of generality, we can suppose that $\frac{b}{e}-\frac{c}{f}$ is not divisible by $p$ or $bf\not\equiv ce(\mathrm{mod}p)$, then for all $x_0=1,\dots ,p-1$, there is exactly one value $y_0,z_0$ such that $$b{y}_0+c{z}_0=a{x}_0,e{y}_0+f{z}_0=d{x}_0(\mathrm{mod}p).$$ On the other hand, there are $p$ values $x_0$ and we do not consider the tuple $(0,0,0)$, then there are at most $p-1$ solutions.

Note that if $(x,y,z)$ is a solution, then so is $(kx,ky,kz)$, then the above system has no more than one solution.

This finishes our proof and $k_{\text{max}}=(p+1)(p^2+p+1)$.