Adversarial map coloring

This Riddler problem considers the classical map-coloring problem with an adversarial twist! One player draws countries and the other player colors them.

Allison and Bob decide to play a map-coloring game. Each turn, Allison draws a simple closed curve on a piece of paper, and Bob must then color the interior of the “country” that curve creates with one of his many crayons. If the new country borders any pre-existing countries, Bob must color the new country with a color that is different from the ones he used for the bordering ones.

Allison wins the game when she forces Bob to use a sixth color. If they both play optimally, how many countries will Allison have to draw to win?

Here is my solution:
[Show Solution]

8 thoughts on “Adversarial map coloring”

  1. 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.

    1. 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.

      1. 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.

    2. 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)

      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.

  2. 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

Leave a Reply

Your email address will not be published. Required fields are marked *