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 USAJMO Problems/Problem 5"
m
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.
+
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  
+
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  
 
<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.
  
 
==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}}

Revision as of 19:55, 9 January 2024

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

We claim that the game will always end if and only if $\nu_{2}(n) < \nu_{2} (a)$ for all $n$ that are in the list of positive integers. First, we will prove the if direction. Notice that if Alice adds $a$ to $n,$ since we have \[\nu_{2} (ka+n) = \nu_{2} (n) < \nu_{2} (a)\] for all integers $k>0,$ eventually Bob will decrease $\nu_{2} (n)$ by $1,$ and Alice will not be able to change $\nu_{2} (n),$ and so $\nu_{2}(n)$ will eventually become $0.$ Similarly, all of the other numbers on the list will have the same fate as $n,$ and so, no matter what Bob or Alice do, the game will end. Now, if $\nu_{2} (n) \ge \nu_{2} (a),$ where $n$ 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 $\nu_{2} (n)$ by $1$ at a time, and so if $\nu_{2} (n) \le \nu_{2} (a),$ we need $\nu_{2} (n) = \nu_{2} (a)$ at some point. But, then, if this is true, take $n = 2^{k}(2m+1),$ and $a = 2^{k}(2\ell+1),$ and notice that \[a+n = 2^{k}(2m+1)+2^{k}(2\ell+1) = 2^{k}(2m+2\ell+2) = 2^{k+1}(m+\ell+1),\] so $\nu_{2}(a+n) > \nu_{2} (n).$ Thus, if Bob gets $\nu_{2} (n)$ equal to $\nu_{2} (a),$ Alice can simply add $a$ to $n,$ and then $\nu_{2} (n) > \nu_{2} (a)$ again. Thus, Alice can keep the game going forever, and hence we are done.

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_USAJMO_Problems/Problem_5&oldid=210374"