Enigmatic Code
Programming Enigma Puzzles
Puzzle #211: Cross purposes
Posted by on 3 March 2023
From New Scientist #3428, 4th March 2023 [link] [link]
Debbie and Hoi are playing a game where they take turns to cross out numbers written on a piece of paper.
Each player must cross out a divisor or a multiple of the number most recently crossed out. The first player who is unable to cross out a number loses.
Hoi goes first and crosses out 11. Debbie smiles, knowing she can now win in three moves. What number does she cross out?
[puzzle#211]
Enigmatic Code 
Note: Apparently I misunderstood what it means for Debbie to “win in three moves”. (See below).
H starts by playing 11.
D then has to play one of 33, 55, 77. And any one of these can give D a guaranteed win in 3 moves.
If D’s first move is 55, then H can only respond with 5. D can then play 35 → (7) → 77, or 15 → (3) → 33/51 to win in 3 moves.
So this is probably the required solution, that D plays 55 as a first move.
However, if D’s first move is 33, then H can only respond with 3. D can then play 51, and as H cannot play D has won in just 2 moves.
Or, instead of 51, D can play 15, and then H can only respond with 5, and D can then play 55 to win in exactly 3 moves.
So if D’s first move is 33 they can also win in 2 or 3 moves, and it is up to D which path is followed. So this is also a viable solution.
And if D’s first move is 77, then play must proceed: 77 → (7) → 35 → (5). D can then play 55 and win in 3 moves, or 15 → (3) → 33/51, and win in 4 moves.
So it is also possible for D to guarantee a win in exactly 3 moves by playing 77 as a first move.
Hence, after H plays 11, they lose control of the game. It is possible for D to win in 2, 3, or 4 moves, and D can choose which of these paths to follow. Each of D’s moves can force a particular move for H, so H has no further influence on the game.
Solution: Debbie can guarantee a win in exactly 3 moves by playing 55. Or 77. Or 33. Which is any of the 3 permissible next moves.
D can win via any of the following paths:
There are further paths that end with D winning, but these require H to co-operate by making a choice that allows D to win.
This Python program find possible length 6 games.
Run: [ @replit ]
from enigma import (delete, append, printf) # return moves as: {0: <wins for 0>, 1: <wins for 1>} def play(ns, ss, p): # the other player q = p ^ 1 # the outcomes of possible next moves rs = { 0: [], 1: [] } n = ss[-1] for (i, x) in enumerate(ns): # can we play x? if (n % x if x < n else x % n) == 0: r = play(delete(ns, [i]), append(ss, x), q) rs[0].extend(r[0]) rs[1].extend(r[1]) # no plays = win for opponent if not (rs[p] or rs[q]): return { p: [], q: [ss] } # but if there are winning plays ... if rs[p]: return { p: rs[p], q: [] } # otherwise ... return { p: [], q: rs[q] } # find plays after first player has chosen 11 rs = play([2, 3, 4, 5, 7, 15, 19, 33, 35, 38, 51, 55, 76, 77, 95], [11], 0) # look for D wins in 3 moves (= length 6 sequence) for ss in rs[0]: if len(ss) == 6: printf("{ss} -> win for {x}", x=len(ss) % 2)Assuming a unique solution, better wording would have been
“Debbie smiles, knowing that if she makes the right choice now she can win on her next move.” The three moves are hers, his, hers.
Ah. I see. Three more moves in the entire game, rather than three moves for Debbie. So the entire game consists of four moves in total (two moves each).
Yes. There is only one path with length 4 (shown above), so this does give a unique solution to the puzzle.