12
$\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?

$\endgroup$
5
  • $\begingroup$ How about part two: at each turn a previously unused digit must be used $\endgroup$ May 23 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 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$ May 23 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 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$ May 25 at 2:32
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.

$\endgroup$
3
  • $\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 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 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 at 22:44
8
$\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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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