Browse · MathNet
PrintSilk Road Mathematics Competition
counting and probability
Problem
Find all pairs of positive integers for which it is possible to paint each unit square of an chessboard either white or black in such a way that, for any unit square of the board, the number of unit squares which are painted the same color as that square and which have at least one common vertex with it (including the square itself) is even.
Solution
We shall call a painting satisfying the condition of the problem a good painting. We shall also call squares sharing a vertex neighbors. Note that every square is a neighbor of itself.
If is even, then there is a good painting: Suppose that the number of rows is even. Then we paint 1st and 2nd rows white, 3rd and 4th rows black, 5th and 6th rows white and so on. This is a good painting.
Now assume that is odd and there is a good painting. Either the number of white squares or the number of black squares is odd. Let us assume the first. Consider the set of ordered pairs of white squares which are not neighbors.
Since each square is a neighbor of itself, has an even number of elements.
On the other hand, there is an odd number of white squares and, since the painting is good, for each white square there is an odd number of white squares which are not neighbors of it. This implies that has an odd number of elements, a contradiction.
If is even, then there is a good painting: Suppose that the number of rows is even. Then we paint 1st and 2nd rows white, 3rd and 4th rows black, 5th and 6th rows white and so on. This is a good painting.
Now assume that is odd and there is a good painting. Either the number of white squares or the number of black squares is odd. Let us assume the first. Consider the set of ordered pairs of white squares which are not neighbors.
Since each square is a neighbor of itself, has an even number of elements.
On the other hand, there is an odd number of white squares and, since the painting is good, for each white square there is an odd number of white squares which are not neighbors of it. This implies that has an odd number of elements, a contradiction.
Final answer
All pairs with mn even (i.e., at least one of m or n is even).
Techniques
Counting two waysColoring schemes, extremal arguments