Find all $(m,n) \in \mathbb{Z}^2$ that we can color each unit square of $m \times n$ with the colors black and white that for each unit square number of unit squares that have the same color with it and have at least one common vertex (including itself) is even.
Problem
Source: SRMO 2005
Tags: combinatorics proposed, combinatorics
10.04.2005 18:23
so, is the problem to find all m,n for which an mxn rectangle's unit squares can be colored W/B, so that every black squares has vertices touching to 0,2 or 4 (a square number) of other black squares and vice versa for white? But that cannot be, since a chessboard always fulfils the condition [always 0]... please clarify yourself.
10.04.2005 22:25
Peter, I have no idea what you find hard to understand here.. For a small square, call all the squares which share at least a vertex with it (including itself) its neighbours. We have to find those $m,n$ for which it's possible to color the squares of an $m\times n$ board in two colors, s.t. each square has an even number of neighbours colored in the same color as itself. I believe the answer is: those $m,n$ for which $2|mn$ (i.e. at least one of $m,n$ is even). If $m$ is even, for example, we color the first two lines in white, the next two in black, and so on. Conversely, let's assume we can find such a coloring for our $m\times n$ board. We look at the graph having the black squares as vertices and in which two different squares are connected iff they are neighbours. The hypothesis tells us that in this graph, each vertex has an odd degree, so it has an even number of vertices. The same goes for the graph formed by the white squares, so the board has an even number of squares, and this is what we wanted to show: $mn$ (the number of squares) is even.
11.04.2005 11:47
For $m \times n$ table that $m$ is even, Divide the table in $\frac m2$ of $ n \times 2$ tables. And color the tables black and white
11.04.2005 11:52
That's what I said, but i guess my post looked too long to be worth reading .
11.04.2005 13:19
Is that long? I'm still waiting for Pierre's first post of that length As for my misunderstanding: I skipped the last line and thus thought that the number of neigbours not including itself needed to be even... and then a chessboard pattern does the job