Alice and Bob play the following coins-on-a-stack game. 20 coins are stacked…
2024
Alice and Bob play the following coins-on-a-stack game. 20 coins are stacked one above the other. One of them is a special (gold) coin and the rest are ordinary coins. The goal is to bring the gold coin to the top by repeatedly moving the topmost coin to another position in the stack.
Alice starts and the players take turns. A turn consists of moving the coin on the top to a position ‘i’ below the top coin (0 ≤ i ≤ 20). We will call this a i-move (thus a 0-move implies doing nothing). The proviso is that a i-move cannot be repeated; for example once a player makes a 2-move, on subsequent turns neither player can make a 2-move. If the gold coin happens to be on top when it's a player's turn then the player wins the game. Initially, the gold coin is the third coin from the top. Then
- A.
In order to win, Alice's first move should be a 1-move.
- B.
In order to win, Alice's first move should be a 0-move.
- C.
In order to win, Alice's first move can be a 0-move or a 1-move.
- D.
Alice has no winning strategy.
Attempted by 4 students.
Show answer & explanation
Correct answer: A
Concept: This is a shared move-pool combinatorial game — once either player plays move value i, it is permanently removed from BOTH players' future options. In such a game, what decides the outcome is not whose turn it is but which specific move-value is still available at the decisive depth of play; a player wins by preserving the exact move needed at that decisive moment while forcing the opponent to run out of it instead.
Let c = the number of ordinary coins currently sitting above the gold coin. Moving the top coin to depth i leaves c unchanged (a stall) whenever i ≤ c − 1, and reduces c to c − 1 (gold moves one step closer to the top) whenever i ≥ c.
The decisive depth is c = 1: the ONLY stalling value there is i = 0; any other move forces gold to the top, so whoever moves at c = 1 without i = 0 available hands the very next turn — and the win — to the opponent.
Play starts at c = 2 (gold is third from the top), where the stalling values are i = 0 and i = 1, and every i ≥ 2 reduces c straight to 1.
If Alice opens with a 0-move, she spends her own c = 1 lifeline early. Bob can then play any i ≥ 2 to drop the game to c = 1; with i = 0 already used, Alice has no stall left there and must herself reduce c = 1 to 0 — Bob wins on his next turn.
If Alice opens with a 1-move instead, i = 0 stays unused after her turn. Bob now faces c = 2 with two options: stall using the only stall value left there, i = 0, or reduce immediately with some i ≥ 2. If Bob stalls with i = 0, both stall values at c = 2 (0 and 1) are now spent while c is still 2, so Alice is forced to reduce to c = 1 — but Bob, facing c = 1 with i = 0 already used, has no stall of his own left and must reduce c = 1 to 0 himself. If Bob instead reduces immediately, c drops straight to 1 with i = 0 still unused, so Alice stalls with it there, leaving Bob once again with no stall at c = 1 and forced to reduce it to 0. Either branch ends the same way: Bob is the one who brings gold to the top, and Alice wins on her very next turn.
Cross-check: the trace above shows the 0-move losing for Alice and the 1-move winning against both of Bob's possible replies, so a winning strategy does exist and it is not the 0-move — leaving the 1-move as the only opening that guarantees Alice's win.