Spring 2017, problem 42

A board with $m\times n$ squares on it is painted in such a way that each square is either black or white and such that for every black square, the number of black squares adjacent to it is odd (two squares are adjacent if they share one edge). Show that the number of black squares is even.


4 years ago

Let us label the black squares by the numbers 1,2,3,...,q . For each i let us denote the number of black neighbors of the i square by $d_i$ . Let us also name an edge which is common to two black squares a border edge. Assume that there are k such edges. Since the i black square has $d_i$ border edges and each border edge belongs to two black squares $\sum\limits_{i=1}\limits^{q}{d_i}=2k$   . But $d_i$ is odd for every i .Then q must be even .