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$enter image description here

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?

  • $\begingroup$ Sounds an awful lot like Hex to me. $\endgroup$ – user88 Mar 29 '15 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.

  • $\begingroup$ I'm impressed you solved this so fast! Had you seen it (or an equivalent puzzle) before? $\endgroup$ – Rand al'Thor Mar 29 '15 at 22:16
  • $\begingroup$ @randal'thor Nope, but I was familiar with all the needed graph-theory facts about trees. $\endgroup$ – xnor Mar 29 '15 at 22:17
  • $\begingroup$ 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. $\endgroup$ – user3294068 Jan 23 '19 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.