Difference between revisions of "2023 USAMO Problems/Problem 4"
m |
|||
| Line 19: | Line 19: | ||
Case 2: <math>v_2 (a)=1</math> | 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') | + | 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. | 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. | ||
| 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') | + | 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>+1. 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" | ||
Revision as of 23:26, 17 May 2023
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 +1. 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.
