Tricoloring of vertices of m*n grid

Question

Every vertex of the unit squares on an $m$ x $n$ grid is colored either blue, green or red, such that all vertices on the boundary are colored red, where $m,n>0$ A square is properly colored if and only if one pair of its adjacent vertices are colored the same color. Show that the number of properly colored squares is even.

What I have: assume there exist a properly colored square (o/w we're done) and look at a side with two vertices of the same/different color, but then I'm stuck. Can I have a hint please? Thank you.

Does the condition mean the same as saying that all three colors are used on the vertices of the square? — saulspatz, Sep 16 '19 at 19:16
I don't really understand the notion of proper coloring you're trying to explain - but I'd imagine that the answer is just "if you flip blue and green, you get a fixed-point free involution on the colorings" — Milo Brandt, Sep 16 '19 at 19:17
I don't understand this. Consider the grid whose vertices are ${0,1,2,3}\times{0,1,2,3}$ Let all vertices be red, except that $(1,2)$ is blue and $(2,1)$ is green. As I read the problem, only the central square is properly colored. Where am I going wrong? — saulspatz, Sep 16 '19 at 19:33
Really the only fault in the question is that it should say that a square is properly coloured if and only if exactly one pair of its adjacent vertices are colored the same color. With that, unless I am terribly mistaken, the statement is valid (see my answer below). — , Sep 16 '19 at 20:03

score 1 · Accepted Answer · 2019-09-16T20:00:14.443

As it stands, if all vertices were red, then there are zero properly coloured squares, which is fine.

We will now allow any vertex not on the edge to change colour (to any of the other two colours). This will affect only the surrounding four squares. If we can prove that this change only changes the number of properly coloured squares by an even number (i.e. by $0, \pm 2, \pm 4$), then, applying this operation of colour change multiple times, we will arrive at any desired colouring, and the number of properly coloured squares will stay even all the time.

This means we have reduced the problem to just a $2\times 2$ grid, eight surrounding vertices and one in the centre changing colour - altogether there are $3^9=19683$ cases to consider.

In the absence of better inspiration, one can write a program to brute-force this search. For example, in Python: a,b,c,d,e,f,g,h are colours of the surrounding vertices, x is the colour of the central vertex, num_red, num_green, num_blue are the counts of properly coloured (out of the four) squares with x taking values of 'red', 'green' and 'blue':

RED = 1
GREEN = 2
BLUE = 3

all_colors = [RED, GREEN, BLUE]


# Checks if a square with vertices coloured into x,y,z,t
# (clockwise) is proper. Returns 1 if proper, 0 otherwise.

def is_proper(x, y, z, t):
    if (x == y and x != z and x != t and z != t) or \
       (y == z and y != t and y != x and t != x) or \
       (z == t and z != x and z != y and x != y) or \
       (t == x and t != y and t != z and y != z):
        return 1
    return 0


# Counts the number (between 0 and 4) of proper squares in the
# 2x2 grid, where the outer vertices (clockwise from top left)
# are coloured as a,b,c,d,e,f,g,h and the central vertex is
# coloured as x.

def count_proper(a, b, c, d, e, f, g, h, x):
    return is_proper(a, b, x, h) + \
           is_proper(b, c, d, x) + \
           is_proper(x, d, e, f) + \
           is_proper(h, x, f, g)

# For every possible colouring of the outer vertices

for a in all_colors:
    for b in all_colors:
        for c in all_colors:
            for d in all_colors:
                for e in all_colors:
                    for f in all_colors:
                        for g in all_colors:
                            for h in all_colors:

                                # Find the number of proper squares for all
                                # three choices for the central vertex
                                num_red = count_proper(a, b, c, d, e, f, g, h, RED)
                                num_green = count_proper(a, b, c, d, e, f, g, h, GREEN)
                                num_blue = count_proper(a, b, c, d, e, f, g, h, BLUE)

                                # Print a warning if the parity has changed

                                if (num_red - num_green) % 2 != 0:
                                    print(a, b, c, d, e, f, g, h, "RED vs GREEN")
                                if (num_red - num_blue) % 2 != 0:
                                    print(a, b, c, d, e, f, g, h, "RED vs BLUE")

which ends up not printing anything, as a proof that num_red, num_green and num_blue are always of the same parity.

Great solution. Does anybody have a coloring argument for the 2*2 part? Maybe think about the number of properly squares, or the edges with the midpoint as an endpoint. FYI I do not have a solution yet. — Kai, Sep 17 '19 at 03:41

Tricoloring of vertices of m*n grid

1 Answers1