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.

Answer 1

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.