MathDB
Colouring a discretised torus

Source: Baltic Way 2018, Problem 7

November 6, 2018
combinatoricsColoringgraph theoryGraph coloring

Problem Statement

On a 16×1616 \times 16 torus as shown all 512512 edges are colored red or blue. A coloring is good if every vertex is an endpoint of an even number of red edges. A move consists of switching the color of each of the 44 edges of an arbitrary cell. What is the largest number of good colorings so that none of them can be converted to another by a sequence of moves?