I split it into even and odd: When it is odd, then Bob cannot force a win anyways or trivially there is only one number on the board and so the moves are forced For even, just do some stuff with v_2 and get that the integers must always go down to all odds and we are done

My guess: if exists V2(x)>=V2(a), where x is any number written on the board, then the game will never ends. Otherwise the game will ends regardless how Alice and Bob move.

elaboration to @2above: For $a$ is even, show that $v_2(m) < v_2(a)$ for all integers $m$ on the board. Then Alice's move make no impact on $v_2(m)$ since $v_2(m+a)=v_2(m)$. No matter what the two do, Bob will eventually run out of choices.

Rewrite each number as its 2-adic valuation; then the problem becomes equivalent to moving $n \geq 2$ tokens on the graph below, where Alice's moves are denoted by magenta edges, and Bob's moves --- cyan. (The picture shows an example for $\nu_2(a)=2$.) [asy][asy] unitsize(1cm); usepackage("kpfonts"); real v_rad = 0.3; void vertex(real x, real y, pen p, string s) { filldraw(circle((x, y), v_rad), p); label(s, (x, y)); } pen RED = lightgrey; pen apen = linewidth(1.5)+fuchsia; pen bpen = linewidth(1.5)+heavycyan; draw((0,0)..(0,0.6)..(0,0), apen); draw((1,0)..(1,0.6)..(1,0), apen); draw((2,0)--(3,0), apen); draw((2,0)..(2.5,0.6)..(4,0), apen); draw((2,0)..(2.5,0.6)..(5,0), apen); draw((2,0)..(2.5,0.6)..(6,0), apen); for (int i = 1; i <= 6; ++i) { draw((i,0)..((2i-1)/2,-0.6)..(i-1+0.1,-0.3), bpen, arrow = Arrow(TeXHead)); } vertex(0, 0, RED, "$0$"); vertex(1, 0, RED, "$1$"); vertex(2, 0, RED, "$2$"); vertex(3, 0, RED, "$3$"); vertex(4, 0, RED, "$4$"); vertex(5, 0, RED, "$5$"); vertex(6, 0, RED, "$6$"); label("$\dots$", (6.75,0)); [/asy][/asy] If Alice has any tokens to the right of or at $\nu_2(a)$, then she wins by stalling until Bob moves a token there, and then ``shooting'' that token outwards so that Bob has to move it again. Otherwise it's clear that Alice is basically useless, and Bob is playing with a ticking fuse until the game is over.

If all $n\in S$ satisfy $\nu_2(n)<\nu_2(a)$, then \[\sum_{n\in S}\nu_2(n)\]always decreases. Otherwise Alice can choose some element $n\in S$ where $\nu_2(n)\ge\nu_2(a)$ and increment $n$ if and only if $\nu_2(n)=\nu_2(a)$. Also, one element case is vacuously true but should be a dock if ignored.

asdf334 wrote: Also, one element case is vacuously true but should be a dock if ignored. "some positive integers" is plural, and is never equal to 1.

kred9 wrote: asdf334 wrote: Also, one element case is vacuously true but should be a dock if ignored. "some positive integers" is plural, and is never equal to 1. "zero integers" is valid grammatically

YaoAOPS wrote: "zero integers" is valid grammatically And last I checked zero is not one, so my point stands.

kred9 wrote: asdf334 wrote: Also, one element case is vacuously true but should be a dock if ignored. "some positive integers" is plural, and is never equal to 1. wait i never noticed this--i suppose you're right

"Some" positive integers doesn't imply there cant be 1. If I had one apple and someone said I have some apples they would be correct.

pray 4 no combo games on 2024 usamo :plz: i want more geo and less combo :plz:

It's been a general consensus in math competitions to ignore grammar. Specifically, it's not common for a problem to have answer 1 and the type requested being indicated in plural. Funny (but true) story: The one element case took me longer to resolve than the rest of the problem.

2 Combo Games on Day 2? Hellish contest for me If one number is on the board every move is forced and the problem is obvious. If $a$ is odd, every move Alice makes swaps the parity of a number, so a terminal state can always be avoided by Alice by a simple backtracking argument. Assume $a$ even. The key idea is that Alice can keep the game going forever iff there is a number $t$ on the board with $\nu_{2}(t) \geq \nu_{2}(a)$. For the if direction, she can simply preserve the condition $\nu_{2}(t) \geq \nu_{2}(a)$ because $\nu_{2}(x+y)>\nu_{2}(x)$ if $\nu_{2}(x)=\nu_{2}(y)$ For the only if direction, let the set of numbers on the board be $S$. Then $\sum_{n \in S} \nu_{2}(n)$ is a decreasing monovariant because $\nu_{2}(x+y)=\min \left(\nu_{2}(x), \nu_{2}(y)\right)$ for $\nu_{2}(x) \neq \nu_{2}(y)$. Thus it eventually hits zero and the game ends. In fact, it is forced to eventually hit zero, and the game is forced to end. Done.

bobthegod78 wrote: It's been a general consensus in math competitions to ignore grammar. Specifically, it's not common for a problem to have answer 1 and the type requested being indicated in plural. Funny (but true) story: The one element case took me longer to resolve than the rest of the problem. bruh what? if Bob can force an end to the game then an end is inevitable because neither players have any choice for their move...

sixoneeight wrote: bobthegod78 wrote: It's been a general consensus in math competitions to ignore grammar. Specifically, it's not common for a problem to have answer 1 and the type requested being indicated in plural. Funny (but true) story: The one element case took me longer to resolve than the rest of the problem. bruh what? if Bob can force an end to the game then an end is inevitable because neither players have any choice for their move... yeah, i was being stupid. took me like 5 minutes for the 1 case because i was like "ok what happens if v_2((n+a)/2) = v_2(n) always and i was doing some induction argument until i realized it was fixed.

Let $S$ be the set of numbers on the board. Claim: Alice can keep the game going for infinite moves if and only if there exists $t \in S$ with $\nu_{2}(t) \geq \nu_{2}(a)$. Proof: Suppose the claim is $A \iff B$. ($-B \Rightarrow -A$) Look at \[ X = \sum_{n \in S} \nu_2(n). \]Note that $X$ strictly decreases with each move, so $X$ eventually reaches $0$, which forces the game to end. ($B \Rightarrow A$) Just note that $\nu_2(x)=\nu_2(y)$ implies $\nu_2(x+y)>\nu_2(x)$. $\blacksquare$ Hence the conclusion follows. $\blacksquare$ Remark. This gave me vibes of 2012 C1/2020 JMO #1, which inspired me to use a simple monovariant.

We notice JMO-5/AMO-4 wrote: some positive integers are written on a board. and move on, If $a$ is odd, Alice chooses an even number $n$ and the game would end. If $a$ is even, we have two cases. For all $n\in S$, such that $\nu_2(n)<\nu_2(a)$. We have that $\nu_2(n+a)=\nu_2(n)$. So, $\nu_2$'s decreases by $1$ after a complete move and would tend to become $0$ and the game would end. $\nu_2(n)\rightarrow \nu_2(n)-1\rightarrow \dotsc \rightarrow 0$ From here, we show that the game would not end if $\nu_2(n)\geq \nu_2(a)$. It is because $\nu_2(x+y)\geq \nu_2(x)+1$ if $\nu_2(x)=\nu_2(y)$

for some reason i couldn't solve this in the contest... We claim that the game will end iff every $n$ on the board satisfy $\nu_2(n)<\nu_2(a)$. The one number case is trivial, with every move being forced. Notice \[\sum_{n\in S}\nu_2(n)\] is strictly decreasing, implying the game will end if $\nu_2(n)<\nu_2(a)$. Otherwise, choose an element $n$ such that $\nu_2(n) \ge \nu_2(a)$ and we have $\nu_2(n+a) \ge \min(\nu_2(n), \nu_2(a)) = \nu_2(n)$. In other words, the game will never end by simply adding $a$ to $n$ repeatedly. $\square$

The case $N = 1$ is obvious. Also, note that $a$ cannot be odd. Claim: There does not exist a number $x$ such that $v_2(x) \geq v_2(a)$. Assume by contradiction there does. Let this number have position $i$ and original value $x$. Then if $v_2(x) = v_2(a)$, Alice should add $a$ to $x$ since $v_2(x+a) > v_2(x)$. But note that in order to end the game, Bob must decrease the $v_2$ of this $i$th number, so the $v_2$ of the $i$th number will be $v_2(a)$ again (in the meantime Alice should not touch this number). Then Alice can just add $a$ to it and the game will go on. $\square$ Thus, all the numbers on the board $x$ satisfy $v_2(x) < v_2(a)$. Clearly then adding by $a$ does nothing to the $v_2$ of any number, so the sum of the $v_2$ of all numbers on the board is a monovariant. The game is guaranteed to end. $\blacksquare$

We claim the game ends iff $\forall n\in \text{board}$, $v_2(n)<v_2(a)$. First note that: \[v_2(n+a)\geq \min(v_2(n),v_2(a)),\]equality when $v_2(n)\neq v_2(a)$. Claim: If $v_2(n)<v_2(a)$, the game will end. Proof: Note that: \[v_2(n+a)=v_2(n).\]Therefore, Alice can never increase the value of $v_2(n)$ in any of her turns. On Bob's turn, he must do the following to at least one $n$: \[v_2(n)\rightarrow v_2(n)-1,\]unless its even, in which the game is already over. As Bob has full control of $v_2(n)$, consider: \[\sum_{n\in \text{board}}v_2(n),\]which must be strictly decreasing on Bob's turn, therefore, eventually turning into $0$ $\square$ Claim: If $\exists$ at least one $n$ such that, $v_2(n)\geq v_2(a)$, the game will not end. Proof: Note that: \[v_2(n+a)\geq v_2(a).\]If Bob transforms this, it must become: \[v_2(a)-1,\]unless $v_2(a)=0$, which will not be equal to $v_2(n+a)$ if $n$ is also odd, which can happen. After this, Alice can transform it to $v_2(a)-1+1=v_2(a)$. Basically, Alice can always increase the $v_2(a)$ by $1$, making the game never end, as desired $\square$

Define $S$ as the set of numbers on the board. We will show that Bob being able to force an end and the game ending inevitably are equivalent to $v_2(k) < v_2(a)$ for all $k \in S$. We start by noting that both players moves are forced in the $N=1$ case, so it is trivial. We proceed by assuming $N \ge 1$. Claim 1: If $v_2(k) < v_2(a)$ for all $k$, the game must end regardless of either Alice or Bob's moves. Notice that Alice cannot change the value of $\sum_{k \in S} v_2(k)$, as $v_2(k+a)=v_2(k)$. On the other hand, Bob will always decrease the sum by exactly 1 each move. ${\color{blue} \Box}$ Claim 2: If $v_2(k) \ge v_2(a)$ for some $k$, Alice can force the game to continue indefinitely. Alice can always perform the following algorithm on this entry to always ensure $v_2(k)>v_2(a)$ following her move, which ensures the game cannot end: If $v_2(k)=v_2(a)$, add $a$ to this term, as $v_2(k+a)>v_2(k)$. If $v_2(k)>v_2(a)$, add $a$ to some other term. ${\color{blue} \Box}$

Onk. First we find all instances in which Bob can force a win. We claim Bob can force a win if and only if $\nu_2(a) > \nu_2(n)$ for all $n$ on the board. This is just from the fact that, \begin{align*} \nu_2(a + n) \geq \min(\nu_2(a), \nu_2(n)) \end{align*}with equality if and only if $\nu_2(a) = \nu_2(n)$. If some integer $n$ does satisfy $\nu_2(n) \geq \nu_2(a)$ then Alice can just keep adding $a$ to $n$. Else, the $\nu_2(n)$ for all $n$ on the board is strictly decreasing so Bob must run out of moves. Now this in fact finishes as if $\nu_2(n) < \nu_2(a)$ for all $a$, then regardless the game must end.

Assume $N > 1$, because the case $N = 1$ is easy (we wil deal with it later). If there exists some number on board $k$ with $\nu_2(k) = \nu_2(a)$, I claim that the game will never end. Just consider that one number for now, and nothing else (we can do this because if this number can't be reduced to $1$ with a finite number of turns, even if the rest can be, it is pointless). The first operation Alice does will increase $\nu_2$ (because $\nu_2(x) + \nu_2(y) > \nu_2(x + y)$ for $\nu_2(x) = \nu_2(y)$). The first operation Bob does will decrease $\nu_2$ (maybe take it back to $\nu_2(a)$, or take it to something greater than $\nu_2(a)$). The point is, the next operation Alice does, she can once again take the $\nu_2$ to $\nu_2(a)$, so this will repeat indefinitely, and thus the game can't end in this case. In fact, more generally, if we have some number on board $k$ with $\nu_2(k) > \nu_2(a)$, I claim that the game will never end. Assume the game ends. The following strategy for Alice: Make ``waiting moves" on any other number except $k$, until Bob makes a move which makes $k$ such that $\nu_2(k) = \nu_2(a)$ (at some point this must occur because if we have assumed the game ends, then at some point $\nu_2(k)$ must pass $\nu_2(a)$, because in the end all numbers are odd). But after this, Alice can just replicate the previous strategy on $k$ to make the game go on indefinitely. So, all numbers $k$ on board must have $\nu_2(k) < \nu_2(a)$, so any operation Alice makes won't have any effect on the sum of $\nu_2$s of all the numbers on the board, and every operation Bob makes decreases it by exactly one, so at some point all $\nu_2$s must become $0$, regardless of whether Bob plays sensibly or not. (For $N = 1$, the same thing holds, with a notable difference that only $\nu_2(x) = \nu_2(a)$, where $x$ is the only number written on blackboard, will make the game go on indefinitely, because for $\nu_2(x) > \nu_2(a)$, Alice takes it to $a$, then Bob takes it to $a - 1$, and now Alice is powerless)

Solution- Denote the initial numbers by $x_1,x_2,x_3 \cdots $ Claim-: If for any $x_i$ we have $\nu_2(x_i) \geq \nu_2(a)$ the game is endless Proof- For the equality case - $\nu_2(a) \xrightarrow{\text{Alice}} \nu_2(a)+k \xrightarrow {\text{Bob}} \nu_2(a)$ or $\nu_2(a)+m$ where $m<k $. If its $\nu_2(a)$ all the time then the game repeats and does not end. If its $\nu_2(a)+m$ then its our other case $\nu_2(x_i)> \nu_2(a)$ in which Alice will just waits until Bob turns $\nu_2(a)+m$ to $\nu_2(a)$ and from there she will repeat the above strategy. Thus, for all $x_i$ we have $\nu_2(x_i) < \nu_2(a)$ Alice here has no control of $\nu_2$'s here as $\nu_{2}(x+a)=\min\left\{\nu_{2}(x),\nu_{2}(a)\right\} = \nu_{2}(x)$. Thus, Bob can go down until he reaches $\nu_2(x)=0$ for all $x_i$'s without any interruption and hence is successful in finishing the game.

Okay.... I had to look at a hint to consider $\nu_2.$ Let $b_i$ denote the $2$-adic valuation of the $i$th number on the board, and let $m$ denote the $2$-adic valuation of $a.$ $N = 1:$ If $b_1 < m,$ then $b_1$ will always decrease until it becomes $0.$ Thus Bob forces a win AND the game is over either way, and we are fine, Otherwise, if $b_1 \ge m,$ then $b_1$ will keep decreasing until it reaches $m$ for the first time, at which point the $p$-adic valuation doesn't decrease at all. We thus get stuck in an infinite loop, so the game can never end. Once again okay. Now assume that $N > 1.$ First, note that if $b_i < m$ for all $1 \le i \le N,$ by $2$-adic addition rules, the sum of all the $b_i$ will never increase on Alice's move, and will always decrease by $1$ on Bob's move. Therefore, the game is doomed to end. On the other hand, if there is some $i$ such that $m \ge b_i,$ then Alice can act on this $i.$ Alice can always increase the $i$th number on the board by $a$ to increase $b_i$ by at least $1,$ and Bob's move will decrease exactly one of the $b_i$ by $1.$ Thus the sum of the $b_i$ can never decrease, thus the game lasts forever. We have just proven that the game is doomed to end if and only if $m > b_i$ for all $1 \le i \le N.$ Therefore, we must show that if Bob can force the game to end regardless of what Alice does, then $m > b_i$ for all $1 \le i \le N.$ In fact, the contrapositive holds, as demonstrated above. Hence we are done!

I WoN ThE GaMe

did this with thooms note: we had an ela skill issue For $N = 1$, it is trivial as all moves are forced, and all games that Bob wins are forced. From now on, we are considering under the assumption that $N > 1$. If $2 \nmid a$, Bob cannot win if Alice plays optimally. Alice can always flip the parity of any odd numbers on her turn, and effectively stall out the game for all of eternity. Therefore, we must consider when $2 \mid a$. Denote $a = m \cdot 2^k$, where $m$ is an arbitrary odd integer and $k$ is an arbitrary positive integer. If there exists some number $n$ such that $\nu_2(n) \geq k$, then Bob never wins; Alice can just play until Bob reduces $n$ such that $\nu_2(n) = k$, and Alice can add $a$ to the number, increasing its $\nu_2$ value, and effectively keeping $\nu_2(n) \geq k$ for all of eternity. Then, the only values of $a$ and the $N$ integers $x_1, x_2, \dots, x_N$ we must consider are $2 \mid a$ and $\nu_2(x_i) < \nu_2(a)$ for all $x_i$. In this case, Alice can never increase the $2$-adic valuation of any $x_i$ because $\nu_2(x_i + a) = \min(\nu_2(x_i), \nu_2(a)) = \nu_2(x_i)$. However, on every move Bob decreases the $2$-adic valuation of an arbitrary number by $1$, and after some number of turns it is guaranteed for there to be no even integers on the board, making Bob win. Therefore, the game is guaranteed to end regardless of Alice or Bob's moves.

Suppose $N \geq 2$; otherwise Alice and Bob have no choice in their moves and the statement holds trivially. Say Bob wins the game if the game ends in finitely many turns, and say Alice wins otherwise. The main idea is the following claim: Claim: Bob can force a win if and only if $\nu_2(n) < \nu_2(a)$ for all initial positive integers $n$. Proof. Suppose $\nu_2(n) < \nu_2(a)$ holds for all $n$ on the board. Then for any $n$ on the board at any point during the game, $\nu_2(n + a) = \min(\nu_2(n), \nu_2(a)) = \nu_2(n)$, so the $\nu_2$-values are unchanged by Alice's moves. However, $\nu_2\left(\prod_n n\right)$ decreases by $1$ after Bob's every turn (no matter what Bob's move is), so since this is originally finite, at some point $\nu_2\left(\prod_n n\right)$ is $0$. On the other hand, suppose $\nu_2(n) \geq \nu_2(a)$ for some original $n$ on the board. Alice can force a win in this case by replacing $n$ with $n + a$ whenever $\nu_2(n) = \nu_2(a)$ (yielding $\nu_2(n + a) > \nu_2(a)$), and adding $a$ to some other integer otherwise. Thus she can always keep $\nu_2(n)$ above $\nu_2(a)$, and so the game never ends. $\square$ This essentially finishes, since the condition on Bob forcing a win translates to $\nu_2(n) < \nu_2(a)$ for all integers $n$ on the board, and by the above logic the game is guaranteed to end regardless of Bob's moves. $\square$

Let $x_1,x_2, \dots , x_N$ be the $N$ integers written on the black board. We claim that if $\nu_2(x_i)<\nu_2(a) \forall i \in \{1,2, \dots , N \}$ then the game will end regardless of Alice's or Bob's moves. Let $\nu_2(x_i)=m$ and $\nu_2(a)=n$ First assume $\nu_2(x_i)<\nu_2(a)$ then we know that: $\nu_2(x_i+a)=\text{min} (\nu_2(x_i),\nu_2(a))=v_2(x_i)=m (\because\nu_2(x_i) \neq \nu_2(a) ) \implies \nu_2(x_i+a)=m \forall i \in \{1,2, \dots , N \}$ After Bob's move the number $x_i+a$ transforms into $\frac{x_i+a}{2}$ So $\nu_2(\frac{x_i+a}{2})=\nu_2(x_i+a)-\nu_2(2)=\nu_2(x_i+a)-1=m-1 \implies \nu_2(\frac{x_i+a}{2})=m-1$ So we decreased the power of $2$ by one so from $m \rightarrow m-1$, we will continue this until we reach 0. Hence the game will end regardless of Alice's or Bob's moves. Now if $ \nu_2(x_i) \geq \nu_2(a) \iff m \geq n$ Then after Alice will continue adding some $a$-s on some integer $x_t$ until we get $\nu_2(x_t)=\nu_2(a)$ for some $t \in \mathbb{Z^+}$ So $\nu_2(x_t)=\nu_2(a)=n \implies x_t=2^n \cdot k \wedge a=2^n \cdot l , k,l \in \mathbb{Z^+}$ and $k \equiv l \equiv 1 (\mod 2)$ So $\nu_2(x_t+a)=\nu_2(2^n \cdot k + 2^n \cdot l)=\nu_2(2^n(k+l))=\nu_2(2^n)+\nu_2(k+l)=n+\nu_2(k+l) \geq n+1$ Hence we increased the power of $2$ by at least one from $z \rightarrow \leq z+1$ so the game will never end.

Assuming that some positive integers implies we have more than one integer on the board. Let $N$ be the set of integers on the board initially. Then there are two cases, $\max_{n \in N} \nu_2(n)<\nu_2(a)$ or there exists some $n \in N$ such that $\nu_2(n) \geq \nu_2(a)$. If $\max_{n \in N} \nu_2(n)<\nu_2(a)$, then note that for any $n$, the operation $n+a$ will have $\nu_2(n+a)=\nu_2(n)$. Thus the $\nu_2$ of integers remain invariant under Alice operations, and since Bob operations decrease the $\nu_2$ by $1$ it is clear that this is a situation that Bob can force the game to end. It is also clear that it doesn't matter what moves Alice or Bob plays. If there exists some $n$ such that $\nu_2(n) \geq \nu_2(a)$, then Alice has a way to stop Bob from winning as follows. Whenever $\nu_2(n)=\nu_2(a)$, she will operate on $n$ by replacing it with $n+a$, since $\nu_2(n+a) \geq \nu_2(n)+1$ she will always be increasing the $\nu_2$ of that number. Otherwise, she can keep operating on any other number in any way she likes. For Bob to end the game, he must eventually decrease the $\nu_2$ of $n$ to $0$, however since he is decreasing it by one each time there will always be a turn where $\nu_2(n)=\nu_2(a)$ after Bob's operation in which case Alice can raise the $\nu_2$ back up, so Bob cannot force the game to end.

We will only consider $N\geq 2$ because the condition is trivial for $N=1$. If $a$ is odd, then for any odd number on the board, Alice can make it even. If all numbers are currently even, then just pick any and add $a$. If the number remains even after Bob divides it by $2$, then Alice can keep changing other numbers, until that one number Alice originally chose is odd, after which she makes it even again by adding $a$. Thus, Bob is not able to force the game to end for odd $a$. Now for even $a$, we claim that if $\nu_2(a)>\max\{\nu_2(n_1), \nu_2(n_2), \ldots, \nu_2(n_N)\}$ where $n_1,n_2,\ldots, n_N$ are the $N$ integers, then Bob is always able to force the game to end. Otherwise, he is not. To see this, we see that $\nu_2(n+a)=\nu_2(n)$, since $\nu_2(a)>\nu_2(n)$. However, $\nu_2(\frac{n}{2})=\nu_2(n)-1$. So, letting $V=\sum\limits_{i=1}^n \nu_2(n_i)$, we see that $V$ stays the same no matter what Alice does, and $V$ always decreases no matter what Bob does. Thus, $V$ must reach $0$ eventually, regardless of what Alice and Bob do. Now, if $\nu_2(a)\leq\max\{\nu_2(n_1), \nu_2(n_2), \ldots, \nu_2(n_N)\}$ then pick an $n_i$ such that $\nu_2(a)\leq \nu_2(n_i)$. Then, for the game to end, Bob will eventually have to decrease $\nu_2(n_i)$. If at any point $\nu_2(a)=\nu_2(n_i)$, then $\nu_2(a+n_i)>\nu_2(n_i)$, meaning Alice can always perform moves to avoid $\nu_2(n_i)$ reaching $0$. Thus, Bob cannot force the game to end.