Find the smallest positive integer $n$, such that one can color every cell of a $n \times n$ grid in red, yellow or blue with all the following conditions satisfied: (1) the number of cells colored in each color is the same; (2) if a row contains a red cell, that row must contain a blue cell and cannot contain a yellow cell; (3) if a column contains a blue cell, it must contain a red cell but cannot contain a yellow cell.
Problem
Source: CGMO 2021 P3
Tags: combinatorics, Coloring
Mr.Trick
14.08.2021 14:44
$n=3k$,and $3k^2$ can be written as the product of to integers in $(\frac{3k}{2},3k)$. The sallest $k$ is $15$.
zsgvivo
14.08.2021 14:52
Note that these conditions are still satisfied after exchanging any two rows or columns of a grid that satisfies these conditions. Assuming that all yellow cells are moved into a \(x\times y\) rectangle, it's easy to note that all of these \(x\times y\) cells are yellow. We have: $$xy=\frac{n^2}{3}$$$$y(n-x)+n-y\leq \frac{n^2}{3}$$$$x(n-y)+n-y\leq \frac{n^2}{3}$$ So we get the smallest integer n is 45.
FishHeadTail
18.08.2021 07:36
Call a row or a column "pretty" iff it contains a yellow cell. First note that exchanging any two rows or any two columns doesn't matter. Let there be $x$ pretty rows and $y$ pretty column, and that the first $x$ rows and first $y$ columns are all pretty.
It can then be proven that the upper-left $x \times y$ rectangle only contains yellow cells since any red/blue cell in there would make a whole row/column becomes not pretty.
Next we try some bounding. Clearly, every color appears exactly $n^2/3$ times, which means $3 \vert n$. As the lower-left $(n-x) \times y$ rectangle can only contain red cells and the upper-right $x \times (n-y)$ rectangle can only contains blue cells, if $x < n / 2$, there must be more red cells (in the lower-left rectangle) than yellow cells. On the other hand, if $x > 2n / 3$, even if every cell in the lower $(n-x)\times n$ rectangle are colored red there won't be enough red cells. Similarly we get $$\frac{n}{2} \le x, y \le \frac{2n}{3}, xy=\frac{n^2}{3}.$$After that, we can search through all $n \le 42$ and arrive at the fact that there aren’t any integral solutions for $(x, y)$. (Hope there are better ways, though it's just at most $14$ cases to consider)
When $n=45$, there's a solution $(x, y)=(25, 27)$, so it suffices to give a construction:
(the shaded area can be randomly filled with red and blue, as long as the total num of both red and blue is $n^2/3$.
Attachments:
