# A Game with Strings and Coins

Alice and Bob play a game using the following arrangement of coins, which are joined by strings and hanging from the ceiling:

$\qquad\qquad\qquad\qquad\quad$

The two alternate turns, with Alice going first. On their turn, a player must cut a string. This continues until a player causes one or more coins to fall to the ground, in which case that player loses.

Who wins under optimal play?

• Sounds an awful lot like Hex to me.
– user88
Commented Mar 29, 2015 at 21:58

Bob wins.

We show that as long as there are 17+ strings, there's a move that doesn't immediately lose, but once we're down to 16 strings, the next move loses. Each move removes a string, so Alice will lose because she cuts when there are an even number of strings (28 strings, 26 strings, ...., 16 strings).

Treat the ceiling as a single node, making the construction a graph with 17 nodes and 28 edges. As long the graph has at least as many edges as nodes (17), it cannot be a tree, and so must contain a cycle. Cutting any edge in that cycle cannot cause anything to fall because any path to the ceiling that used that edge has a "detour" where the rest of the cycle was used in place of that edge.

But, once we're down to 16 edges, the graph (if still connected) must be a tree, and removing an edge will disconnect it, so the next player loses.

• I'm impressed you solved this so fast! Had you seen it (or an equivalent puzzle) before? Commented Mar 29, 2015 at 22:16
• @randal'thor Nope, but I was familiar with all the needed graph-theory facts about trees.
– xnor
Commented Mar 29, 2015 at 22:17
• Another explanation. There are 12 "rooms", areas surrounded by string. Each cut to a wall of a room reduces the number of rooms (merges two rooms or opens one to the outside), but drops no coins. Once there are no rooms left, the next cut droms coins. Thus, there are 12 safe moves and the 13th move loses. Commented Jan 23, 2019 at 21:11