Question 144
Let $p$ be a prime number and a table of size $(p^{2}+p+1) \times (p^{2}+p+1)$ which is divided into unit cells. The way to color some cells of this table is called nice if there are no four colored cells that form a rectangle (the sides of rectangle are parallel to the sides of given table).
1. Let $k$ be the number of colored cells in some nice coloring way. Prove that $k \leq (p+1)(p^{2}+p+1)$. Denote this number as $k_{\text{max}}$.
2. Prove that all ordered tuples $(a, b, c)$ with $0 \leq a, b, c \lt p$ and $a+b+c\gt 0$ can be partitioned into $p^{2}+p+1$ sets $S_{1}, S_{2}, \ldots, S_{p^{2}+p+1}$ such that two tuples $(a_{1}, b_{1}, c_{1})$ and $(a_{2}, b_{2}, c_{2})$ belong to the same set if and only if $a_{1} \equiv k a_{2}, b_{1} \equiv k b_{2}, c_{1} \equiv k c_{2} \pmod{p}$ for some $k \in \{1,2,3, \ldots, p-1\}$.
3. For $1 \leq i, j \leq p^{2}+p+1$, if there exist $(a_{1}, b_{1}, c_{1}) \in S_{i}$ and $(a_{2}, b_{2}, c_{2}) \in S_{j}$ such that $a_{1} a_{2}+b_{1} b_{2}+c_{1} c_{2} \equiv 0 \pmod{p}$, we color the cell $(i, j)$ of the given table. Prove that this coloring way is nice with $k_{\text{max}}$ colored cells.
1. Let $k$ be the number of colored cells in some nice coloring way. Prove that $k \leq (p+1)(p^{2}+p+1)$. Denote this number as $k_{\text{max}}$.
2. Prove that all ordered tuples $(a, b, c)$ with $0 \leq a, b, c \lt p$ and $a+b+c\gt 0$ can be partitioned into $p^{2}+p+1$ sets $S_{1}, S_{2}, \ldots, S_{p^{2}+p+1}$ such that two tuples $(a_{1}, b_{1}, c_{1})$ and $(a_{2}, b_{2}, c_{2})$ belong to the same set if and only if $a_{1} \equiv k a_{2}, b_{1} \equiv k b_{2}, c_{1} \equiv k c_{2} \pmod{p}$ for some $k \in \{1,2,3, \ldots, p-1\}$.
3. For $1 \leq i, j \leq p^{2}+p+1$, if there exist $(a_{1}, b_{1}, c_{1}) \in S_{i}$ and $(a_{2}, b_{2}, c_{2}) \in S_{j}$ such that $a_{1} a_{2}+b_{1} b_{2}+c_{1} c_{2} \equiv 0 \pmod{p}$, we color the cell $(i, j)$ of the given table. Prove that this coloring way is nice with $k_{\text{max}}$ colored cells.