Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2023 USAMO Problems/Problem 4"

(Created page with "==Problem== A positive integer <math>a</math> is selected, and some positive integers are written on a board. Alice and Bob play the following game. On Alice's turn, she must...")
 
m
 
(3 intermediate revisions by one other user not shown)
Line 4: Line 4:
  
 
After analyzing the integers on the board, Bob realizes that, regardless of what moves Alice makes, he will be able to force the game to end eventually. Show that, in fact, for this value of <math>a</math> and these integers on the board, the game is guaranteed to end regardless of Alice's or Bob's moves.
 
After analyzing the integers on the board, Bob realizes that, regardless of what moves Alice makes, he will be able to force the game to end eventually. Show that, in fact, for this value of <math>a</math> and these integers on the board, the game is guaranteed to end regardless of Alice's or Bob's moves.
 +
 +
 +
 +
==Solution 1==
 +
The contrapositive of the claim is somewhat easier to conceptualize: If it is not guaranteed that the game will end (i.e. the game could potentially last forever), then Bob is not able to force the game to end (i.e. Alice can force it to last forever). So we want to prove that, if the game can potentially last indefinitely, then Alice can force it to last indefinitely.
 +
Clearly, if there is <math>1</math> number on the board initially, all moves are forced. This means the claim is true in this specific case, because if the game "potentially" can last forever, this means it must last forever, since the game can only be played in one way. Ergo Alice can "force" this to occur because it is guaranteed to occur. Now we look at all cases where there is more than <math>1</math> number on the board.
 +
 +
 +
Case 1: <math>v_2 (a)=0</math>
 +
 +
The game lasts forever here no matter what. This is true because, if the game ends, it means the board was in some position <math>P</math>, Alice added <math>a</math> to some number on the board, and all the numbers now on the board are odd. If there are only odd numbers on the board in position <math>P</math>, Alice will add <math>a</math> to some number on the board, making it even, meaning this cannot have been the state <math>P</math> of the board. If at least one number n on the board is even, Alice can add <math>a</math> to a number other than <math>n</math>, meaning there is still at least 1 even number on the board, meaning this also cannot have been the state <math>P</math> of the board. This covers all possible boards when  <math>v_2 (a)=0</math>, so we're done.
 +
 +
 +
Case 2: <math>v_2 (a)=1</math>
 +
 +
If there is at least one number n on the board that is even, the game can also last forever. On any move, Alice will add <math>a</math> to this number <math>n</math> if and only if <math>v_2 (n)=1</math>. This way, the new number <math>n'= n+a</math> satisfies <math>v_2 (n') \geq 2</math>. If Bob does divides <math>n'</math> until <math>v_2 (n)=1</math>, Alice will again add <math>a</math> to <math>n</math> resulting in <math>v_2 (n') \geq 2</math>. This means that Alice can always keep an even number on the board for Bob to divide no matter how Bob plays.
 +
 +
If there is no even number on the board, then the game can clearly not last forever. No matter what Alice does, Bob will have no even number to divide after her move.
 +
 +
 +
General Case: <math>v_2 (a)=x</math>
 +
 +
In general, it seems to be the case that the game can last indefinitely for some given <math>a</math> if and only if there exists some number <math>n</math> on the board such that <math>v_2 (n) \geq v_2 (a)</math>, so we should aim to prove this.
 +
 +
1. "If"
 +
 +
Alice can apply a similar strategy to the strategy used in case 2. On any move, Alice will add <math>a</math> to <math>n</math> if and only if <math>v_2 (n)=v_2 (a)</math>. If she does this addition, then <math>v_2 (n') \geq v_2 (a)+1</math>, keeping an even number on the board. Even if Bob divides <math>n'</math> until <math>v_2 (n)=v_2 (a)</math>, Alice will apply the same strategy and keep <math>v_2 (n') \geq v_2 (a)+1</math>. Alice's use of this strategy ensures that there always exists some number n on the board such that <math>v_2 (n) \geq v_2 (a)</math>, ensuring there always exists an even number n on the board.
 +
 +
2."Only If"
 +
 +
If <math>v_2 (n) < v_2 (a)</math> for all n on the board, this means that Alice can never change the value of <math>v_2 (n)</math> for any <math>n</math> on the board. Only Bob can do this, and Bob will subtract <math>1</math> from each <math>v_2 (n)</math> until they are all equal to <math>0</math> (all odd), ending the game.
 +
 +
We've shown that the game can last indefinitely iff there exists some number <math>n</math> on the board such that <math>v_2 (n) \geq v_2 (a)</math>, and have shown that Alice can ensure the game lasts forever in these scenarios using the above strategy. This proves the contrapositive, proving the claim.
 +
 +
~SpencerD.
  
 
==Video Solution==
 
==Video Solution==
  
 
https://www.youtube.com/watch?v=Fbs9ncZuwGM
 
https://www.youtube.com/watch?v=Fbs9ncZuwGM
 +
 +
==See Also==
 +
{{USAMO newbox|year=2023|num-b=3|num-a=5}}
 +
{{MAA Notice}}

Latest revision as of 18:18, 6 October 2023

Problem

A positive integer $a$ is selected, and some positive integers are written on a board. Alice and Bob play the following game. On Alice's turn, she must replace some integer $n$ on the board with $n+a$, and on Bob's turn he must replace some even integer $n$ on the board with $n/2$. Alice goes first and they alternate turns. If on his turn Bob has no valid moves, the game ends.

After analyzing the integers on the board, Bob realizes that, regardless of what moves Alice makes, he will be able to force the game to end eventually. Show that, in fact, for this value of $a$ and these integers on the board, the game is guaranteed to end regardless of Alice's or Bob's moves.


Solution 1

The contrapositive of the claim is somewhat easier to conceptualize: If it is not guaranteed that the game will end (i.e. the game could potentially last forever), then Bob is not able to force the game to end (i.e. Alice can force it to last forever). So we want to prove that, if the game can potentially last indefinitely, then Alice can force it to last indefinitely. Clearly, if there is $1$ number on the board initially, all moves are forced. This means the claim is true in this specific case, because if the game "potentially" can last forever, this means it must last forever, since the game can only be played in one way. Ergo Alice can "force" this to occur because it is guaranteed to occur. Now we look at all cases where there is more than $1$ number on the board.


Case 1: $v_2 (a)=0$

The game lasts forever here no matter what. This is true because, if the game ends, it means the board was in some position $P$, Alice added $a$ to some number on the board, and all the numbers now on the board are odd. If there are only odd numbers on the board in position $P$, Alice will add $a$ to some number on the board, making it even, meaning this cannot have been the state $P$ of the board. If at least one number n on the board is even, Alice can add $a$ to a number other than $n$, meaning there is still at least 1 even number on the board, meaning this also cannot have been the state $P$ of the board. This covers all possible boards when $v_2 (a)=0$, so we're done.


Case 2: $v_2 (a)=1$

If there is at least one number n on the board that is even, the game can also last forever. On any move, Alice will add $a$ to this number $n$ if and only if $v_2 (n)=1$. This way, the new number $n'= n+a$ satisfies $v_2 (n') \geq 2$. If Bob does divides $n'$ until $v_2 (n)=1$, Alice will again add $a$ to $n$ resulting in $v_2 (n') \geq 2$. This means that Alice can always keep an even number on the board for Bob to divide no matter how Bob plays.

If there is no even number on the board, then the game can clearly not last forever. No matter what Alice does, Bob will have no even number to divide after her move.


General Case: $v_2 (a)=x$

In general, it seems to be the case that the game can last indefinitely for some given $a$ if and only if there exists some number $n$ on the board such that $v_2 (n) \geq v_2 (a)$, so we should aim to prove this.

1. "If"

Alice can apply a similar strategy to the strategy used in case 2. On any move, Alice will add $a$ to $n$ if and only if $v_2 (n)=v_2 (a)$. If she does this addition, then $v_2 (n') \geq v_2 (a)+1$, keeping an even number on the board. Even if Bob divides $n'$ until $v_2 (n)=v_2 (a)$, Alice will apply the same strategy and keep $v_2 (n') \geq v_2 (a)+1$. Alice's use of this strategy ensures that there always exists some number n on the board such that $v_2 (n) \geq v_2 (a)$, ensuring there always exists an even number n on the board.

2."Only If"

If $v_2 (n) < v_2 (a)$ for all n on the board, this means that Alice can never change the value of $v_2 (n)$ for any $n$ on the board. Only Bob can do this, and Bob will subtract $1$ from each $v_2 (n)$ until they are all equal to $0$ (all odd), ending the game.

We've shown that the game can last indefinitely iff there exists some number $n$ on the board such that $v_2 (n) \geq v_2 (a)$, and have shown that Alice can ensure the game lasts forever in these scenarios using the above strategy. This proves the contrapositive, proving the claim.

~SpencerD.

Video Solution

https://www.youtube.com/watch?v=Fbs9ncZuwGM

See Also

2023 USAMO (Problems • Resources)
Preceded by
Problem 3 		Followed by
Problem 5
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_USAMO_Problems/Problem_4&oldid=199259"