my first-look guess is that B wins iff $n=2^k,k$ odd.

well he does, but the answer is much more than that!

If $N$ is odd $A$ wins. He first writes $1$, an odd number. If he writes an odd number $n$, both $n+1, 2n$ are even, so the number he gets is even and thus can make the +1 move, writing another odd number. Thus $B$ only writes even numbers and never $N$. Let $N=d_1d_2...d_k$ in binary, and suppose $N$ is even. Let $a_i=d_1d_2...d_{k-i+1}+1$. Partition the set ${1, 2, ..., N}$ into $S_1={N, N-1, ..., a_2}, S_2={a_2-1, ..., a_3}$, and so on. A move $n \rightarrow 2n$ always goes to the following subset. Now it is clear that if a player is the first to write a number in $S_1$, doing it by doubling the previous number, he wins (because he writes the even numbers from then on). If $X$ is the first to write a number in $S_2$, $Y$ will then jump to $S_1$ by a $n \rightarrow 2n$ move and win. So the first to write a number in $S_2$ loses. We have $S_2={d_1....d_{k-1}, ..., d_1...d_{k-2}+1}$. Clearly $d_1...d_{k-2}$ will be written, unless a player commits suicide, because the only way to skip it is to play a $n \rightarrow 2n$ move and that is losing. So for even $N$ the player who writes $d_1...d_{k-2}$ wins. Then the winner for the $d_1...d_k$ game is $A$ if $d_k=1$, and it is the same as for the $d_1...d_{k-2}$ game if $d_k=0$. If among $d_k, d_{k-2}, d_{k-4}$ and so on there's a $1$, the winner is $A$. If not, and if $k$ is even, the winner is the same as for $d_1d_2$, which is $A$ if $d_2=1$, and $B$ if $d_2=0$, by inspection. If $k$ is odd, the winner is either $A$ or the same as for $d_1d_2d_3$, which is always $A$ by inspection. We conclude that $B$ wins iff $N$ is the sum of distinct odd powers of 2.

Yes! Easy problem, right?

The solution set is equal to the set of all base 4 numbers consisting of only 2's and 0's Proof: If N is odd, A wins It is easy to see that he who can always write k, or forces his opponent to be the first to write a number >k writes 4k and 4k+2(if N is one of these). Let this mean that this person controls k. (statement 1) As per question, A controls 4,6 Also A controls all odd numbers B controls 2 statement 1 implies that he who controls k also controls 4k and 4k+2 so B controls numbers 2,8,10,32........ we will attempt to construct the set of all numbers controlled by B The first element is 2 Working in base 4: if abc..n(the number in base 4) belongs to the set , so does (abc..n0) and (abc..n2) so the set can be infinitely extended by adding 2 or 0 to the right also A controls all numbers not in this set: from 3..7 A gets 12 to 30 from this he gets all numbers uptil 122 execpt those in B's winning set. because B does not control k ,so A controls k(as he can force B not to write k) so A also controls 4k and 4k+2 (statement 1) this completes the solution(ans at top of post) PS:this answer is obviously same as Severius' solution which can be seen simply by converting base 4 numbers to sum form i think u will agree that this answer is simpler to derive and explain Rahul Singh

Let $g(N)$ denote the player, who wins the game for the number $N$. It is easy to see that $g(2k+1)=A$, as player A can win by executing only $n+1$-moves. Then B can only write even numbers and can therefore never write $N$. Lemma. $g(N)=g\left(\left[\frac{N}{4}\right]\right)$ for $N$ even, where $[x]$ denotes the largest integer not greater than $x$. Player $g\left(\left[\frac{N}{4}\right]\right)$ wins the game for $N$ in the following way: As long as his opponent does not write a number greater than $\left[\frac{N}{4}\right]$, he plays according to his strategy for $\left[\frac{N}{4}\right]$, so the first player having to write a number $n$ greater than $\left[\frac{N}{4}\right]$ must be his opponent. Then $\frac{N}{4}<n\le \frac{N}{2}$. Then he writes $2n$ with $\frac{N}{2}<2n\le N$. From now on, only $n+1$-moves are allowed, and as $N$ is even, Player $g\left(\left[\frac{N}{4}\right]\right)$ wins. Given a number $N$, we can now repeatedly apply our lemma. Eventually we will either get $g(N)=g(2k+1)=A$ or $g(N)=g(2)=B$. Now let $N=\sum_{i=0}^n a_i \cdot 2^i$ with $a_i\in\{0,1\}$. Let $j$ be the smallest index such that $a_{2j}=1$. After applying our lemma $j$ times, we will get $g(N)=g\left(\sum_{i=2j}^n a_i\cdot 2^{i-2j}\right)=g(2k+1)=A$. If on the other hand $a_{2j}=0\quad\forall j$ and $N=\sum_{i=0}^n a_i \cdot 2^{2i+1}$ we get $g(N)=g(2)=B$ after applying our lemma $n$ times. Hence, B wins the game iff $N$ can be written as the sum of distinct odd powers of 2, i.e. $N=\sum_{i=0}^n a_i \cdot 2^{2i+1}$.$\square$

In collaboration with mathdebam.

I had a rather interesting incident today with this problem; hence I feel obliged to post my solution (which is essentially the same as that already in the thread) and narrate the incident IMO ShortList 2004 C5 wrote: $A$ and $B$ play a game, given an integer $N$, $A$ writes down $1$ first, then every player sees the last number written and if it is $n$ then in his turn he writes $n+1$ or $2n$, but his number cannot be bigger than $N$. The player who writes $N$ wins. For which values of $N$ does $B$ win? Proposed by A. Slinko & S. Marshall, New Zealand Answer: $B$ wins if and only if $N$ is a sum of several odd powers of $2$. Firstly, note that for all odd $N$, $A$ can ensure a win just by adding $1$ all the time since his current number always stays odd whilst $B$'s stays even. Claim: For even $N$, a player has a winning strategy if and only if they have one for $n=\left \lfloor \frac{N}{4} \right \rfloor$. (Proof) The key idea is that the player who lands up on an even number $k$ with $2k>N$ wins the game, since thereafter all moves made are simply addition by one. Suppose the other player has a winning strategy for $n$, then they reach $n$ unless the protagonist reaches an even number in $(n, 2n)$; in which case they double the current number to win. Otherwise, regardless of what the protagonist does they simply double at the next turn and win thereafter by the initial observation. $\blacksquare$ From the previous analysis, and the fact that $B$ wins for $N=2$ we see that she wins only for the prescribed set of values of $N$. $\blacksquare$

ANSWER: $B$ wins if and only if $N$ can be expressed as the sum of distinct odd powers of $2$. SOLUTION: Call a natural number $N$ good if $B$ wins, and bad otherwise. Call this trait of a number to be good or bad as its character. We make a series of claims before the final result. Claim 1 If $N$ is an odd integer, then it is bad. PROOF: Suppose that at some point of time during the game, when $N$ is an odd integer, $B$ writes down the integer $n$. Then we claim that $A$ can win by writing $n+1$ at all such times. To see that this is true, just notice that, whenever $A$ writes an odd integer, $B$ writes an even integer on the board in the next move. But, as $A$ starts from an odd integer only, we get that $B$ must always write an even integer, and so $B$ can never terminate on an odd integer. Thus, we get that all odd integers are bad. $\Box$ Claim 2 $N$ and $4^kN$ have the same character $\forall k \in \mathbb{N}$. PROOF: We proceed by induction. Suppose that $N$ is bad. We'll show that $4N$ is also bad, i.e. $A$ can always reach $4N$. To show this, we'll play God in the game . Initially, we'll make $A$ play with the same strategy that he/she would have used to reach $N$, till $B$ doesn't write a number greater than $N$. But, as soon as $B$ writes a number of the form $N+C$, where $1 \leq C \leq N-2$, $A$ will write the number $2(N+C)$ on the board in his next move. As $2(2N+2C)>4N$, $B$ will be forced to write the number $(2N+2C+1)$, then $A$ will be forced to write the number $(2N+2C+2)$, and so on. This shows that $A$ will be the one to reach $4N=2N+2N$, and so $4N$ is bad. By a similar argument, one can show that if $N$ is good, then so is $4N$. Let's turn towards the inductive hypothesis, i.e. we suppose that our claim is true for some $k \in \mathbb{N}$. Then by the above argument, we get that $4^{k+1}N$ has the same character as $4^kN$, which in turn has the same character as $N$ (by the inductive hypothesis). Thus, we are done with the induction, and so our claim is proved. $\Box$ Claim 3 $N$ and $4N+2$ have the same character. PROOF: This easily follows by a similar argument as done while proving the base case in Claim 2. $\Box$ CONCLUSION: Note that $N=2$ is good. By Claim 2, we get that $N=2 \cdot 4^k=2^{2k+1}$ is also good, where $k \in \mathbb{N}$, i.e. all odd powers of $2$ are good. But, by Claim 3, this gives that $2^{2k+1}+2$ is also good. Again, By Claim 2, $2^{2k+2l+1}+2^{2l+1}$ is also good, where $l \in \mathbb{N}$. Continuing in a similar fashion, we get that the sum of distinct odd powers of $2$ is good. All we need to show now is that no other value of $N$ works. To see this, assume to the contrary (duh!) that some other value of $N$ is also good. Name this value as $M$. By Claim 1, $M$ must be even, i.e. $M=4m_1$ or $M=4m_1+2$. But then, by Claim 2 and Claim 3, we get that $m_1$ is also good. Again, we must have $m_1=4m_2$ or $m_1=4m_2+2$, and once again, $m_2$ must also be good. As $M$ can not be expressed as the sum of distinct odd powers of $2$, it's easy to see that $m_1$ also can not be expressed as the sum of distinct odd powers of $2$. Continuing in a similar fashion, we get a decreasing sequence of even positive integers, which can never reach an odd power of $2$, and more importantly which can never reach $2$. But, by the method of infinite descent, we know that this is never possible for finite $M$. Thus, no such $M$ exists. $\blacksquare$ EDIT: $333^{rd}$ post on AOPS, and that too a combi. I call that an achievement

I claim that $B$ will win iff $N$ is the sum of distinct odd powers of 2. First, note that if $N$ is odd, $A$ can always force $B$ to pick an even number. Hence, $A$ has the winning strategy. Next, if $N=4k+2$, the first person to pick a number, $i$, between $k+1$ and $2k+1$ will lose, since the next person can choose $2i$. No further doubling can occur, since the number is larger than $N/2$, so every move afterward will be a +1, resulting in the person who picked $i$ to lose. If the previous person, say $A$, picked $i<k+1$, then the largest number $B$ can write is $2i<2k+1$. So, as there is no way to "skip" this interval, the optimal strategy will be to reach $k$. Hence, the person who has a winning strategy for $k$ also has a winning strategy for $4k+2$. The same logic can be applied to show that if a person has a winning strategy for $k$ iff he has a winning strategy for $4k$. Now, we use strong induction on $N$ to show that $B$ will only win in the claimed case. Of course, this is true for $N\le 2$. Now, suppose the claim is proven for all numbers smaller than $N$. If $N\equiv 1\pmod 2$, we have already stipulated that $A$ will win. This follows our claim, since $1$ is an even power of 2. If $N\equiv 0\pmod 4$, $B$ will win iff $B$ wins $N/4$. Multiplying by $4$ increases all the exponents by $2$, so their parities and distinctness are preserved, as desired. Finally, if $N\equiv 2\pmod 4$, $B$ wins iff $B$ wins $(N-2)/4=k$. Similar to before, $4k+2$ is a sum of odd powers of 2 iff $k$ was. Hence, our induction is complete.

Solution from Twitch Solves ISL: Call this game the $N$-game (as we will induct on $N$). The answer is that Bob wins the $N$-game are exactly those that, when expressed in binary, have no $1$'s in the $2^0$, $2^2$, $2^4$, \dots positions. Setup. Define the $N$-table as follows. It has $N$ entries indexed by $\{1, \dots, N\}$. The $n$th entry is losing if and only if a player who sees this number on their turn wins; otherwise, it is winning. Hence by definition the last entry is always $L$ (because a player who is faced with $N$ has just lost!). Equivalently, here is a recursive description. We say $N$ is losing. Then, a given $n$ is winning if either $n+1$ or $2n$ is losing (ignoring $2n$ if $n > N/2$); else, it is winning. Bob wins the $N$-game if and only if $1$ is $W$. The tables are shown below for $N=12$, respectively. \[ \begin{array}{cccccccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ L & W & L & W & W & W & W & L & W & L & W & L \\ \hline 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ L & W & L & W & L & W & L & W & L & W & L & W & L \\ \hline 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ L & W & L & W & W & W & W & L & W & L & W & L & W & L \end{array} \]Proof. We start with the following claim. Claim: If $N$ is odd, then Alice wins the $N$-game. Proof. Alice can force Bob to stay on odd numbers. $\blacksquare$ We now address the case where $N$ is even. Claim: Suppose $N \equiv 2 \pmod 4$ and $N > 2$. Then Bob wins the $N$-game if and only if he wins the $(N-2)$-game. Proof. In the $N$-table, we have $N$ is losing, $N-1$ is winning, $N-2$ is losing, and so on; until $N/2+1$ is losing. Thus $N/2$ is winning. Now note that we may delete $N$ and $N-1$ (the last two columns) from the table without affecting any other entries; indeed $N/2$ was winning anyways as $N/2+1$ is losing. Thus the $N$-table is the $(N-2)$-table with two extra columns at the end. $\blacksquare$ Claim: Suppose $N \equiv 0 \pmod 4$ and $N > 4$. Then Bob wins the $N$-game if and only if he wins the $N/4$-game. Proof. In the $N$-table, we have $N$ is losing, $N-1$ is winning, $N-2$ is losing, and so on; until $N/2+1$ is winning. Now from this it follows $N/2$, $N/2-1$, \dots, $N/4+1$ are all winning. Since this entire range of numbers is winning and thus don't affect any later numbers, we wind up finding the first $N/4$ numbers are just a copy of the $(N/4)$-table. $\blacksquare$ These three claims imply the answer directly by induction.

Long and repetitive, but the idea is simple. For positive integers $N_1,N_2,$ write $N_1\sim N_2$ if the player with a winning strategy when $N=N_1$ also has a winning strategy when $N=N_2.$ Say a number $n$ is $\emph{sharp}$ if $2n>N.$ Note that if a player plays a sharp number, then all later turns must increase the number by exactly one. As a result, if a player writes a sharp number with the same parity as $N,$ then they win, and if a player writes a sharp number with opposite parity as $N,$ then they lose. $\textbf{Claim: }$ If $N\equiv 0\pmod{4},$ then $N\sim\frac{N}{4}.$ $\emph{Proof: }$ Suppose a player writes $\frac{N}{4}$ on turn $t.$ \begin{itemize}\item If $\frac{N}{4}+1$ is written on turn $t+1,$ then the player can write $\frac{N}{2}+2$ on turn $t+2$\item If $\frac{N}{2}$ is written on turn $t+1,$ then the player can write $N$ on turn $t+2$\end{itemize} In either case, the player who writes $\frac{N}{4}$ wins, so it suffices to show there must always be such a player. Assume no player writes $\frac{N}{4}.$ Then, some player must have written some even number in the interval $[\frac{N}{4}+1,\frac{N}{2}-2].$ But then the next player can double to reach a sharp even number and thus win, contradiction. $\blacksquare$ $\textbf{Claim: }$ If $N\equiv 1\pmod{4},$ then $N\sim\frac{N+1}{2}.$ $\emph{Proof: }$ Since $\frac{N+1}{2}$ is a sharp odd number, it suffices to show that $\frac{N+1}{2}$ will always be written. Suppose no player writes $\frac{N+1}{2}.$ Then, some player must write an even number in the interval $[\frac{N+3}{2},N-1].$ But each number in this interval is sharp, so the player will lose, contradiction. $\blacksquare$ $\textbf{Claim: }$ If $N\equiv 3\pmod{4},$ then $N\sim\frac{N-1}{2}$ $\emph{Proof: }$ If a player writes $\frac{N-1}{2},$ then the other player must write a sharp even number on the next turn, so they will lose. Hence, it suffices to show that $\frac{N-1}{2}$ will always be written. Assume no player writes $\frac{N-1}{2}.$ Then, some player must write an even number in the interval $[\frac{N+1}{2},N-3].$ But every number in this interval is sharp, so the player will lose, contradiction. $\blacksquare$ $\textbf{Claim: }$ If $N\equiv 2\pmod{4},$ then $N\sim\frac{N-2}{4}$ $\emph{Proof: }$ Suppose a player writes $\frac{N-2}{4}$ on turn $t.$ \begin{itemize}\item If $\frac{N+2}{4}$ is written on turn $t+1,$ then the player can write $\frac{N+2}{2}$ on turn $t+2$\item If $\frac{N-2}{2}$ is written on turn $t+1,$ then the player can write $N-2$ on turn $t+2$\end{itemize} In either case, the player can write a sharp even number and thus win, so it suffices to show there must always be such a player. Assume no player writes $\frac{N-2}{4}.$ Then, some player must write an even number in the interval $[\frac{N+2}{4},\frac{N-2}{2}].$ But then, the next player can double to reach a sharp even number and hence win, contradiction. $\blacksquare$ These claims are enough to imply that the answer is all $N$ with no ones in even positions when expressed in binary.

Nice Problem! Solution. Define two sets, good and bad respectively as $$G := \left\{\left\lceil \frac{N-1}{2} \right\rceil +1, \ldots, N \right\}~\text{and}~V:=\left\{\left\lceil \frac{\left\lceil \frac{N-1}{2} \right\rceil}{2} \right\rceil, \ldots, \left\lceil \frac{N-1}{2} \right\rceil \right\}$$We will abbreviate them as $G$ and $V$ respectively as shown above. Interpret the chosen numbers lying on the number line extended till $N$. Note that the biggest element of $V$ is consecutive to that of least element of $G$. It's worth noticing that one player must pick a number from $V,$ in particular both players cannot "skip" $V$. Now we have the following claim. Claim. If $N$ is even and if any player $P \in \{A,B\}$ lands up in $V$ before other player does does, then $P$ will lose eventually. Proof. Note that if $A$ lands up in $V$ before $B$ does, then $B$ must make the next move. But observe that $2V \subset G$. So $B$ can either "jump" from $V \to G$ or stays in $V$. If $B$ jumps then it will land on some $2k \in G$ but since $N$ is even, and $2g > N$ for every $g \in G,$ therefore $A,B$ must make the $+1$ move, then the parity of numbers chosen by $A$ is always odd, which leads $B$ to win. Since both players plays optimally. If one player jumps to $V$ then other player jumps to $G$ and wins eventually, which is what we desired. $\square$ Consequently, neither $A$ nor $B$ would want to land up in $V$ before other player does $~(\clubsuit)$. If one does, then he will lose. This is at central of the rest of the solution. Call a number $N, P$ true if player $P$ could always win that number, where $P \in \{A,B\}$. Now since $A$ started with $1$ then $B$ must pick $2$. Now we deal with the cases when $N$ is odd or even seperately. If $N$ is odd, we present the follwing winning strategy for $A$. If at any time $A$ faces $2k$ chosen by $B$. Then simply pick $2k+1$. Now $B$ can either pick $2k+2$ or $2(2k+1)$ which are both even, we conclude that parity of the numbers chosen by $B$ remains the same as even since $B$ started with $2$. But since $N$ is odd, $B$ cannot pick $N$. We conclude $A$ wins the game. $\square$ If $N$ is even, we claim that if $x$ is $P$ true implies $4x+2$ is $P$ true. Let $N=4k+2$ then the good and bad sets are $$G=\{2k+2, \ldots, 4k+2\}~\text{and}~V=\{k+1, \ldots, 2k+1\}$$Consider the set $\mathcal{K}=\{1,\ldots, k\}$. By $(\clubsuit)$ we have, no player will jump from $\mathcal{K'}=\{\lceil \tfrac{k}{2}\rceil+1, \ldots, k\}$ to $V$. But this is same as if we are playing game on $\mathcal{K}$ set. Now if a player $P\in \{A,B\}$ manages to reach $k,$ which is same as saying $k$ is $P$ true, then the other player must pick number from set $V$ which will lead other player (not the $P$ player) to lose. Therefore, $4k+2$ is $P$ true as desired. $\square$ Similar setting yields $4x$ is $P$ true if $x$ is $P$ true. Also it's easy to verify that $1,3,4,5,6,7,9$ are $A$ true numbers and $2,8$ are $B$ true numbers. Define $$\mathcal{A}=\{x \mid x\in \mathcal{A} \implies 4x+2,4x \in \mathcal{A}, ~\text{given}~1,3,4,5,6,7,9 \in \mathcal{A} \}~\text{and}~\mathcal{B}=\{x \mid x \in \mathcal{B} \implies 4x+2,4x \in \mathcal{B},~\text{given}~2,8 \in \mathcal{B}\}$$We claim that $\mathcal{A}\cup\mathcal{B}\equiv 2\mathbb{Z}$ and $\mathcal{A} \cap \mathcal{B} \equiv \emptyset$. Assume at some moment, $\{1,2,\ldots, 4k\}$ are occupied by either $A$ or $B$. Then $k$ is $P$ true for some $P$ implying $4k+2$ is also $P$ true, and thus occupied. If at some moment $\{1,2,\ldots,4k+2\}$ is occupied, then $k+1$ is $P$ true, implying $4k+4$ is $P$ true for some player $P$. We conclude by induction that $\mathcal{A} \cup \mathcal{B} \equiv 2\mathbb{Z}$. Now assume if possible $4m+2=4n+2$ where $4m+2\in \mathcal{A}$ and $4n+2\in \mathcal{B},$ now this implies $m=n,$ and so on, implying that one of $a \in \{1,3,4,5,6,7,9\}$ is same as one of $b \in \{2,8\},$ which is a contradiction, we conclude that $\mathcal{A} \cap \mathcal{B}\equiv\emptyset$. Now $\mathcal{A},\mathcal{B}$ consists of numbers for which $A,B$ have a winning strategy. To characterize $\mathcal{B}$ we claim that $\mathcal{B}$ is nothing but the sum of distinct odd powers of $2$. We see that, working backwards from any such sum boils down to the given $\{2,8\}\subset \mathcal{B}$. Also combing terms with each other yields sum of distinct odd powers of $2$ as desired. This finishes the problem. $\blacksquare$

Let a number be weird if it can be written as the sum of distinct odd powers of 2. We claim that $B$ wins if and only if $N$ is weird. Claim 1:If $N\geq 4$ is even, and a player can guarantee getting $\lfloor \frac{N}{4} \rfloor$, then they can also guarantee getting $N$. Proof: Let's say $P_1$ gets $\lfloor \frac{N}{4} \rfloor$. If $P_2$ doubles, then $P_1$ doubles too and gets $4\cdot \lfloor \frac{N}{4} \rfloor$. At which point if this is not equal to $N$, $P_2,P_1$ will exchange a round of $+1$s and $P_1$ will win. If $P_2$ adds one, then $P_1$ doubles to $2\cdot \lfloor \frac{N}{4} \rfloor+2$. At this point, $2(2\cdot \lfloor\frac{N}{4}\rfloor+2)> N$. Thus, the only course of action is for both players to add one repeatedly, but since $P_1$ will always be the one writing down evens, $P_1$ wins. $\square$. Claim 2: If $N$ is odd, then $A$ wins Proof: If $A$ repeatedly does the add one operation, then $B$ will always receive an odd number which he will have to turn into an even which will never be equal to $N$.$\square$. To finish, note that all odd $N$ aren't weird and $A$ wins. If $N$ is weird, then $\lfloor \frac{N}{4}\rfloor$ is weird too, so $B$ wins $N$. If $N$ isn't weird, then $\lfloor\frac{N}{4}\rfloor$ isn't weird, so $A$ wins. The base cases are easy to show (Alice wins $1,3$ and $B$ wins $2$), and so we are done with this strong induction. $\blacksquare$.

There are a lot of this i want to tell while i solved this problem lol. So when i saw this problem, i really wanted to solve it, hence i remembered something that my teacher told about this kind of problems, i should play the game first. And here is when Rama1728 comes!, so i told him "wanna play a game?" ,and then he said "what game?" ,then i had to explain the rules of this thing lol and after a lot of talking i decided to start (Rama was player A and i was player B), we started with the number $N=69$ in which Rama won (later i realiced why this happens which is my first claim). Then we did the game with $N=32$ in which i lost becuase i'm dumb lol (now knowing how to always win at that number). Then when trying with $N=8$ i always won and then tried some other numbers. Later we realiced that if $N$ was odd then Rama would always win and no much time later they disconnected (rip). From here progress is mine and this is how i solved a C5 (a victory for me becuase i suck at combo lol) Claim 1: If $N$ is odd then $A$ wins always. Proof: The winning strategy for $A$ is just always writting an odd number which is posible as after $A$ puts $1$, $B$ nesesarily puts $2$ and here is when this strategy comes, so every time $A$ writtes an odd number $k$ then $B$ writes $k+1$ or $2k$ but both are even, and after doing that $A$ just needs to add $1$ to any of these options to write an odd number so $A$ will always win becuase $B$ will never write an odd number and $N$ is an odd number. Hence from here we will be working with $N$ even as we want $B$ to win. Claim 2: If $B$ can win for $\left \lfloor \frac{N}{4} \right \rfloor$ then he can win for $N$ Proof: Realice that $A$ is smart enough to realice that if he puts a number $k$ between the range $\left \lfloor \frac{N}{4} \right \rfloor < k \le \frac{N}{2}$ then $B$ wins becuase $B$ puts $2k$ and then clearly this becomes an adding $1$ game in which $B$ will always win becuase $N$ is even. So $A$ will do all the possible to let $B$ write such $k$, but remember that $B$ has an strategy to reach $\left \lfloor \frac{N}{4} \right \rfloor$ meaning that this thing is even. Now if $A$ puts a number less than $\frac{\left \lfloor \frac{N}{4} \right \rfloor}{2}$ then $B$ can multiply it by $2$ and then $A$ will try to use the adding $1$ game in which they will obviously fail as $B$ can always write even numbers. And if $A$ somehow writes a number greater than $\frac{\left \lfloor \frac{N}{4} \right \rfloor}{2}$ then $B$ does the adding $1$ game, which destroys $A$ strategy as if he multiplies by $2$ then its self-kill and if $A$ follows the adding $1$ game then $B$ always reaches $\left \lfloor \frac{N}{4} \right \rfloor$ becuase its even. Finishing the problem: So lets use Claim 1 and Claim 2. Very easy to verify that Claim 2 is the only way to win for $B$ when $N$ is even. Also note that if for a even number $N$ it holds that $\left \lfloor \frac{N}{4} \right \rfloor$ is even then $N=8a, 8a+2$ for some positive integer $a$. And now here is where the cycle begins..., basicaly we need to find more about $a$ which holds that $\left \lfloor \frac{a}{2} \right \rfloor$ is even. And now here is the funniest part. For any posititve integer $m$ that satisfies that $\left \lfloor \frac{m}{2} \right \rfloor$ is even then its very easy to see that $m=4m_1, 4m_1+1$ and since from $a$ and the future definitions of $a$ holds the same thing we have a cycle where $N$ ends by being expressed in this way: $$N=\sum_{j=0}^{k} a_j \cdot 2^{2j+1} \; \text{where} \; a_n \in [0,1] \; \text{for every non-negative integer} \; n$$And from this we got our answer to the problem. Answer: $B$ wins if $N$ is the sum of odd powers of $2$. Thus we are done

Claim: A wins for all odds. Proof: every turn, A can write down an odd by playing +1, where anything from B writes down an even. Claim: the player who wins n also wins 4n, 4n+2. Proof: assume WLOG it's A. Then, suppose that A reaches n; then, regardless if B writes down n+1 or 2n, A can win with x2. Now, if B plays some n<k<2n, then A can also won by writting down an even 2n+1<2k<4n. Now, combining the above 2 claims alongside the fact that B wins 2, it's obvious that B wins iff n's binary representation has 0's in every even position, counting from the right.

This took an embarrassingly long time. The answer is $\boxed{N = \text{the sum of distinct odd powers of }2}$. First, notice that Bob cannot win any odd $N$, since Alice can keep adding $1$ to Bob's answer and Bob must keep writing even numbers. The key claim is the following: Claim: Bob wins $N$ iff he wins $\left\lfloor\frac N4\right\rfloor$. Proof: If any player ever plays a number in the range $\left(\frac N2, N\right]$ with the same parity as $N$, they win, since the remaining moves must all be $+1$s, and the original player will play all of the remaining $N$-parity numbers until they reach $N$ ($\spadesuit$). Assume FTSOC Bob does not win $N$ but wins $\left\lfloor\frac N4\right\rfloor$, which must be even. Then Alice must play a number in $\left(\left\lfloor\frac N4\right\rfloor, \frac N2\right]$, and Bob can then double and win by $\spadesuit$, a contradiction. Now FTSOC assume Bob wins some even $N$ but Bob does not win $\left\lfloor\frac N4\right\rfloor$. Then Alice wins $\left\lfloor\frac N4\right\rfloor$. Bob must play a number in $\left(\left\lfloor\frac N4\right\rfloor, \frac N2\right]$, and then Alice may double and win by $\spadesuit$. This is a contradiction, and therefore the original assumption must be false, and the claim is proved. Obviously Bob wins $N = 2$, and through some trivial induction, we arrive at the answer and finish.

We claim that $B$ can win if and only if $N$ can be presented as a sum of distinct odd powers of $2$. Obviously, the only case when $B$ wins for $N<4$ is $N=2,$ so two following claims are sufficient. Claim 1. For every odd $N$ player $A$ can force a win. Proof. The strategy for $A$ is to increase last written number by $1$ on each move. Thus $B$ always writes an even number, and since the game is clearly finite, $A$ wins $\Box$ Claim 2. For even $N=n\geq 4$ player has a winning strategy iff he has it for $N=\left\lfloor \frac n4\right \rfloor .$ Proof. Note that the only if part follows from the if part by indirect argument. Assume the player $X$ has a winning strategy for $n=\left \lfloor \frac n4\right \rfloor ;$ thus in case $N=n$ this player can force his opponent to write the first-ever number from interval $\left( \left \lfloor \frac n4\right \rfloor ;\frac n2\right]$. After that let player double the number, and so he writes the even number from interval $\left( \frac n2;n\right]$. Henceforth both players must increase number by $1$ on each move, so by parity argument $X$ must win $\Box$

If $N$ is odd, then if $A$ only does $+1$ moves, then the parity must change after each of $A$'s and $B$'s moves, so $B$ always plays on an even number and thus cannot win. If $N$ is even, then let $N_1=\lfloor \tfrac{N}{2}\rfloor$, $N_2=\lfloor \tfrac{N}{4}\rfloor$, and $N_3=\lfloor \tfrac{N}{8}\rfloor$. If a player writes a number in $(N_2,N_1]$ then the opponent can double it for a value in $(N_1,N]$. Thus, from there the only available move is $+1$, so the one who writes a number with the same parity as $N$ wins. That player is the opponent, since they just doubled it. If a player reaches $N_2$, then the opponent has no choice but write a number in $(N_2,N_1]$ no matter what they do, so they win. If the number is in $(N_3,N_2]$ then doubling it will make them lose, so the only logical move is $+1$. Thus, the person who wins is the same as the person who wins $N_2$. Write $N$ in base $4$. $A$ wins if and only if some digit is odd.

First C5 ever, maybe this is a lot easier than a C5. We claim that Bob wins if and only if $N$ when written in the form $$a_02^0 + a_12^1 + a_22^2 + \dots$$for $a_i\in \{0,1\}$ does not have $a_i=0$ for all even indices $i$. First we exclude odd $N$. Notice that if Alice always adds 1 to the last written number, Bob can only write down even numbers (Alice starts with 1 and Bob 2). This means he cannot ever write $N$ which allows Alice to win. Now, we deal with even $N$, via induction. It is easy to see that Bob wins $N=2$ and Alice wins $N=4$ since Bob must play 2 on his first turn. $N=6$ too can be won by Alice by doing the following moves $$1 \longrightarrow 2 \longrightarrow 4 \longrightarrow 5 \longrightarrow$$(Here Bob has no choices at all). Now, say we know which $N$ Bob can win for $N \leq 2^{2k+1}$ for some $k \geq 1$. Let a number $a$ be called winning if a player who gets his turn with the last number $a$ written can win. Else, let it be called loosing (here the player is forced to lose). Now, let $N=4k$ for some $k\geq 2$. Then, clearly $4k-1$ is winning. This in turn means that $4k-2$ is losing (since it is too large to do the $2n$ move), likewise all odd are winning and all even losing upto $2k+1$, and then $2k$ becomes winning since that player can simply do the $2n$ move. Then, all numbers $2k-1,2k-2,\cdots,k+2$ are winning since that player simply can do the $2n$ move and force the next player to a losing position. Now, $k+1$ is also winning due to the same reason but $k$ is losing since both options $k+1$ and $2k$ are in fact winning. Then, note that $k-1$ is winning and so on. Here, $k-2,k-4 \cdots, \lfloor{\frac{k}{2}}\rfloor$ will be losing since even though it is possible to do the $2n$ move all the positions obtained through them are winning positions. So, since $k$ is also losing, it can be seen that from $k-1$ onwards to the right, the winning and losing positions are exactly the same as in the $N=k$ case. To summarize, \begin{tabular}{c|c c c c c c c c c c c} W& $4k-1$ & $4k-3$ & $\cdots$ & $2k+3$ & $2k+1$ & $2k$ &$\cdots$ & $k+2$ & $k+1$ & $k-1$ & $\cdots$ \\ \hline L & $4k-2$ & $4k-4$ & $\cdots$ & $2k+2$ & & & & $\cdots$ & $k$ & & $\cdots$ \end{tabular} Thus, if $k$ is winning it has to be a sum of odd powers of two (when written as a sum of distinct powers of 2) and thus so must be $N=4k$ (since multiplying by four adds 2 to each index which preserves their parity). Now, to deal with $N=4k+2$, here too we can map the above table keeping track of when it is possible to force the next player into a losing position to obtain, \begin{tabular}{c|c c c c c c c c c c c} W& $4k+1$ & $4k-1$ & $\cdots$ & $2k+3$ & $2k+1$ & $2k$ &$\cdots$ & $k+2$ & $k+1$ & $k-1$ & $\cdots$ \\ \hline L & $4k$ & $4k-2$ & $\cdots$ & $2k+2$ & & & & $\cdots$ & $k$ & & $\cdots$ \end{tabular} Thus, it is only possible for Bob to win $N=4k+2$ if he can win $N=k$. Bob can win $k$ only if it can be written as a sum of odd powers to 2 by our induction hypothesis, and thus he can win $N=4k+2$ only if it can be written as a sum of odd powers of 2 (multiplying by 4 does not change the parity of the index of larger powers and $+2$ adds a power of $2^1$ to the end which is also an odd power). And, the induction is complete. Thus, it is clear that by the Principle of Mathematical Induction, Bob can win if and only if $N$ can be written as a sum of odd powers of 2 (in the above mentioned form).

We claim that N=sum of distinct odd powers of 2 work. Obviously odd N A wins (A keeps on adding 1), and B wins 2. Then, suppose WLOG player A would normally win N; we claim that A would also win 4N and 4N+2. Indeed, note that if A wins by getting B to get to N/2, then A goes to N, and no matter if B doubles or adds 1, A doubles, and A will henceforth win both of those due to the condition. If A wins by getting B to get to k>N/2 with opposite parity than N, if B adds 1 keep adding 1 as A up to N (if A finishes at N, then the problem is evident again); eventually when B doubles to a number N<i<2N, A can double to 2N<j<4N being even, and since B can't do anything but add 1, A will finish at the same parity even. We're now ``home-free": Since B wins 2, our original claimed answer is evident. $\blacksquare$ Remark.Note that the claim is ``sharp", because worst case is when A only wins 4n and 4n+2, which is also when B doubles from N and A doubles, so you couldn't claim a 4n-2 win guarantee, which serves as a sanity check that this is probably the strongest answer we can get. also extremely misplaced for C5; I've seen the one about N coins, you can reduce by at most half of the coins, last person to take coins loses; this is similar, so ``A problem changes from challenging to trivial if a similar one was solved in training."

$B$ can win (assuming that they move after $A$ writes down $1$) if and only if, when $N$ is written in binary, all of its even-indexed digits (units digit, $4$'s digit, etc.) are $0$. First suppose that $N$ is odd. Then player $A$ always adds one to their number. It's easy to prove by induction that $B$ always writes down an even number, and $A$ always writes down an odd number, so $A$ clearly ends up winning. Now suppose that $N$ is even. Then any even number in $(N/2,N]$ is losing (i.e. the player that receives an even number in this range at the start of their turn loses), since both sides can only add $1$. Thus any number in $(N/4,N/2]$ is winning, since the player can just multiply by $2$ to give the other player an even number in $(N/2,N]$. I now claim that the game for $N$ is equivalent to the game for $\lfloor N/4 \rfloor$. Observe that in general we can restate the game as having no restrictions on the size of the number written, but having whatever player first writes a number more than $N$ lose. Then, the player who exceeds $\lfloor N/4\rfloor$ first (in a game for $N$) gives their opponent a number in $(N/4, N/2]$, which is winning for the opponent, so the two players will essentially play a game for $\lfloor N/4\rfloor$ that has the same outcome as the game for $N$. It is then straightforward to extract the advertised solution set from the fact that $N$ odd are losing and $N$ even are winning iff $\lfloor N/4\rfloor$ is. $\blacksquare$

We claim that $N$ wins iff $N$ can be written as the sum of distinct powers of $2$, all of which have odd exponent. Let $N$ be winning if $B$ wins for a given $N$. Notice that if someone places a number greater than $\frac N2$, they win iff the parity of that number is the same as the parity of $N$ as the moves after that placement must be $+1$. Claim: If $N=4k + 1$ or $N = 4k + 3$ for some positive integer $k$, then $N$ wins iff $2k + 1$ wins. Proof: Notice that if someone skips past $2k+1$ (as in they make the number go from under $2k + 1$ to over $2k + 1$), then they reach an even number greater than $\frac N2$, so they lose. Hence we can assume no player makes a move to skip past $2k+ 1$ as that would be their least optimal move. If someone hits $2k + 1$, then they win as the other person is forced to make the number even. Now, the game is played so that the number can't exceed $2k + 1$ and whoever hits $2k + 1$ wins, hence $N$ wins iff $2k + 1$ wins. $\square$ Now to see that all odds lose, we can induct this with base case $1, 3$ obvious. Notice that for each odd number $N$, (using the claim) that $N$ loses if something less than $N$ loses. But everything less than $N$ loses by the inductive hypothesis, so $N$ must also lose. Claim: If $N$ is even, then $N$ wins iff $ \left \lfloor \frac N4 \right \rfloor $ wins. Proof: Let $ \left \lfloor \frac N4 \right \rfloor=k$. Notice that if a player places some number, say $m$, in the interval $(k,2k]$, then notice that they lose as the other person can play $2m$, which is even and over $\frac N2$. Hence if someone skips past $k$, since they can't hit anything over $2k$, they lose. Therefore, we can assume no one skips past $k$, as it would be their less optimal move. If someone actually hits $k$, they win as the other person must place in $(k,2k]$. Hence the game is now played so that the number can't exceed $k$ and whoever hits $k$ wins, so $N$ wins iff $k$ wins. $\square$ Using the facts that $2$ wins but $1, 3, 4$ lose, the conditions ($N$ odds losing and $N$ even winning iff $ \left \lfloor \frac N4 \right \rfloor$ wins) uniquely determine which $N$ win. It suffices to prove that the conditions given by the claims hold with our claimed solution in the beginning. The condition of all odds losing clearly holds true. Now, we need to show that if $N \in \{4k, 4k + 2\}$ that $N$ wins iff $k$ wins. Let $k = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_t}$ for some $t$ and distinct positive integers $a_1, a_2, \ldots, a_t$. Note that $4k = 2^{a_1 + 2} + 2^{a_2 + 2} + \cdots + 2^{a_t + 2}$ and $4k + 2 = 2^{a_1 + 2} + 2^{a_2 + 2} + \cdots + 2^{a_t + 2} + 2^1$. Since $a_1, a_2, \ldots, a_t$ are all odd iff $a_1 + 2, a_2 + 2 , \ldots, a_t + 2$ and $a_1 + 2, a_2 + 2 , \ldots, a_t + 2,1$ are all odd, we get that $4k, 4k + 2$ win iff $k$ wins, as desired.

Solved with OronSH, ihatemath123, and mathJoo (all orz) The answer is all numbers that are the sum of distinct odd powers of two (or whose digits in base four are all even). Claim: $A$ wins for all odd numbers. Proof. Since $B$ writes $2$, $A$ can guarantee writing an odd number and $B$ can guarantee writing an even number. Thus $A$ always adds one, meaning $A$ can never write a number above $NN$ without $B$ writing one before. $\blacksquare$ Claim: If $A$ wins for $N=k$, then $A$ wins for $4k$ and $4k+2$. The similar claim holds for $B$. Proof. We prove for $A$ and symmetrically the result holds for $B$ since we don't use the fact of who goes first. If $A$ wins for $k$, then that means $A$ can guarantee $B$ making a number in $[k+1,2k].$ Then $A$ doubles it to get an even number between $2k+2$ and $4k$. For $N=4k$ and $4k+2$ $B$ can't double either one and thus we just add $1$ each time and $A$ wins by parity. $\blacksquare$ Now, given $N$, write it in binary. If $N$ is not a sum of odd powers of $2$, it must contain an even power of $2$ in it's binary representation. Thus we truncate the last $2$ digits if $N$ is even and get a number that has the same state as $N$. Eventually if $N$ is not of the desired form then we get to an odd number, thus losing. If $N$ is of the desired form, then we get to $N=2$ which is trivially winning.

Bob wins if and only if $N$ is the sum of distinct odd powers of 2. If $N$ is odd, then Alice just adds 1 at her round. Note that after Alice's turn, the number will be always odd, thus, after Bob's turn, the number will be always even, which means that Bob can never reach $N$. Call a positive integer $N$ good if Bob wins at it. Then I claim that $N$ is good $\iff$ $\left\lfloor\frac{N}{4}\right\rfloor$ is good and $N$ is even. Indeed, if $N$ is odd, then Alice can surely win. Thus, we may assume that $N$ is even. Now suppose that $\left\lfloor\frac{N}{4}\right\rfloor$ is good. Then Bob can reach it. Alice either writes $\left\lfloor\frac{N}{4}\right\rfloor + 1$ or $2\left\lfloor\frac{N}{4}\right\rfloor$, both of them is less or equal to $\frac{N}{2}$. Then Bob just multiply the number Alice wrote by 2. Therefore, Bob's written number is even and larger than $\frac{N}{2}$, and combined with the fact that $N$ is even, Bob can surely win. If Alice can reach the number $\left\lfloor\frac{N}{4}\right\rfloor$, then Alice just follows the same strategy as Bob's so that she can win. Thus, we may conclude that Bob wins if and only if $N$ is even and Bob wins at $\left\lfloor\frac{N}{4}\right\rfloor$. Since Bob wins at $N = 2$, so induction gives that Bob wins if and only if $N$ is the sum of distinct odd powers of 2. $\blacksquare$

$ $