Difference between revisions of "2023 USAMO Problems/Problem 4"
m |
m |
||
(One intermediate revision by one other user not shown) | |||
Line 30: | Line 30: | ||
1. "If" | 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)</math> | + | 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" | 2."Only If" | ||
Line 43: | Line 43: | ||
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 19:18, 6 October 2023
Contents
Problem
A positive integer 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
on the board with
, and on Bob's turn he must replace some even integer
on the board with
. 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 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 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
number on the board.
Case 1:
The game lasts forever here no matter what. This is true because, if the game ends, it means the board was in some position , Alice added
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
, Alice will add
to some number on the board, making it even, meaning this cannot have been the state
of the board. If at least one number n on the board is even, Alice can add
to a number other than
, meaning there is still at least 1 even number on the board, meaning this also cannot have been the state
of the board. This covers all possible boards when
, so we're done.
Case 2:
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 to this number
if and only if
. This way, the new number
satisfies
. If Bob does divides
until
, Alice will again add
to
resulting in
. 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:
In general, it seems to be the case that the game can last indefinitely for some given if and only if there exists some number
on the board such that
, 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 to
if and only if
. If she does this addition, then
, keeping an even number on the board. Even if Bob divides
until
, Alice will apply the same strategy and keep
. Alice's use of this strategy ensures that there always exists some number n on the board such that
, ensuring there always exists an even number n on the board.
2."Only If"
If for all n on the board, this means that Alice can never change the value of
for any
on the board. Only Bob can do this, and Bob will subtract
from each
until they are all equal to
(all odd), ending the game.
We've shown that the game can last indefinitely iff there exists some number on the board such that
, 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.