Each field of the $n \times n$ array has been colored either red or blue, with the following conditions met: $\bullet$ if a row and a column contain the same number of red fields, the field at their intersection is red; $\bullet$ if a row and a column contain different numbers of red cells, the field at their intersection is blue. Prove that the total number of blue cells is even.
Problem
Source: 2023 Czech-Polish-Slovak Match Junior, individual p4 CPSJ
Tags: combinatorics, Coloring
05.05.2024 19:19
Claim: When we take two column and two rows' intersection, there cannot be exactly $1$ blue square. Proof: Assume that we took $a,b.$ rows and $c,d.$ columns and the intersection of $a$ and $c$ is blue and the others are red. Denote $R_b(x),C_b(x)$ as the number of blue cells in $x.$ row and column respectively. We have $R_b(A)=C_b(D)=R_b(B)=C_b(C)\neq R_b(A)$ which is impossible.$\square$ Let's induct on $n$. Assume that it's true for $1,2,...,n-1$. We will prove it for $n$. Changing rows and columns' place doesnot affect conditions. Let the intersection of first $k$ rows with the first column be blue and the intersection of $k+1,...,n.$ and the first column be red. We can assue that $n-1\geq k\geq 1$. Because after taking first column with the least number of blue squares among all columns if $k=0,$ then all squares are red which obviously satisfies and if $k=n,$ then all squares are blue which does not satisfy the conditions. $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline B&&&&&& \\\hline B&&&&&& \\\hline B&&&&&& \\\hline B&&&&&& \\\hline R&&&K&& \\\hline R&&&L&& \\\hline R&&&M&& \\\hline \end{array} $$ Because of the claim, if $K$ is blue, then $L,M$ are blue too. By changing the place of columns, we can assume that intersections of $k+1,...,n.$ rows with $2,...,k+1.$ columns are blue since there are exactly $k$ blue squares in $k+1,...,n.$ rows. $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline B&Y&Y&Y&Y&X&X \\\hline B&Y&Y&Y&Y&X&X \\\hline B&Y&Y&Y&Y&X&X \\\hline B&Y&Y&Y&Y&X&X \\\hline R&B&B&B&B&R&R \\\hline R&B&B&B&B&R&R \\\hline R&B&B&B&B&R&R \\\hline \end{array} $$ There must be exactly $k$ blues in each of $k+2,...,n.$ columns thus all $X'$s must be blue. $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline B&Y&Y&Y&Y&B&B \\\hline B&Y&Y&Y&Y&B&B \\\hline B&Y&Y&Y&Y&B&B \\\hline B&Y&Y&Y&Y&B&B \\\hline R&B&B&B&B&R&R \\\hline R&B&B&B&B&R&R \\\hline R&B&B&B&B&R&R \\\hline \end{array} $$There are $2nk-2k^2$ blue squares other than $Y'$s. Also there exists an even number of blue squares in $Y'$s by our induction assumption since all $Y'$s are in in the same row and column with exactly $n-k$ blue squares. So we get the desired conclusion.$\blacksquare$