Number-erasing game with multiples of 3

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Number-erasing game with multiples of 3

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2024 Mexican Mathematical Olympiad, Problem 6

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7 posts

#1 h Nov 6, 2024, 10:36 PM

Y by

Ana and Beto play on a blackboard where all integers from 1 to 2024 (inclusive) are written. On each turn, Ana chooses three numbers $a,b,c$ written on the board and then Beto erases them and writes one of the following numbers:
$a+b-c, a-b+c, ~\text{or}~ -a+b+c.$ The game ends when only two numbers are left on the board and Ana cannot play. If the sum of the final numbers is a multiple of 3, Beto wins. Otherwise, Ana wins. ¿Who has a winning strategy?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

705 posts

#3 h Nov 7, 2024, 6:07 AM • 1 Y

Y by YaoAOPS

Made an obvious mistake, will be fixed

This post has been edited 1 time. Last edited by bin_sherlo, Nov 20, 2024, 2:49 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

41 posts

IMD2

#4 h Nov 14, 2024, 11:26 PM

Y by

bin_sherlo wrote:

We claim that $B$ wins.
Rephrased Problem: There are $675$ times $1$ , $675$ times $2$ and $674$ times $0$ on a board. On each turn, $A$ chooses $a,b,c$ and $B$ writes one of $(a+b+c)+\{a,b,c\}$ and erases $a,b,c$ . After some turns, there will be two numbers on the board. If sum of the numbers written on the board is a multiple of $3$ , then $B$ wins and $A$ wins otherwise. Who wins?
We work on modulo $3$ .
$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 0&0&0&\rightarrow&0\\\hline 0&0&1&\rightarrow&1\\\hline 0&0&2&\rightarrow&2\\\hline 0&1&1&\rightarrow&0\\\hline 0&2&2&\rightarrow&0\\\hline 0&1&2&\rightarrow&0\\\hline 1&2&2&\rightarrow&1\\\hline 1&1&2&\rightarrow&2\\\hline 1&1&1&\rightarrow&1\\\hline 2&2&2&\rightarrow&2\\\hline \end{array}$ The parity of number of $1$ -number of $2$ does not change during this operations. Hence there will exist $0,0$ or $1,2$ at the end of the game as desired. $\blacksquare$

What about $1,1$ or $2,2$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

86 posts

IMUKAT

#5 h Nov 17, 2024, 1:25 AM

Y by

bin_sherlo wrote:

We claim that $B$ wins.
Rephrased Problem: There are $675$ times $1$ , $675$ times $2$ and $674$ times $0$ on a board. On each turn, $A$ chooses $a,b,c$ and $B$ writes one of $(a+b+c)+\{a,b,c\}$ and erases $a,b,c$ . After some turns, there will be two numbers on the board. If sum of the numbers written on the board is a multiple of $3$ , then $B$ wins and $A$ wins otherwise. Who wins?
We work on modulo $3$ .
$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 0&0&0&\rightarrow&0\\\hline 0&0&1&\rightarrow&1\\\hline 0&0&2&\rightarrow&2\\\hline 0&1&1&\rightarrow&0\\\hline 0&2&2&\rightarrow&0\\\hline 0&1&2&\rightarrow&0\\\hline 1&2&2&\rightarrow&1\\\hline 1&1&2&\rightarrow&2\\\hline 1&1&1&\rightarrow&1\\\hline 2&2&2&\rightarrow&2\\\hline \end{array}$ The parity of number of $1$ -number of $2$ does not change during this operations. Hence there will exist $0,0$ or $1,2$ at the end of the game as desired. $\blacksquare$

As above points out, this is an incomplete solution, and you need to be more careful to avoid 1, 1 and 2, 2 endings. Interestingly, the problem was proposed with this fakesolve as the solution, although the comitee was able to fix it. Indeed, several students fakesolved the problem this way during the exam.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

242 posts

#6 h Apr 2, 2025, 5:32 PM • 1 Y

Y by MS_asdfgzxcvb

Beto has a winning strategy. Look at $1,2,...,2024$ using mod 3. Denote $n_1, n_2$ and $n_0$ to the number of 1’s, 2’s and 0’s in the list at a given point in the game. Hence, the game starts with $n_1=n_2=675$ and $n_0 = 674$ . In other words, the game starts with an odd number of 1's and 2's, and an even number of 0's.

Beto’s strategy will begin by following the steps in Rule A (below). He’ll follow this rule until Ana selects (0,1,2).

$\text{Rule A} = \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 0&1&2&\rightarrow&0 \\\hline 0&0&1&\rightarrow&1 \\\hline 0&0&2&\rightarrow&2 \\\hline 0&1&1&\rightarrow&0 \\\hline 0&2&2&\rightarrow&0 \\\hline 1&2&2&\rightarrow&1 \\\hline 1&1&2&\rightarrow&2 \\\hline 0&0&0&\rightarrow&0 \\\hline 1&1&1&\rightarrow&1 \\\hline 2&2&2&\rightarrow&2 \\\hline \end{array}$
Say the game ends without Ana selecting (0,1,2). Note that none of the steps in Rule A change the parity of $n_1, n_2$ and $n_0$ , except for step (0,1,2) -> 0. Therefore, in this scenario, the only possibility for the game to end is with $n_1=n_2=1$ and $n_0=0$ . That is, the final numbers are (1,2), which sum is a multiple of 3. Beto wins.

Now, say Ana selects (0,1,2) before the game ends. Beto will follow step (0,1,2) -> 0, and immediately change its strategy. The new strategy is described in Rule B.

$\text{Rule B} = \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 0&1&2&\rightarrow&0 \\\hline 0&0&1&\rightarrow&2 \\\hline 0&0&2&\rightarrow&1 \\\hline 0&1&1&\rightarrow&0 \\\hline 0&2&2&\rightarrow&0 \\\hline 1&2&2&\rightarrow&1 \\\hline 1&1&2&\rightarrow&2 \\\hline 0&0&0&\rightarrow&0 \\\hline 1&1&1&\rightarrow&1 \\\hline 2&2&2&\rightarrow&2 \\\hline \end{array}$
Note that the only differences between Rule A and Rule B are cases (0,0,1) and (0,0,2).

Once Beto switches his strategy to Rule B, he’ll follow it until Ana selects one of these cases: (0,1,2), (0,0,1), (0,0,2). Note that these cases are the only ones in Rule B that change the parity of $n_1, n_2, n_0$ . Say the game ends while Beto is following Rule B, and Ana didn’t select any of the cases (0,1,2), (0,0,1), (0,0,2). Observe that, when Beto performed the step (0,1,2) -> 0, the parity of $n_1, n_2$ was flipped from odd to even, while keeping the parity of $n_0$ (even). Moreover, since $n_0$ is even, then $n_0 \geq 2$ . Thus, in this scenario, the game ends with $n_1=n_2=0$ and $n_0=2$ . That is, the final numbers are (0,0), which sum is a multiple of 3. Beto wins.

Finally, if Ana selects any of (0,1,2), (0,0,1), (0,0,2) while Beto is following Rule B, then the parity of $n_1, n_2, n_0$ will return to their initial state (i.e., odd, odd, even; respectively). Thus, Beto will switch its strategy back to Rule A. This switching strategy demonstrates that Beto can always win the game.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a