4-color coloring game.

260 Views Asked by At

Similar to this question. 5-color coloring game.

Let there be two players, $$ and $$, and a map.

They now play a game such that:

Player $$ picks a region and player $$ colors it such that the region is a different color than all adjacent regions. Player $B$ wins if at the end of the game, the map is colored such that no two adjacent regions are the same color. Player $A$ wins if at any point in time that becomes impossible. If there are four available colors, then does player $$ have a winning strategy for every possible map?

1

There are 1 best solutions below

13
On

A does not always have a winning strategy. Suppose the map is of a Torus. Since it is well known that 7 colors are needed to color arbitrary partitions of a Torus, B can sometimes have a completely winning strategy. It all depends on the euler characteristic of the surface of the map.

Edit: Let $E = \mathbb R^3$ be endowed with the Euclidean metric. Embed a torus $T \subset \mathbb E$ and consider it with the topology given by the Euclidean metric on $E$. Hence, we are dealing with an Euclidean map, yet there are partitions of the underlying space for which 7 colors are needed so that no two touching partitions are the same color.