Alice and Bob Game 123456789

Question

The number 123456789 is written on the blackboard. Alice and Bob play the following game, taking turns. At every turn, each player decreases by 1 or 2 any digit other than the leftmost digit, if the sequence of symbols on the board after the change is a positive integer. A player losses if he cannot make a turn. Who has a winning strategy if Alice starts?

Answer 1

As you can't change the leftmost number, if I understand correctly, you can model your problem as a game of matches.

Matches are displayed like this :

||

|||

||||

|||||

||||||

|||||||

||||||||

|||||||||

Each turn, player choose a line of matches and take 1 or 2 of them.

Players lose if they take the very last match on the board.

Such games are called 'Nim Games' and are very well-known. Techniques for finding the best optimal strategy are classical problems of game theory.

You should investigate in that direction, I think.

https://en.wikipedia.org/wiki/Nim

Answer 2

To answer the question asked, if I have understood the description of the game correctly, Alice has a winning strategy. It turns out that Sprague-Grundy theory for this game is quite simple, the Grundy number for any single digit $\ d\ $ being $\ d\left(\hspace{-0.6em}\mod 3\right)\ $.

One winning strategy for Alice is the following:

• On her first move, decrease the $8$ by $2$ to turn it into $6$.

• Whenever Bob decreases a digit divisible by $3$ by the amount $\ a\ $, decrease that same digit by a further $\ 3-a\ $ so that it remains divisible by $3$.

• Consider the $2^\mathrm{nd}$ and $5^\mathrm{th}$ digits, and the $4^\mathrm{th}$ and $7^\mathrm{th}$ digits to constitute two mated pairs. Each digit of a mated pair leaves the same remainder on division by $3$ as the other ($\ 2\left(\hspace{-0.6em}\mod 3\right)\ $ $=5\left(\hspace{-0.6em}\mod 3\right)=2\ $, and $\ 4\left(\hspace{-0.6em}\mod 3\right)=7\left(\hspace{-0.6em}\mod 3\right)=1\ $). Whenever Bob decreases one of the digits of a mated pair by the amount $\ a\ $, Alice either decreases the same one by $\ 3-a\ $, or the other of the two by $\ a\ $ (it will always possible for her to make at least one of those moves). This will ensure that, after Alice has moved, both digits of each mated pair will still leave the same remainder on division by $3$.

The game ends whenever the number $100000000$ is reached, and the above strategy of Alice's ensures that it will have to be Bob's move when that occurs.