Consider a $n$x$n$ table such that the unit squares are colored arbitrary in black and white, such that exactly three of the squares placed in the corners of the table are white, and the other one is black. Prove that there exists a $2$x$2$ square which contains an odd number of unit squares white colored.
Problem
Source: Romanian JBTST III 2007, problem 3
Tags: modular arithmetic, induction, combinatorics proposed, combinatorics
PhilAndrew
13.05.2007 22:39
Assume the contrary. Denote $a_{i,j}$ the colour on the $i$-th row and $j$-th column $\forall i,j \in \overline{1,n}$ - $0$ if black and $1$ if white. Furthermore, make the notation $A_{m,p}=a_{m,p}+a_{m+1,p}+a_{m,p+1}+a_{m+1,p+1}$, which is therefore even, $\forall m,p \in \overline{1,n-1}$. We get the contradiction:
$0 \equiv$ $\sum_{1\le i,j\le n-1}A_{i,j}\equiv$ $4\sum_{1\le i,j\le n}a_{i,j}-2\sum_{1 \le i \le n}(a_{1,i}+a_{i,1}+a_{n,i}+a_{i,n})+$ $a_{1,1}+a_{1,n}+a_{n,1}+a_{n,n}\equiv$ $a_{1,1}+a_{1,n}+a_{n,1}+a_{n,n}\equiv$ (from the hypothesis) $3 \equiv 1 \pmod{2}$.
Sashsiam_2
24.11.2009 20:15
Let us try to color the table in such a way that all the 2 x 2 squares have an even number of white unit squares. We start coloring the first two rows. If the first column has the two squares of the same color, then so has the second, and easy induction shows that it holds for the entire "2-row". If the first column has the two squares of different colors, then so have the second and the others. Take the first square and the last square of the bottom row. Assume that they are of the same color. The previous discussion shows that the first square and the last square of the second row must be both black or both white. The same then applies to the third column an so on. We see that we must have an even number of white corners. With a similar reasoning, if the first square and last square of the bottom row were of different colors then so would be the first square and last square of the second row and so on. Again the number of white corners is even, what finishes the problem. Remark: this proof works for an m x n table.