17
$\begingroup$

Alice and Bob play the following game, taking turns. Alice starts and writes a digit from the set M={1, 2, 3, 4, 5, 6} at the blackboard. Bob appends another digit from the set M until a 2n-digit number is reached, where n is a positive integer. If this number is divisible by 9, Bob wins, otherwise Alice wins. For which n can Alice win and for which n can Bob win?

$\endgroup$

2 Answers 2

16
$\begingroup$

I believe that Bob can win if (and only if) n is

a multiple of 9. There's probably an easier way to prove this, but at first glance, in order for the 2n-digit number to be divisible by 9, the sum of its digits must be divisible by 9. In other words, at the of the final round of appending numbers (a single "round" being Alice and Bob each appending a digit), the sum of all the digits must be 0 mod 9 for Bob to win.

Note that the only control Bob has is to change this value by 7 mod 9 each round; whichever digit Alice chooses (call it a), Bob can always choose 7-a. So at the end of the penultimate round, Bob needs the sum of digits to be 2 mod 9. Consequently, at the end of the round prior to that, he needs it to be 4 mod 9, and working backwards he needs 6 mod 9, 8 mod 9, 1 mod 9, 3 mod 9, 5 mod 9 and finally 7 mod 9. This last one is the only one he can force from the start of the game, and this is the first in a repeating cycle of 9 rounds.

$\endgroup$
11
$\begingroup$

I'll add on to SQLnoob's answer and say Bob can't win if n isn't

a multiple of $9$. Set $k = 7n \pmod 9$. Suppose Alice starts with move $m$. For the next $n-1$ rounds, Alice will counter Bob's move (call it $b$) with $7-b$. Thus, the total digit sum will be $m+7(n-1) = m+k-7$, with one final Bob move coming. If Alice can force $m+k-7$ to be $0$, $1$, or $2 \pmod 9$, then Bob can't win.

So she chooses

$$ m = \begin{cases} 7-k & k < 7 \\ 1 & k = 7, 8 \end{cases} $$

For example,

suppose $n = 11$. Then $k = 77 \pmod 9 = 5$. So Alice starts with $m = 2$. The next $10$ rounds proceed with Bob and Alice alternating adding to 7, which totals $70$. Now we're at $72$. Bob makes the final move, but can't get to the next multiple of 9.

$\endgroup$
3
  • 1
    $\begingroup$ For completeness, you might want to add Bob's (simple) strategy in case $n$ is a multiple of $9$. Also, it would be nice to prove these strategies for Alice and Bob are the only ones (if in fact they are), i.e.: effectively prove that deviating form such strategy allows opponent to win. Or, if not the only ones, come up with counter example strategies for both in one or vboth cases. $\endgroup$ Mar 12 at 15:21
  • 1
    $\begingroup$ @FirstNameLastName: Good questions. I think Bob cannot deviate: if the current sum is $s$, and there are $n$ rounds left, he needs $7n+s=0 \pmod 9$ after his turn, which means there is only one thing he can choose. Alice may have a bit more flexibility (for example, if k = 7. she could choose m = 2 instead of m = 1), but I don't know exactly how much. $\endgroup$ Mar 12 at 15:41
  • $\begingroup$ the combination of the two answers solves the question, well done. It is hard to tick one of the answers as both parts are needed for the solution. $\endgroup$
    – ThomasL
    Mar 12 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.