Is there any winning strategy?

302 Views Asked by At

a) Adam and Eve take turns writing one number each until they have 20 numbers in a row. Adam writes the first number, and the only numbers they can use are 1, 2, 3, 4, and 5. Eve tries to ensure that the 20-digit number obtained is divisible by 9. Can Adam prevent it?

(b) The same task as above, but this time Adam and Eve write a 30-digit number.

EDIT: I know that : "A natural number is divisible by 9 iff its checksum is." But i do not know how to continue from that.

3

There are 3 best solutions below

0
On BEST ANSWER

Following the hint of @donpartini, you can reduce the problem to summing integers in $S=\{1,2,3,4,5\}$ and considering the last value modulo $9$, i.e., observing numbers as values in $\mathbb{Z}/9$.

Let a round be a sequence of two turns, first by Adam and then by Eve. Suppose a round starts with a value $x\in\mathbb{Z}/9$, then Adam choses a value $a\in S$, followed by Eve chosing a value $e\in S$. The value is than updated to $$x_n = x+a+e \pmod 9. $$ Are there any values of $x_n$ that Eve can force, independently of the choice that Adam makes?
Yes, there is a single such value, and that is $x_n=x+6$. For any choice $a\in S$ of Adam, Eve can select $e=6-a\in S$, which forces $x_n = x + a + (6-a) = x + 6$.
Similarly, for any other choice of $y \in \mathbb{Z}/9\setminus\{x+6\}$, Adam can choose a move that prevents Eve from reaching $y$.
For $y\in(x+1,x+2,x+3,x+4,x+5,x+7,x+8,x)$, Adam will choose $(1,2,3,4,5,1,2,3)$ accordingly. This move forces $x_n \not=y$ no matter the choice of Eve.

A simple example, if we have $x=1$, Adam can prevent Eve from reaching $y=8$ by choosing $a=1$, and then $x+a+e\not= 8$ for any choice of $e\in S$.

This allows us to solve the problem in the following way:
Assume after $20$ rounds the final value is $x_n=0$, i.e., Eve wins. In order to force this outcome, the previous round must have started with $x=3$ (by inverting the previous formula $x=x_n-6$). But in order to force this, the round before must have started with $x=6$, and the one before with $x=0$, and so on. In particular round $20-n$ must start with value $x=3+3n$. In particular this means that the game at round $1$ (i.e. the beginning of the game) must start with the value $x=3+57 = 6 \pmod 9$. However this game starts with an empty number to which digits are added, which in our terminology means that it starts with the value $x=0$. This means that Eve does not have a winning strategy, and Adam has a winning strategy. Adam will simply prevent Eve from reaching values $3+3n$ in round $n$ as explained above.
If the game lasted for $21$ rounds (or any number of rounds which is a multiple of $3$), then Eve would have a winning strategy. Her strategy would be to return $6-a$ for any play $a$ of Adam.

3
On

Hint: A natural number is divisible by 9 iff its checksum is.

0
On

This turned out to be quite tedious to write out and I wasn't able to provide a full answer but a path with which to solve it I guess. I will try to give hints at points so you might be able to finish it from there without my following solutions.

Theoretical background: So the basic idea is just to look at the check sum at the different states of the game and work with that (since the sum is divisible by 9 iff the checksum is)

Furthermore we know that a number $x$ is divisible by $9$, if $x = 0 \mod 9$ ($\mod 9$ being the residual when dividing by 9). Basically saying that a number is divisible by $9$, iff, we can divide the number by 9 without residual).

As such we will only be looking at the checksum (c) of the current number $\mod 9$ and if $c = 0 \mod 9$ in the end Eve wins. Furthermore we know that if we have the checksum $c$ for n numbers chosen. If the next person choses the number b the checksum will be $c+b$ and as such we will look at $c+b \mod 9$.

As such in the following I will be refering to the modulo (class) of the checksum as the checksum.

Now to the game itself:

An approach could be reverse engineering the solution by looking at the last turns of the game.

Suppose that we have picked 18 Numbers (so its Adams turn) and he has to choose his next number. Now think about what would be the worst possible checksum in this case?

3. In this case whatever $x$ in $1$ to $5$ Adam would choose, Eve could choose $6-x$ and would win.

Now we know what Eve "wants" for this gamestate. In all the other checksums at this state Adam can guarantee that he still wins (try to understand this as well).

Now we want to look at Eves turn after 17 numbers have been chosen. Again we look at the current checksum c (in $0$ to $8$).

Try to find the checksums at this state which are good for Eve and Adam respectively.

For the checksums $0,1,2,7,8$, whatever Eve can play a number such that the new checksum is $3$ with which she can guarantee her win (see above). For the checksums $3,4,5,6$ Eve can not get the new checksum to be a $3$ and as such won't win (see above)

Now we can look at the Adams turn when 16 Numbers have been chosen. It is clear that if the checksum at this point is everything except for $6$ Adam can force himself to win.

From this point on one could go one with reverse engineering the strategies and finding out who wins. Maybe a cycle would pop up which would simplify the calculations a lot. One can at least say that the game is deterministic in the sense that from the start it is clear who would win if both players played optimally.

Maybe there is a better solution, I'd also be interested in one. I will definitely think about it and might refine my answer.

Edit: This would also lead to a solution for the second question with 30 numbers