{"id":1860,"date":"2017-03-12T13:01:55","date_gmt":"2017-03-12T18:01:55","guid":{"rendered":"http:\/\/www.laurentlessard.com\/bookproofs\/?p=1860"},"modified":"2017-03-13T00:55:58","modified_gmt":"2017-03-13T05:55:58","slug":"space-race","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/space-race\/","title":{"rendered":"Space race"},"content":{"rendered":"

<\/p>This Riddler puzzle<\/a> is about a game involving filling up the space on a square table using coins.\n

Two players are seated at a square table. The first player places a coin on the table, the second places a coin on the table, and they carry on placing coins one after another, with the only condition being that the coins are not allowed to touch. The winner is the person who places the final coin on the table, meaning that he or she fills the last remaining space between the other coins.<\/p>\n

The table has to be larger than a single coin, and all the coins placed must be identically sized. If the players play optimally, is one of the two players guaranteed to win? If so, what is the winning strategy?<\/p><\/blockquote>\n

Need a hint?
\n[Show Solution]<\/a><\/p>\n

\nUse symmetry!\n<\/div>\n

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

\n

It\u2019s easy to get stuck thinking that this problem has some sort of solution involving the pigeonhole principle<\/a>; there is this tendency to try and subdivide the table into some sort of grid and argue that only so many coins can fit in each cell. This turns out to be very difficult since circles can be tiled in complicated ways. The solution to this problem turns out to be much much simpler.<\/p>\n

Let\u2019s call the players Alice (first player) and Bob (second player). Alice always wins, and the strategy is as follows: Alice places her coin in the center of the table. Then, no matter what Bob does, Alice responds by placing a coin radially opposite to the coin that Bob placed, and at an equal distance to the center. Whenever it\u2019s Bob\u2019s turn to play, the board is in a symmetric arrangement of coins. So for every spot Bob can place a coin, there is an identical open spot opposite it where Alice can play her response. Eventually, Bob has no space left to play and Alice wins!<\/p>\n

Here is a simulation showing Alice (magenta) and Bob (blue) that illustrates how the game could play out assuming optimal play from Alice and random play from Bob. (board size is 10\u00d710 and coins have a diameter of 1).<\/p>\n

\"\"<\/p>\n<\/div>\n

<\/p>\n<\/body>","protected":false},"excerpt":{"rendered":"

This Riddler puzzle is about a game involving filling up the space on a square table using coins. Two players are seated at a square table. The first player places a coin on the table, the second places a coin on the table, and they carry on placing coins one after another, with the only … Continue reading “Space race”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":1867,"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":[29,23,2,14],"class_list":["post-1860","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-classics","tag-logic","tag-riddler","tag-symmetry"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t