Eventually you either encounter a conflict where neighboring regions share a color, in which case no “two-coloring” exists, or the colors spread through the whole map conflict-free, in which case you’ve found a valid coloring. In turn, all of their neighbors become red, and so on, propagating through the map. This forces all of the region’s neighbors into the other color, say, blue. To do it, pick out any region and choose a color for it, say, red. Deciding whether two colors suffice would take about an hour.Curiously, while these three tasks seem nearly identical, they each require radically different amounts of time to complete. How long would it take you to determine whether the map could be colored with two colors? Three colors? Four colors? You don’t necessarily need to find a coloring, just decide whether a coloring exists for each number of colors. Suppose I printed out a large poster with a complicated map containing a few thousand regions. With the rules established, here are some questions with surprising answers.

For example, Utah and New Mexico famously only touch at a corner and so do not count as neighbors for our purposes. For two regions to count as adjacent, they must share some contiguous border touching at a single point (or discrete set of points) doesn’t qualify. The question is, given any such map, what is the minimum number of colors required to fill in each region so that no two adjacent regions have the same color? Some ground rules: each region must be contiguous, so technically Michigan violates the setup because Lake Michigan severs the state into two disconnected parts. The map doesn’t need to correspond to real geography-any partitioning of a flat surface into distinct regions qualifies. Could we have done it with only three? Might other maps require five or six?

Under this constraint, we used four colors to fill in the map above. Naturally, we don’t want neighboring states to have the same color, because that would make the boundaries more confusing.

Timetable maths without answers chart