13
$\begingroup$

Alice and Bob play the following game, taking turns. Alice starts and writes a single digit from 0 to 9 at the blackboard. At every turn, each player adds a single digit at the right of the current number. This digit must differ from the previously chosen digit modulo 3. The game ends when a number with 10 digits is reached. If this number is divisible by 3, Bob wins otherwise Alice wins.

Who has a winning strategy?

Improve this question
$\endgroup$
5
  • $\begingroup$ How about part two: at each turn a previously unused digit must be used $\endgroup$
    – theonetruepath
    May 23, 2021 at 7:48
  • 1
    $\begingroup$ @theonetruepath Unfortunately, that's trivial (rot13): N gra qvtvg ahzore (va onfr gra) jvgu rnpu qvtvg rknpgyl bapr vf nhgbzngvpnyyl qvivfvoyr ol avar, naq gurersber guerr. $\endgroup$
    – No Name
    May 23, 2021 at 13:05
  • $\begingroup$ @NoName Your observation is true, yet I don't believe it fully trivialises the variation: One still has to think a bit more about the last few digits. Vs gur ynfg qvtvg vf 0,3,6 be 9 gura jung lbh fnl nccyvrf gb gur svefg 9 qvtvgf. Vs gur 9gu qvtvg vf gur fnzr, vg nccyvrf gb gur svefg 8 qvtvgf, rgp. $\endgroup$
    – theonetruepath
    May 23, 2021 at 23:58
  • $\begingroup$ @theonetruepath You make an excellent point, but the stated rules are that the game ends when ten digits is reached, and only then is the divisibility checked. The variation you suggest would have to change that rule as well. $\endgroup$
    – No Name
    May 24, 2021 at 20:59
  • $\begingroup$ @NoName Not really... checking divisibility only at the end doesn't need to change any more than it does with the current version. We are tracking how it may be forced to end up, and we do that from step one. Eg if we use all digits not divisible by 3 by step 6, the game has effectively ended, but we don't need to change the rule to make that explicit. $\endgroup$
    – theonetruepath
    May 25, 2021 at 2:32

3 Answers 3

Reset to default
10
$\begingroup$

As a number is divisible by 3 iff the sum of its digits is, we need only look at this sum. Let $M_1,M_2,...$ be the moves. We can express the condition that consecutive moves differ modulo 3 by writing

$M_2 = M_1+N_1 \mod 3$

where $N_1 = \pm 1$.

Similarly,

$M_3 = M_1+N_1+N_2$

etc. The total sum is therefore

$\sum_1^{10} M_i = 10 M_1 + \sum_1^9 (10-i) N_i$

Modulo 3 this equals

$M_1 - N_2 + N_3 - N_5 + N_6 - N_8 + N_9$

In particular, each player's every third move is completely irrelevant and the other player can use their two adjacent moves to set an arbitrary value modulo 3. As the last such double move is Alice's she only needs to set this value to 0 such that Bob in the very last move is forced to move away from 0.

So it is

Alice who wins.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Oh, this is interesting! I hadn't realized the implications of continuing further back, but it makes sense that some moves are irrelevant. $\endgroup$
    – Deusovi ♦
    May 21, 2021 at 21:25
  • $\begingroup$ Not sure I understand. I'm not really going backward. Unless you interpret the $(10-i)$ term as going backward. The intuition is every move shifts every subsequent move by the same offset. If the number of moves so involved is a multiple of 3 the net effect is naught. $\endgroup$
    – loopy walt
    May 21, 2021 at 21:57
  • $\begingroup$ By "going further back", I meant in my analysis in the answer posted at about the same time. I understand the intuition in yours; in mine, the "useless moves" would correspond to the turns just before grids where all the \-wards diagonals were monocolor. (Which is why I had to go back to the 7th turn to get a starting point.) $\endgroup$
    – Deusovi ♦
    May 21, 2021 at 22:44
  • $\begingroup$ "such that Bob in the very last move is forced to move away from 0." I don't understand how we can force Bob from not using 0,3,6 or 9 in his last move ? I mean, the only way to force Bob not to use any of these digits in his last turn is for Alice to play 0,3,6,9 in her last turn.. But then, how do we guarantee that Alice can play one of these numbers on her last turn? And even if she can, then how do we guarantee that her playing one of these numbers on her last turn, would make the sum after her last turn, 0 mod 3 ? $\endgroup$
    – Hemant Agarwal
    Jun 25 at 7:04
9
$\begingroup$

Note that

the only thing that matters is the sum of digits modulo 3 - if that sum is zero, Bob wins, and if not, Alice wins

So, let's work backwards:

Represent a state by three things: the sum so far ($s$), the last move played ($l$), and the number of turns remaining ($t$). In these charts, I will color each possible state red for it being a winning state for Alice, or blue for it being a winning state for Bob.
At $t=1$, it is Bob's turn; Alice wins if she had successfully prevented Bob from making the winning move.
enter image description here
At $t=2$, it is Alice's turn; she wants to make the move that would end on one of the "A" spots. If the sum is 0, she wants to play 0; if the sum is 1, she wants to play 1; and if the sum is 2, she wants to play 2. So she wins if she can make that move, and loses if she cannot.
enter image description here
At $t=3$, it is Bob's turn. If the sum is 0, he wants to play 0; if the sum is 1 or 2, though... he cannot land on any of the B spaces! Say the sum is 1. Playing 0 lands on the upper middle, playing 1 lands on the middle right, and playing 2 lands on the bottom left. Similarly, if the sum on Bob's turn is 2, any play will land the game state on an A space at $t=2$.

So, Alice wins with the following strategy: On the second-to-last turn, make the sum either 1 or 2 -- they can't both be blocked! Then, Bob will make a move, setting the new sum to $s$. On your final turn, the move $s$ will be open to you, and this sets the sum to $2s$. Now it's the final turn of the game, and Bob has to play $s$ again to win, but you just blocked it.

For the record:

Here is the entire transition graph for this game. Circles with dashed circumferences are legal starting states for Alice; yellow circles are the states that Bob wants to end the game with.
enter image description here

Improve this answer
$\endgroup$
0
$\begingroup$

Here is Deusovi's answer in a simpler language. All credit goes to him.

Alice is guaranteed to win. She can win by ensuring that by the end of the 7th turn, the sum is not divisible by 3.

She can do this by :

Case 1: If sum is divisible by 3 by the end of the 6th turn. Alice can put a number 3x+1 or 3x+2. At least one of them has to be available.

Case 2: If sum is not divisible by 3 by the end of the 6th turn. Alice can put 3x if it is available. If 3x is not available then that means that 3x was the last move. Then she can put either 3x+1 or 3x+2.

And here is why ensuring that the sum is not divisible by the end of the 7th turn, guarantees Alice a win :

Look at the following figure. It shows the 2nd last turn of the game(t=2) i.e Alice's last turn. l=0 means that Bob put a 3x number on his previous turn, etc. s=0 means that the sum is 0 mod 3 after Bob's turn i.e the sum is divisible by 3.

enter image description here

Thus, Bob can win in t=3(his second last turn, overall 8th turn) if He can make the sum modulo 3=0 by playing a number divisible by 3. He can make the sum modulo 3=1 by playing a number 3x+1. He can make the sum modulo 3=2 by playing a number 3x+2

All the above are only possible if the sum is divisible by 3 by the end of the 7th turn. So, Alice just needs to ensure that the sum is not divisible by 3 by the end of the 6th turn.

Improve this answer
$\endgroup$

Your Answer

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

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