The digits of a calculator (with the exception of 0) are shown in the form indicated by the figure below, where there is also a button ``+": Invalid URL Two players $A$ and $B$ play in the following manner: $A$ turns on the calculator and presses a digit, and then presses the button ``+". $A$ passes the calculator to $B$, which presses a digit in the same row or column with the one pressed by $A$ that is not the same as the last one pressed by $A$; and then presses + and returns the calculator to $A$, repeating the operation in this manner successively. The first player that reaches or exceeds the sum of 31 loses the game. Which of the two players have a winning strategy and what is it?
Problem
Source: CentroAmerican & Caribbean MO 1999 Q3
Tags: algorithm, combinatorics proposed, combinatorics
nkouevda
25.01.2007 10:07
$B$ has a winning strategy:
Each time $B$ adds a number to the current sum, he should add $10-a$, where $a$ is the number $A$ added on his turn. This way, the sum will be $30$ at the end of the third turn (1 turn = both go once), and $A$ loses.
pontios
25.01.2007 11:37
i_like_pie wrote:
$B$ has a winning strategy:
Each time $B$ adds a number to the current sum, he should add $10-a$, where $a$ is the number $A$ added on his turn. This way, the sum will be $30$ at the end of the third turn (1 turn = both go once), and $A$ loses.
It seems that this problem isn't so simple. You are not able to do that at any case. For example, if he add 7 you can only add 1,4,8, or 9 By the way, I have found all the winning conditions, at each step. But I can't find a pattern I mean that, I can't find a formula to express the winning strategy. If I play this game I have to look to the table of the best moves See the table below. I made this table by a reccursive way, from the end to the beginning. The winner is the player $A$ Invalid URLInvalid URL The top of each column shows the current sum. You find the current sum and then you look at that column. You will find the best moves. If some move is prohibited, then you choose some other move, in the same column. So, when the player $A$ starts playing, he should press 3 or 9 exclusive. Say that $A$ presses 3 If then the player $B$ presses the number 9, we go to the sum 12. The best moves are 2,4,6. But $A$ can only press the number 6 (because the last pressed digit was 9). And so on.
We will express the state just with the current sum $S$
Let:
$BM(S)$ be the set of the best moves, when the sum is $S$
$N(a)$ be the set of the prohibited keys starting from the key $a$. So, every key in this set is in the same row or in the same column with $a$ exclusive.
${X(S)=\bigcap_{i\in BM(S)}{N(i)}}$
So, each $k\in X(S)$ is a key not connected to any of the best moves. That is, if we press the number $k$, starting from the state $S-k$, then the opponent won't be able to play some of the winning moves.
Clearly, if the sum is 30 then the player will loose. So there are not best moves on the state-30.
That is, $BM(30)=\emptyset$
The procedure is as follows:
$\forall k \in X(S)$ find $S-k$. Then add $k$ to the set $BM(S-k)$
If you lead your opponent to the state-30, you'll win. So, $k$ is a best move on the state $30-k$.
In other notations, $k\in BM(30-k), \ \ \forall k \in \{1,2,...,9\}$
Now in the state-29.
The set $BM(29)$ is already formed; it is $BM(29)=\{1\}$
We have $X(29)=N(1)=\{1,5,6,8,9\}$.
So we repeat the procedure:
$\forall k \in N(1)$ find $S-k$. Then $k\in BM(S-k)$
In our example it is S=29. Then
$S-1=28 \Rightarrow 1 \in BM(28)$
$S-5=24 \Rightarrow 5 \in BM(24)$
$S-6=23 \Rightarrow 6 \in BM(23)$
$S-8=21 \Rightarrow 8 \in BM(21)$
$S-9=20 \Rightarrow 9 \in BM(20)$
After that, we continue to the state-28, knowing that $BM(28)=\{1,2\}$. Then $X(28) = N(1) \cap N(2)$
And so on...
The above algorithm helps us to find all the winning moves. But you can't have this table on your mind while you are playing. Can somebody see a pattern in this table? Can we find some useful formula for it??
nkouevda
26.01.2007 02:11
Ahh... While I was solving the problem I forgot about that complication.
whiwho
31.07.2016 17:33
Let’s say number A starts. He picks number 9. The sum now equals 9. Let’s now assume every B’s movement. B picks 8. The sum is now 17. Now since we are A, we decide to pick 9 again. The sum is 26 now. B’s possible movements now are {8,7,6,3}, and out of those ones, only the last one can be picked to not overpass the limit. B picks 3. The sum is 29. And A picks 1 now, so the sum is 30 and A has won the game. B picks 7. The sum is 16. We pick 9. The sum is 25. The possible B’s movements are {8,7,6,3} and only “3” is a pickable choice. B picks 3. The sum is 28. A picks 2. The sum is 30 and A wins again. B picks 6. The sum is 15. A picks 5. The sum is 20. And we may see, every number B picks, A can chose the opposite option to make it sum 30 and take the game. {2:8,8:2,4:6,6:4} B picks 3. The sum is 12. A picks 6. The sum is 18. Now B has 4 new choices: B picks either 3 or 9. The sum is either 21 or 27, so A will just have to pick the other one and make it add 30. A wins the game. B picks 4. The sum is 22. A picks 6. The sum is 28 and since we are in 6, the only available choices are {9,5,4,3} which all lend to pass the max sum and A wins the game. B picks 5. The sum is 23. A picks 6. The sum is 29. And, as in the previous example. A has won the game since there aren't more possible choices.
whiwho
31.07.2016 17:33
A always wins by the way.