Question

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. Can John stop the wish of Peter?

Answer 1

First I had constructed a few equations:

To make a number divisible by 9, they should:
x + 2y + 3z + 4p + 5q = 9n
x + y + z + p + q + n = 20

The lowest digits sum that they can achieve is 20 * 1 = 20; the highest - 20 * 5 = 100, so:
20 <= 9n <= 100

Since n must be an integer:
3 <= n <= 11

From that it is easy to see that there are only 9 possible variations that allow the numeber to be divisible by 9 versus 72 that make a number that isn't divisible by 9.

However, even thought odds are better to make a number that is not divisible by 9, we have to take into consideration the fact that both John and Peter are humans, so they base they try to make the best moves for them.

I thought about John starting with 1, then Peter would place 5 (he really wants it to be a multiple of 9) and John would place 4 to make the number give a remainder of 1, when their digits sum is divided by 9. However, playing like that Peter would soon notice the trick that John is using and start playing smarter placing 1 and waiting until the time when John has nothing to do, but place a number that would make a multiple of 9, like such:

J, P, J, P etc.
1545411141 <- we have 10 digits number divisible by 9, so if we make up a number with same digits in the same order twice as long we have a 20 digit number divisible by 9. Hence, my strategy has been crushed.

What kind of strategies could you suggest?

Answer 2

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. (why ?)

Answer 3

Maybe consider all the possible sequences. John wants to accomplish below by controlling the odd indexed terms :

\[\sum\limits_{i=1}^{20}a_i \ne 0 \pmod{9}\]
\(1\le a_i\le5\)

Answer 4

\[(a_1+a_3+\cdots + a_{19}) + (a_2+a_4 + \cdots a_{20}) \ne 0 \pmod{9}\]
\(1\le a_i\le5\)

Answer 5

I think my method is bad. We must look at the problem step by step..

Answer 6

Understood that. If it was more than 4, Peter could make up a number divisible by 9.

Answer 7

```
"So John has to make sure that the sum of the digits is 0, 1, 2, 3 mod 9
after his move. (why ?)"
Not sure why you excluded 4, 5, 6, 7, 8.
```

Suppose I'm John and you're Peter.

At 19th index, I enter a digit such that the sum of the digits thus far is 0, 1, 2, or 3 mod 9.
Can you enter a digit to make the overall sum 0 mod 9 ?

Answer 8

`Understood that. If it was more than 4, Peter could make up a number divisible by 9.`

Exactly

Answer 9

So, for the first move John can place only 1, 2, or 3.
But what would be the best move for Peter after that? I think that we should analyze what are both player's best moves to find the solution.

Answer 10

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

So, seems that when John places 3, every leading move would open 1 more possible digit to place, compared to the first move.

Answer 11

@Kainui

Answer 12

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, 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. Unless Peter was very smart (in this case we should consider that), it should be possible to keep up the same pace forever.
I think that the tables are same for every move, but the part "If John placed x" should be changed to "If John got 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.


Am I right? Do anybody have any ideas how to solve this without writing all those tables? ;)

Answer 13

Posted the question on MSE, perhaps somebody there will answer it: http://math.stackexchange.com/questions/1939260/john-and-peter-are-writing-20-digits-long-number-using-only-1-2-3-4-and-5-pe

Answer 14

Solution to the problem has been posted on MSE. Onto trying to understand what they mean now :)

Answer 15

Looks nice, starting from the end is ineed a clever strategy here..

Answer 16

@ganeshie8 could you explain me the part of the accepted solution? "And in general, with 2n digits left to pick, Peter can force a win if the position is equivalent to 3n modulo 9." What is that "position" that they are talking about?

Answer 17

Consider the residues modulo 9 :
\[\{0,1,2,3,4,5,6,7,8,9\}\]

Answer 18

After each move, you add the digits entered thus far in mod 9.

Answer 19

You get one of those 9 residues. They are calling it a position.

Answer 20

A more proper name would be "state"

Answer 21

After each move, the game could be one of the 9 "states"(positions) based on the digit that you get when you add all the digits entered in modulo 9

Answer 22

@ganeshie8 Oh my! Is this a freely chosen word to follow or is it from some branch of mathematics? I saw that my question has been labeled as a combinatorics game theory one, but I don't really have an idea of what that is.