{"id":1516,"date":"2016-11-14T00:35:18","date_gmt":"2016-11-14T06:35:18","guid":{"rendered":"http:\/\/www.laurentlessard.com\/bookproofs\/?p=1516"},"modified":"2016-11-14T01:35:16","modified_gmt":"2016-11-14T07:35:16","slug":"adversarial-map-coloring","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/adversarial-map-coloring\/","title":{"rendered":"Adversarial map coloring"},"content":{"rendered":"

This Riddler<\/a> problem considers the classical map-coloring problem with an adversarial twist! One player draws countries and the other player colors them.<\/p>\n

\nAllison 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.<\/p>\n

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?\n<\/p><\/blockquote>\n

Here is my solution:
\n[Show Solution]<\/a><\/p>\n

\n

Graph colorings<\/h3>\n

There is a well-known result called the four color theorem<\/a> 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.<\/p>\n

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<\/a>, 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.<\/p>\n

\"graph_coloring_equivalence\"<\/p>\n

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<\/a>.<\/p>\n

Sequential country addition<\/h3>\n

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.<\/p>\n

Solution<\/h3>\n

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.<\/p>\n

\"graphcoloring\"<\/a><\/p>\n

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.<\/p>\n

\"graphcoloring_map\"<\/p>\n

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:<\/p>\n

\"graphcoloring_map_four\"<\/p>\n

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.<\/p>\n

Open problem and conjecture<\/h3>\n

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.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

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 … Continue reading “Adversarial map coloring”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":1551,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[25,23,2],"class_list":["post-1516","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-graph-theory","tag-logic","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1516","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=1516"}],"version-history":[{"count":23,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1516\/revisions"}],"predecessor-version":[{"id":1552,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1516\/revisions\/1552"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/1551"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=1516"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=1516"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=1516"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}