1
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ Not only Alice and Bob : you can play this game with a friend. Did you try? Do it, then get back with ideas. If you find yourself unable to deduce anything by playing, then work back from losing positions. $\endgroup$ – астон вілла олоф мэллбэрг Apr 3 at 12:14
  • $\begingroup$ Can the digits go negative? Like, if the first move was to $103456789$, can you decrease $0$ by $1$ to get $1(-1)3456789$? This still represents a positive integer, equal to $1\times 10^9+(-1)\times 10^8+3\times 10^7+\dots$. $\endgroup$ – Mike Earnest Apr 3 at 16:01
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\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.