Commentary
This problem is about finding a winning strategy in a game. This means describing a way that Claire can choose her moves so that, no matter what Stuart does, she always wins. This may involve having some fixed moves (for example, having a fixed number as her first move), but also “responding” to Stuart’s moves.
In general, it maybe be that neither player has a winning strategy. For example, in Noughts and Crosses (Tic-Tac-Toe) if both players play correctly the game always ends in a draw. In this problem, the question suggests that Claire has a winning strategy for some, but not all, values of \(n\).
It is useful to start thinking about the last few moves of the game. This “working backwards” is unlikely to lead to the full solution, but it gives you a good feel for what it going on.
It should be pretty clear that, if Claire has the final move, she can ensure that the total is not a multiple of 9 (as she has a choice of five numbers). Can you see for which values of \(n\) this happens?
If Claire does not go last, she needs to put Stuart in a position where he cannot win on his final move. You can start working backwards from there, but you will probably quickly realise that there are too many options.You need to look for some sort of strategy that Claire can repeat, no matter how large \(n\) is.
You may have seen this type of problem before. For example, you may be familiar with the following game. Two players take turns counting from 1, saying either one or two numbers at a time. The winner is the person who says 21. Here the second player can always win by saying a multiple of 3 (if the first person says one number the second says two, and vice versa).
In Nifty Nines the person going second can ensure that after their move the total is always a multiple of 6. This means that Stuart can ensure that after every six moves (three lots of two moves) the total is a multiple of 18. Thus, if \(n\) is a multiple of 6, Stuart has a winning strategy.
Are there any other values of \(n\) where Claire can ensure a win? You have probably found that, if Stuart is going last, Claire needs her final move to give a sum which leaves remainder 0, 1, 2 or 3 when divided by 9. After her first move she can play as if she is the second player, “responding” to Stuart’s move to increase the sum by 6, and so ensuring that after every six moves the sum increases by 18. Therefore, if there are \(6k + 2\) moves, she can start with 1, 2 or 3 and force a win.
The only possibility we have not yet covered is when \(n\) is of the form \(6k + 4\). This is similar to the \(6k + 2\) case, but there are additional two moves so Claire can add another 6 to the total. Thus Claire can ensure that after her final move the sum leaves the remainder 7, 8 or 0. Out of those, only the last one prevents Stuart from winning. So if she starts with 3, Claire can ensure a win in this case as well.
Your solution needs to include three things:
(i)State for which values of \(n\) Claire has a winning strategy.
(ii)Describe the winning strategy for each of those values and explain why it works.
(iii)Explain why for all other values of \(n\) she does not have a winning strategy.
Let \(s_k\) be the sum of the numbers chosen up to and including the \(k^{\text{th}}\) step, and let \(r_k\) be the remainder when \(s_k\) is divided by 9. If Claire makes the last choice, she can choose the number 1 or 2 to ensure that \(r_n \neq 0\), so that \(s_n\) is not a multiple of 9. She makes the last choice if and only if \(n\) is odd; therefore if \(n\) is odd then Claire can force a win.
She can also ensure that she wins if \(n\) is even and not a multiple of 3, that is, \(n\) is of one of the forms \(6m + 2\), \(6m + 4\) for some \(m\). To do this, on her first move Claire chooses 3. Thereafter, at step \(2k + 1\), if Stuart has chosen \(d\) at stage \(2k\) then Claire chooses the number \(6 - d\). If \(n = 6m + 2\), after \(3m\) pairs of steps \(s_{6m+1}\) will be \(3 + 3m \times 6\), so \(r_{6m+1} = 3\) and Stuart will be unable to make a multiple of 9 at the \(n^{\text{th}}\) step; and if \(n = 6m + 4\), after \(3m + 1\) pairs of steps \(s_{6m+3}\) will be \(3 + (3m + 1) \times 6\), so \(r_{6m+3} = 0\) and again Stuart will be unable to make a multiple of 9 at the \(n^{\text{th}}\) step.
If, however, \(n\) is a multiple of 6 then Stuart can ensure that he wins: whatever number \(d\) Claire chooses at stage \(r\) (where \(r < n\) and \(r\) is odd), Stuart chooses \(6 - d\) at stage \(r + 1\). This ensures that \(s_{k+6} = s_k + 18\) and Stuart can thereby ensure that \(r_k = 0\) whenever \(k\) is a multiple of 6.
The conclusion is that Claire can force a win if \(n\) is not a multiple of 6; she cannot force a win if \(n\) is a multiple of 6.