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