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 \le (p + 1)(p^2 + p + 1)$. Denote this number as $k_{max}$. 2. Prove that all ordered tuples $(a, b, c)$ with $0 \le a, b, c < p$ and $a + b + c > 0$ can be partitioned into $p^2 + p + 1$ sets $S_1, S_2, .. . 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 ka_2, b_1 \equiv kb_2, c_1 \equiv kc_2$ (mod $p$) for some $k \in \{1,2, 3, ... , p - 1\}$. 3. For $1 \le i, j \le 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_1a_2 + b_1b_2 + c_1c_2 \equiv 0$ (mod $p$), we color the cell $(i, j)$ of the given table. Prove that this coloring way is nice with $k_{max}$ colored cells
Problem
Source: 2017 Saudi Arabia Mock BMO II p4
Tags: rectangle, combinatorics, combinatorial geometry
26.01.2022 17:52
1) Convert the problem into graph: Given a bipartite graph $G=(A,B,E)$, for which $p^2+p+1$ vertices in $A$ are denoted for the column in the table, $p^2+p+1$ vertices in $B$ are denoted for the row in the table. $a \in A$ is connected to $b \in B$ iff the cell $(a,b)$ is colored So $k_{max}$ in the original problem is the maximum edges in $G$ such that there doesn't exist a cycle with length $4$ Lemma: Given a simple graph $G=(V,E)$ with $|V|=n$. Then if $G$ doesn't have any cycle length $4$ then $|E| \le \frac{{n + n\sqrt {4n - 3} }}{4}$ Proof: We count the number of $(a,b,c)$ for which $a,b,c \in V$, $a$ is connected to $b$ and $a$ is connected to $c$ in $2$ ways +) First, there are $n$ choices of $a$, for each $a$, there are $ deg(a) \choose 2$ ways of choosing the pair $(b,c)$. Then \[\left| {(a,b,c)} \right| = \sum\limits_{a \in V} {\left( {\begin{array}{*{20}{c}} {\deg (a)}\\ 2 \end{array}} \right)} \]+) Also, since $G$ does have a cycle lenth $4$; for any $2$ vertices $b,c$ in $V$, there exists at most $1$ vertice $a$ such that $a$ is connected to $b$, $a$ is connected to $c$ Then $$ | (a,b,c) | \le {n \choose 2} $$ Thus \[\left( {\begin{array}{*{20}{c}} n\\ 2 \end{array}} \right) \ge \left| {(a,b,c)} \right| = \sum\limits_{a \in V} {\left( {\begin{array}{*{20}{c}} {\deg (a)}\\ 2 \end{array}} \right)} \Leftrightarrow {n^2} - n \ge \sum {{{\deg }^2}(a)} - \sum {\deg (a) \ge \frac{{(\sum {\deg (a){)^2}} }}{n}} - \sum {\deg (a)} = \frac{{{{(2|E|)}^2}}}{n} - 2|E|\] which leads to \[|E| \le \frac{{n + n\sqrt {4n - 3} }}{4}\] Return to the main problem By applying the above lemma, we have \[k \le 2\frac{{({p^2} + p + 1) + ({p^2} + p + 1)\sqrt {4({p^2} + p + 1) - 3} }}{4} = (p + 1)({p^2} + p + 1)\]