Difference between revisions of "2023 USAJMO Problems/Problem 5"
Mr.sharkman (talk | contribs) m |
Mr.sharkman (talk | contribs) |
||
(3 intermediate revisions by the same user not shown) | |||
Line 6: | Line 6: | ||
==Solution== | ==Solution== | ||
We claim that the game will always end if and only if <math>\nu_{2}(n) < \nu_{2} (a)</math> for all <math>n</math> that are in the list of positive integers. | We claim that the game will always end if and only if <math>\nu_{2}(n) < \nu_{2} (a)</math> for all <math>n</math> that are in the list of positive integers. | ||
− | First, we will prove the if direction. Notice that if Alice adds <math>a</math> to <math>n,</math> since we have <cmath>\nu_{2} (ka+n) = \nu_{2} (n) < \nu_{2} (a)</cmath> for all integers <math>k>0,</math> eventually Bob will decrease <math>\nu_{2} (n)</math> by <math>1,</math> and Alice will not be able to change <math>\nu_{2} (n),</math> and so <math>\nu_{2}(n)</math> will eventually become <math>0.</math> Similarly, all of the other numbers on the list will have the same fate as <math>n,</math> and so, no matter what Bob or Alice do, the game will end. | + | |
− | Now, if <math>\nu_{2} (n) \ge \nu_{2} (a),</math> where <math>n</math> is one of the numbers in the list, we will prove that Alice can keep the game going forever. Notice that Bob can only decrease <math>\nu_{2} (n)</math> by <math>1</math> at a time, and so if <math>\nu_{2} (n) \le \nu_{2} (a),</math> we need <math>\nu_{2} (n) = \nu_{2} (a)</math> at some point. But, then, if this is true, take <math>n = 2^{k}(2m+1),</math> and <math>a = 2^{k}(2\ell+1),</math> and notice that | + | |
+ | First, we will prove the if direction. Notice that if Alice adds <math>a</math> to <math>n,</math> since we have <cmath>\nu_{2} (ka+n) = \nu_{2} (n) < \nu_{2} (a)</cmath> for all integers <math>k>0,</math> eventually Bob will decrease <math>\nu_{2} (n)</math> by <math>1,</math> and Alice will not be able to change <math>\nu_{2} (n),</math> and so <math>\nu_{2}(n)</math> will eventually become <math>0.</math> | ||
+ | |||
+ | Similarly, all of the other numbers on the list will have the same fate as <math>n,</math> and so, no matter what Bob or Alice do, the game will end. | ||
+ | |||
+ | |||
+ | Now, we complete the only if direction, i.e. if <math>\nu_{2} (n) \ge \nu_{2} (a),</math> where <math>n</math> is one of the numbers in the list, we will prove that Alice can keep the game going forever. | ||
+ | |||
+ | |||
+ | Notice that Bob can only decrease <math>\nu_{2} (n)</math> by <math>1</math> at a time, and so if <math>\nu_{2} (n) \le \nu_{2} (a),</math> we need <math>\nu_{2} (n) = \nu_{2} (a)</math> at some point. But, then, if this is true, take <math>n = 2^{k}(2m+1),</math> and <math>a = 2^{k}(2\ell+1),</math> and notice that | ||
<cmath> a+n = 2^{k}(2m+1)+2^{k}(2\ell+1) = 2^{k}(2m+2\ell+2) = 2^{k+1}(m+\ell+1),</cmath> so | <cmath> a+n = 2^{k}(2m+1)+2^{k}(2\ell+1) = 2^{k}(2m+2\ell+2) = 2^{k+1}(m+\ell+1),</cmath> so | ||
<math>\nu_{2}(a+n) > \nu_{2} (n).</math> | <math>\nu_{2}(a+n) > \nu_{2} (n).</math> | ||
Thus, if Bob gets <math>\nu_{2} (n)</math> equal to <math>\nu_{2} (a),</math> Alice can simply add <math>a</math> to <math>n,</math> and then <math>\nu_{2} (n) > \nu_{2} (a)</math> again. Thus, Alice can keep the game going forever, and hence we are done. | Thus, if Bob gets <math>\nu_{2} (n)</math> equal to <math>\nu_{2} (a),</math> Alice can simply add <math>a</math> to <math>n,</math> and then <math>\nu_{2} (n) > \nu_{2} (a)</math> again. Thus, Alice can keep the game going forever, and hence we are done. | ||
+ | ~Mr.Sharkman | ||
==See Also== | ==See Also== | ||
{{USAJMO newbox|year=2023|num-b=4|num-a=6}} | {{USAJMO newbox|year=2023|num-b=4|num-a=6}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 22:41, 9 January 2024
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
We claim that the game will always end if and only if for all
that are in the list of positive integers.
First, we will prove the if direction. Notice that if Alice adds to
since we have
for all integers
eventually Bob will decrease
by
and Alice will not be able to change
and so
will eventually become
Similarly, all of the other numbers on the list will have the same fate as and so, no matter what Bob or Alice do, the game will end.
Now, we complete the only if direction, i.e. if where
is one of the numbers in the list, we will prove that Alice can keep the game going forever.
Notice that Bob can only decrease by
at a time, and so if
we need
at some point. But, then, if this is true, take
and
and notice that
so
Thus, if Bob gets
equal to
Alice can simply add
to
and then
again. Thus, Alice can keep the game going forever, and hence we are done.
~Mr.Sharkman
See Also
2023 USAJMO (Problems • Resources) | ||
Preceded by Problem 4 |
Followed by Problem 6 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.