John and Peter are writing 20 digits long number using only 1, 2, 3, 4 and 5. Peter wants the result to be a multiple of 9. Could John stop Peter?

Question

Problem: John and Peter are writing 20 digits long number using only 1, 2, 3, 4 and 5. First digit is written by John, then Peter and so on. Peter wants the resulting number to be divisible by 9. Could John destroy the wish of Peter?

My attempt: If the sum of the digits is divisible by 9, then the number is divisible by 9. So John has to make sure that the sum of the digits is 0, 1, 2, 3 mod 9 after his move. In other words, he can place either 1, 2, or 3.

If John placed 2, Peter placed 1, then John would have only 1, 2, 3, 4, 5 to place;

If John placed 2, Peter placed 2, then John would have only 1, 2, 3, 4 to place;

If John placed 2, Peter placed 3, then John would have only 1, 2, 3, 5 to place;

If John placed 2, Peter placed 4, then John would have only 1, 2, 4, 5 to place;

If John placed 2, Peter placed 5, then John would have only 1, 3, 4, 5 to place;

If John placed 1, Peter placed 1, then John would have only 1, 2, 3, 4, 5 to place;

If John placed 1, Peter placed 2, then John would have only 1, 2, 3, 4, 5 to place;

If John placed 1, Peter placed 3, then John would have only 1, 2, 3, 4 to place;

If John placed 1, Peter placed 4, then John would have only 1, 2, 3, 5 to place;

If John placed 1, Peter placed 5, then John would have only 1, 2, 4, 5 to place;

So, it seems that for John it's best to start with 1. However, we should look at a table of values that John could chose from to make remainder of 1, 2, or 3 mod 9:

If John placed 1, Peter placed 1, then John would have nothing to place;

If John placed 1, Peter placed 2, then John would have nothing to place;

If John placed 1, Peter placed 3, then John would have nothing to place;

If John placed 1, Peter placed 4, then John would have only 5 to place;

If John placed 1, Peter placed 5, then John would have only 4, 5 to place;

If John placed 2, Peter placed 1, then John would have nothing to place;

If John placed 2, Peter placed 2, then John would have nothing to place;

If John placed 2, Peter placed 3, then John would have only 5 to place;

If John placed 2, Peter placed 4, then John would have only 4, 5 to place;

If John placed 2, Peter placed 5, then John would have only 3, 4, 5 to place;

If John placed 3, Peter placed 5, then John would have only 2, 3, 4 to place;

If John placed 3, Peter placed 4, then John would have only 3, 4, 5 to place;

If John placed 3, Peter placed 3, then John would have only 4, 5 to place.;

If John placed 3, Peter placed 2, then John would have only 5 to place;

If John placed 3, Peter placed 1, then John would have nothing to place;

So, basically John should start with 3, then act according to the table. I think that the tables are same for every move, but the part "If John placed x" should be changed to "If John placed something to make a remainder of x".

So, the answer is no, it is not possible for John to destroy Peter's plan to make a multiple of 9. Unless, Peter is a normal human being.

My problems with this: I don't think that it's very elegant to use tables in solutions, so could anyone help me with that? Also, am I really correct?

Answer 1

The sure way to analyze such games is to work backwards from the end of the game. As you notice, only the sum of the digits modulo 9 matter, so we can simply list which of the 9 positions are winning for each player at each step of the game.

With 0 digits left to pick, $\{1,2,3,4,5,6,7,8\}$ win for John and $\{0\}$ wins for Peter.

At the step before that, Peter will win if the position is one he can reach $0$ from. Otherwise John wins.

With 1 digit left to pick, $\{4,5,6,7,8\}$ win for Peter, and $\{0,1,2,3\}$ win for John.

At the step before that, John will win if the position is one he can reach 0, 1, 2, or 3 from. Otherwise Peter wins.

With 2 digits left to pick, $\{0,1,2,4,5,6,7,8\}$ win for John, and $\{3\}$ wins for Peter.

But this is essentially the same situation as the one with $0$ digits left to pick, in that there is a single residue that will win for Peter, and everything else wins for John. So the analysis will repeat itself every two turns -- just at a different point in the cycle of possible residues -- and we can fast-forward:

With 4 digits left to pick, $\{6\}$ wins for Peter and everything else goes to John.

With 6 digits left to pick, $\{0\}$ wins for Peter and everything else wins for John.

And in general, with $2n$ digits left to pick, Peter can force a win if the position is equivalent to $3n$ modulo $9$.

Thus, with 20 digits left to pick, Peter will win if the position is equivalent to $30$ modulo $9$. But the actual starting position is $0$ (since no digits are picked yet), and $0\not\equiv 30\pmod 9$. So John has a winning strategy.

---

In particular, this analysis lets us construct an easy winning strategy for John:

Pick $1$ as the first digit. For each of the next nine digits John gets to pick, choose $6-a$ where $a$ is the digit Peter has just picked. Then when Peter is about to make his last pick, the sum of the digits will be $1+9\times 6$, and there is no way for Peter to make that into a multiple of $9$ by adding something between $1$ and $5$.