Counting, Probability & Logic: MAC UKMT Intermediate Maclaurin 2020 Q6

Maclaurin 2020 Q6

MACCurrent spec10 marksCounting, Probability & Logic

6. Seth and Cain play a game. They take turns, and on each turn a player chooses a pair of integers from 1 to 50. One integer in the pair must be twice the other, and the players cannot choose any integers used previously. The first player who is unable to choose such a pair loses the game. If Seth starts, determine which player, if any, has a winning strategy.

Maclaurin Olympiad 2020, Question 6. © UK Mathematics Trust. Original paper on ukmt.org.uk

Solution (UKMT)

Seth will win if the total number of moves is odd, and Cain if it is even.

A player must choose \(k\) and \(2k\) for some \(1 \le k \le 25\). This leads to the partition of the integers from 1 to 50 shown below. At any turn, a player must choose consecutive numbers from the same set.

{1 2 4 8 16 32} {5 10 20 40}
{3 6 12 24 48}
{7 14 28} {9 18 36} {11 22 44}
{13 26} {15 30} {17 34} {19 38} {21 42} {23 46} {25 50}

The remaining twelve integers are in singleton sets and they cannot be chosen in the game.

The 10 sets consisting of two or three elements can each only be chosen once. As their number is even, this makes no difference to the result.

The five-element set containing 3 can only be used twice, so this too is irrelevant.

So if the players stick to these 11 sets, they will occupy 12 moves.

Hence the outcome of the game rests entirely on how the players use the sets. We call moves from these two sets ‘interesting’.

Seth can guarantee a win if, on his first move, he chooses either (1, 2) or (16, 32) from the first interesting set. The two sets which remain after this removal have exactly the same structure, namely \(\{k, 2k, 4k, 8k\}\). As soon as Cain chooses a pair from one of them, Seth mimics him by choosing the corresponding pair from the other. As a result, these two sets are exhausted in an odd number of moves, so the total number of moves is odd and Seth wins.

Note that it is not essential that Seth chooses (1, 2) or (16, 32) immediately, but it is harder to analyse the alternatives. If he is the first to choose a pair from the interesting sets, he will lose if it is anything but (1, 2) or (16, 32). If Cain is the first to choose such a pair, he will lose if it is anything but (1, 2) or (16, 32). If, however, he chooses one of these pairs, Seth can still win by being patient. He can temporise with uninteresting moves until Cain is forced to play a second interesting move once all the uninteresting moves have been used. Then Seth is back in control and can force a win.