Graph colorings
There is a well-known result called the four color theorem that states that at most four colors are required to color a map such that countries sharing a border are always different colors. So why would six colors ever be required? While it’s true that it only takes four colors to color a given map, you need to see the whole map in order to know which colors to use where. In this problem, Allison can (and must) change the way she draws the countries based on how Bob chooses to color them.
Maps can get messy pretty quickly, but it turns out we can work with graphs instead. Each country is represented by a vertex, and we draw an edge between two vertices whenever those countries share a border. Every map can be represented by a planar graph, i.e. a graph that can be drawn such that none of its edges intersect. Likewise, every planar graph corresponds to a map. Here is an example illustrating the transformation.
Every map coloring therefore corresponds to a coloring of the graph vertices such that whenever vertices share an edge, they cannot share the same color. This is known as a graph coloring.
Sequential country addition
The game involves drawing new countries sequentially and then coloring them. From the graph point of view, this amounts to Allison drawing a new vertex along with some number of edges such that the new graph is still planar, and then Bob picking a color for that vertex. The planar graph divides the plane into regions separated by the existing edges: several inner regions and one outer region.
Solution
The smallest map I came up with has eight countries (in the worst case). In the figure below, I show which countries Allison should add at each stage (gray nodes) and what Bob’s color options are. In a couple cases, I pruned the graph to remove interior vertices just to simplify the picture, and I ignored equivalent positions resulting from permuting colors since the color itself doesn’t matter, only whether colors are the same or different. Allison starts by drawing three touching countries.
If Bob does his best to delay the inevitable (he follows the longest path on the diagram above), then there will be a total of 8 countries on the map when Bob is forced to use a sixth color. Here is what one of the final largest maps looks like with all the countries drawn in when both players are playing optimally. I numbered the regions in the order in which Allison draws them, and colored them as Bob would color them.
The eigth country forces Bob to choose the sixth color. As mentioned above, every map can be colored using only four colors, so in hindsight, Bob could have recolored this same map using only four colors. Here is one possible way to do that:
Of course, there is no hindsight in this game. No matter how Bob colors the map, Allison will simply adjust how she draws subsequent countries in such a way to force a sixth color to appear.
Open problem and conjecture
The natural question to ask is whether Allison can ever force Bob to use 7 colors, or 8 colors, or arbitrarily many colors. I suspect the answer is yes, because if we repeatedly add nodes with only two neighbors, we can make the graph’s boundary as large as we like. We can also ensure all four colors are used as often as we like by occasionally grouping triples (e.g. group 1,2,3 to force a 4). We can also group 1,2,3,4 to force a 5 and by adding enough nodes, we can include as many 5’s as we like in the boundary as well. This process continues and ultimately we can force the appearance of a 6, then arbitrarily many 6’s, then a 7, then arbitrarily many 7’s, and so on. The question of finding the minimum number of countries required to force a given number of colors seems difficult, but I suspect it grows exponentially.
Nice job with this problem (I’m the guy who posed it to the Puzzler). In answer to the question at the end as to whether Allison can force Bob to use any number of colors, the answers is yes. My friend, Tony Dillof, a professor at Wayne State Law School, has proven that N colors can be forced in no more than twice the number of moves it took to force N-1 colors. For example, to force 7 colors:
1. A should begin to force 6 but stop one move short of forcing 6 so 5 colors are still exposed (i.e., on the outside of the map). This will take 7 moves if B plays optimally.
2. A should then begins a new island and do the same thing again so again 5 colors are exposed on the outside of the new island. This will take 7 more moves.
3a. If any color in Island 2 differs from the 5 colors exposed in Island 1, there are 6 exposed so A can circle both islands to force 7.
OR
3b. If the same 5 colors are exposed on both islands, A will force color 6 on one island and then circle both islands to force 7 (16 moves total).
This strategy can be used iteratively to force any higher number, so A can use it to force 8 colors in 32 moves, 9 colors in 64 moves, and so on. But I’m pretty sure it’s far from optimal in forcing color N in the fewest number of moves. For example, I suspect one can force 7 colors in 11 moves, not 16, though I haven’t been able to prove it yet.
Thanks for the wonderful problem. I really enjoyed working on it! That’s a clever way to construct an exponential upper bound for the general case.
Seems difficult to solve in general, though I wonder if you could use some sort of Markov Chain / dynamic programming approach. There are only finitely many possible moves at each stage and we can think of the “current state” of the map as the set of exposed countries along with their specified order. I’m not saying it will be easy (after all, chess only has finitely many moves at each position…), but it might be computationally doable for the small cases, e.g. 7, 8, 9 colors, etc.
Hi Laurent,
I like your solution but you did not include a demonstration that you can always get to 7 countries using only 5 colors. That would complete the problem — by showing that 8 countries is not only possible, but it is also necessary.
I have put my proof at
http://theorie.ikp.physik.tu-darmstadt.de/qcd/moore/graph.pdf
I suspect that for each additional color beyond 6, one needs to add two more countries.
guy
Hi Guy,
You are right. I did not prove that it was impossible to force 6 colors using only 7 countries. Thanks for sharing your proof!
I’m curious — why do you suspect that Allison can force new colors at a rate linear in the number of countries? I would imagine that the task of forcing new colors to appear gets progressively more difficult for Allison because the number of colors available to Bob keeps growing.
This strategy for an upper bound can be improved upon as follows:
1. A should begin to force 6 but stop one move short of forcing 6 so 5 colors are still exposed (i.e., on the outside of the map). This will take 7 moves if B plays optimally.
2. A should then begins a new island and do the same thing but only until there are 4 colors on the outside of the new island. This will take 6 more moves.
3a. The islands may use different colors. If there are six colors exposed, we circle them all and get a 7th color on the 14th move.
3b. If there are only 5 colors exposed, we identify the color that exists in part 1. but not part 2. and circle all of the colors, just touching the unique color entry in 1. This will leave color 6 and the unique color exposed on the first island. We then circle everything and get a 7th color on the 15th move.
If A_n is the minimum number of moves required to force n colors, then:
A_n <= A_(n-1) – 1 + A_(n-2) – 1 + 2 = A_(n-1) + A_(n-2); A(5)=7 and A(6)=8
Letting p = (1+sqrt(5))/2 and q = (1-sqrt(5))/2 then:
A_n = (19/sqrt(5)-8)p^n – (19/sqrt(5)+8)(q)^n or about: ((1.618^n)-33(-.618)^n)/2 which is dominated by the first term and grows slower than A_n = 2A_(n-1)
I question this sentence: “A. should then begins a new island and do the same thing but only until there are 4 colors on the outside of the new island. This will take 6 more moves.” It seems to me that A. can get 4 colors on the outside in just 5 moves, not 6. I work with graphs not maps. A. places vertex V1; it gets color 1. She places vertex V2 adjacent to V1; it gets color 2. She then places V3 adjacent to V1 but not V2. This is either colored 3 (case “new”) or 2 (case “old”). In the new case she places V4 adjacent to V1, V2, V3 so that all four stay exterior. It must get color 4, ending it in 4 moves. In the old case she places V4 adjacent to V1 and V2. So V4 gets color 3. Now V5 can be placed adjacent to V1, V3 and V4 so that all these 4 vertices are still exterior. V5 must get color 4. So 5 steps suffice to get 4 colors on the exterior.
This is correct. The use of A(5)=6 was not calculated and was based upon the trivial observation: A(n-1) is less than or equal to A(n)-1. Letting p and q be as defined above, we have: A(n)=(2sqrt(5)-4)p^n-(2sqrt(5)+4)q^n. Thus for n greater than 5, A(n) = round[(2sqrt(5)-4)p^n,0] which also grows proportionately to p^n. – JZGYK
I’d have thought the four-color theorem would mean that Bob, unless he makes a mistake, would never need more than four colors. (OTOH, it doesn’t look like the rules would prohibit Allison from taping the sheet of paper into a torus.) What am I overlooking?
The four-color theorem only states that “The regions of any simple planar map can be colored with only four colors, in such a way that any two adjacent regions have different colors.” http://www.ams.org/notices/200811/tx081101382p.pdf. If Bob were able to go back and re-color the map, he would only need four colors. But he does not get the benefit of such hindsight in the adversarial map coloring game. Rather, Allison gets to feed him countries after he has already committed to a particular color scheme. And she gets the benefit of knowing the choices he has already made.