I claim $B$ wins only if $n$ is squarefree and odd. Case 1: There exists a prime $p$ such that $p^2\mid n$. $A$ takes $\frac np$. From now on, both players can only take non-multiples of $p$. Since $p\mid \frac np$, there are $\frac np (p-1)$ unchosen non-multiples of $p$. Note $p(p-1) \mid \frac np (p-1)$ is even. $B$ and $A$ will take turns picking the non-multiples of $p$, and when they run out it is $B$ to move, so $B$ loses. Case 2: $\nu_2(n)=1$. $A$ takes $\frac n2$. From now on, both players can only take non-multiples of $2$. Since $2\nmid \frac n2$, there are $\frac n2 - 1$ unchosen non-multiples of $p$. Note $\frac n2-1$ is even, so after $B$ and $A$ take turns picking the non-multiples of $p$, it is $B$ to move, so $B$ loses. Case 3: $n$ is odd and squarefree. Say A takes $k$ and let $d=\gcd(n,k)$. B takes $\frac{n}{dp}$ for a fixed prime $p\mid \frac nd$. From now on, both players can only take non-multiples of $p$. Since $n$ is squarefree, there are $\frac np (p-1)$ unchosen non-multiples of $p$. Note this is an even number, so after $B$ and $A$ take turns picking the non-multiples of $p$, it is $A$ to move, so $B$ wins.

More like an essay rather than a solution

https://drive.google.com/file/d/1YPKtfIoOjeiQ6gv89yVuplSqw8Seh6HT/view?usp=sharing

I claim that Bobasaur wins iff $n$ is a squarefree odd. Aliceurill's winning strategy for any $n$ and prime $p$ with $p^2|n$ is as follows: choose $\frac{n}{p}$ on the first turn. Then, Aliceurill and Bobasaur will always be able to choose anything that isn't a multiple of $p$ throughout the remainder of the game. $\frac{p-1}{p}n$ is even since $p-1$ is even if $p$ is odd, and $n$ is a multiple of $4$ if $p=2$. Aliceurill's winning strategy for any squarefree even $n$ is as follows: choose $\frac{n}{2}$ on the first turn. Then, Aliceurill and Bobasaur can only choose the odds in the remainder of the game. There are $\frac{n}{2}-1$ odds that haven't been chosen, which is odd. Now, to win every other $n$, Bobasaur can choose $n-i$ whenever Alicesaur chooses $1\le i<n$. This wins since, for any prime $p|n$, if Bobasaur chooses a multiple of $p$ at some point, Alicesaur's choice must have also been a multiple of $p$ right before.

Will LateX smtime later P1

The answer is all odd squarefree numbers. Replace Aliceurill and Bobasaur (although nice names) with $A$ and $B$. If $n = 4k+2$, then $A$ chooses $2k+1$, so whoever chooses an even number next loses, and since the odd numbers left are $1,3,\cdots,4k+1$ excluding $2k+1$, there are an even number of these, so $A$ can ensure he picks the last odd and so win, If $n = 4k$, then $A$ chooses $2k$ so again whoever chooses evens loses and since there are $1,3,5,\cdots,4k-1$ an even number of odds, once again $A$ wins. So assume now that $n$ is odd If $n = p^2m$ for some prime $p$, then $A$ chooses $pm$ so whoever chooses a number divisible by $p$ loses. The numbers divisible by $p$ are $p,2p,\cdots,p^2m$, an odd number of these and so the ones not divisible by $p$ must be $p^2m - pm$, which is even so again $A$ wins. If $n$ is squarefree, say equal to $p_1 p_2 \cdots p_k$ and label such that $A$ chooses $p_1 p_2 \cdots p_i$ (with $i$ possibly equal to $0$). Then $A$ chooses $p_{i+1}p_{i+2} \cdots p_{k-1}$ so choosing a number divisible by $p_k$ will lose. But there are an odd number of things divisible by $p_k$ and among the ones that are not, an even number (2) have been chosen so far, leaving an even number of such numbers remaining and so $B$ can ensure he picks the last number not divisible by $p_k$ and hence win.

Bobasaur has a winning strategy if and only if $n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_k^{\alpha_k}$, where $p_1,\,\dots ,\,p_k$ are odd prime numbers and $\alpha_i \in \{0,1\}$ for all $1\leq i\leq k$. To prove this, let's first show that Aliceurill can always guarantee victory if $n$ is not of this form. If $n$ is even, then Aliceurill can first circle the number $n\over 2$ and thus Bobasaur will not be allowed to circle another even number, otherwise he will lose. This implies he will only be able to circle one of the odd integers remaining, which are certainly an even number of integers, as it is easy to see. Consequently, Aliceurill will then circle another one of these odd integers; the same type of move will be repeated by the two players until Aliceurill circles the last odd number and Bobasaur is hence forced to choose an even number, giving victory to Aliceurill. Now, if $n$ is not even but at least one prime in its factorisation has an exponent $\geq 2$, i.e. $n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_k^{\alpha_k}$, with $\alpha_1 \geq 2$, then Aliceurill can first circle the number $n \over p_1$; this way Bobasaur will only be able to choose an integer from a set of $n-\frac{n}{p_1}$ elements (non-losing numbers), which is an even number of elements. So, for the same reason as above, Aliceurill will win. Let's now prove that if $n$ is of the form we indicated at the beginning, Bobasaur can win. The case $n=1$ is trivial. The case $n=p$, where $p$ is an odd prime, is trivial as well. The case $n=p_1 \cdot p_2 \cdots p_k$ (with $p_i\neq 2\,\,\forall\,i$) can be proven in the following way. If, like before, Aliceurill circles a divisor $d$ of $n$, Bobasaur, in order not to lose, will then be able to choose among $n-1-d$ uncircled integers, which is an odd number of integers; at this point he will have a winning strategy consisting in circling none of the losing numbers, so that at the end Aliceurill won't have choice but circling a losing number, again for parity reasons. If, instead, Aliceurill first circles a number not dividing $n$, then Bobasaur will win by applying Aliceurill's strategy we described in the first part consisting in choosing a divisor of $n$ and leaving her an even number of non-losing choices. This concludes the proof.

Here is a very long looking solution. So we will divide it 4 parts: Part I: Very Small Observations Part II: Answer and verification. Part III: Showing no even $n$ works. Part IV: Showing no odd number $n$ with $\nu_q(n)>1$ works where $q$ is an odd prime dividing $n$. Part I: Very Small Observations The player can play a maximum of $\displaystyle \left\lceil{\frac{n}{2}}\right \rceil$ moves and the game can last for maximum of $n$ moves including the move of loss. If we say that Aliceurill has the 1st move, then Aliceurill will always have an odd number of move and Bobasaur will have an even number of move. Part II: Answer and Verification Bobasaur can win the game if and only if the $n$ is an odd number of the form $q_1q_2\ldots q_k$ where $q_i$ is a prime dividing $n$ and $q_i < q_j$ for $i<j$. This could rephrased as $\nu_{q_i}(n) =1$ for any $i \in [1,k], \mathbb{Z}^+$. Call a number "good" if it doesn't make the player lose on their own move. It is time to show that this works. First of all note that $\varphi(n)$ is even. We will split cases on the basis of first choice of number chose by Aliceurill. Case 1: Aliceurill choses $\alpha \in [1,n]$ such that $\gcd(\alpha,n)=1$ at his first turn. The strategy for Bobasaur will be to choose $\prod_{i=1}^{k-1}q_i$ at second turn of the game. Now there are even number of cards relatively prime to prime to $p_k$ after 2nd move. Anyone who encircles a multiple of $p_k$ will immediately lose the game. If there are a total of $2k$ numbers relatively prime to $p_k$. At $(2k)$th move of the game, Bobasaur will chose the last number relatively prime to $p_k$ and then Aliceurill will lose by force. Case 2: Aliceurill choses $\alpha \in [1,n]$ such that $\gcd(\alpha,n)\ne 1$ at his first turn. For Bobasaur in order to win must chose the number $X$ at his second move such that \[X = \frac{n}{\gcd(\alpha,n)\cdot p}\]where $p \mid n$ but $p \nmid \gcd(a,n)$ and $p$ is also a prime. From here on, whoever choses a multiple of $p$ loses immediately. One can essentially copy the proof from the first case now. Part III: Showing no even $n$ works. The winning strategy for Aliceurill is to choose $n/2$ at his first turn. This would force Bobasaur as well as Aliceurill to not circle any even number. As $n$ is even number, then there are a total of $n/2$ odd numbers when no move is played.The race of forcing the opponent to circle an even number begins now. We will show Aliceurill will always win this race and can force Bobasaur to pick an even number before him. We will now split cases for $n/2$ being odd or even. Case 1: $n/2$ is odd. For this case, after 1st move, there will be a total of $(n/2-1)$ odd cards remaining. After $(n/2)$th move of the game(Aliceurill's chance on $(n/2)$th move), there will be no odd cards remaining which forces Bobasaur to circle an even card and lose. To be precise, Bobasaur will lose at a maximum of $(n/2+1)$th move of the game. Case 2: $n/2$ is even. For this case, after 1st move, there will be a total of $(n/2)$ odd cards remaining. Again, after $(n/2+1)$th move of the game there will be no odd cards remaining and Bobasaur will be forced to circle an even even card and lose. To be precise, Bobasaur will will lose at a maximum of $(n/2+2)$th move of the game. Part IV: Showing no odd number $n$ with $\nu_q(n)>1$ works where $q$ is an odd prime dividing $n$. Assume $n=mz^2$ where $z$ is a prime number. The winning strategy for Aliceurril will be to choose $mz$ at his very first move. Now there are only $zm(z-1)$ numbers which are good and is an even quantity. Again whoever choses a multiple of $z$ loses on the spot. Let there be a total of $2k$ cards relatively prime $z$. Then at $(2k+1)$th move, Aliceurril will chose the last good card and Bobasaur will lose at a maximum of $(2k+2)$ moves. With the third part done, we can say that the solution is indeed complete now.$\blacksquare$ Remark. The problem was quite doable but I messed up very bad in exam, won't even get full marks as I initially claimed that the answer to the problem is primes which is quite tempting at first sight. The main reason of messing up was some calculation mistakes when I considered $n=21$. I did something really stupid which somehow made me think that $n=21$ makes Bobasaur lose. As for how you can motivate the solution, it is very easy if you just see some small cases for $n$ and try to play around. Guessing primes would work is really easy and and as for extension into "square-free numbers" just try some more examples and don't mess easy stuff like I did in contest. In my opinion it is fairly tricky to write-up this problem concisely which L567 had done a brilliant job at.

Hopefully this right? Rename Aliceurill and Bobasaur to A and B respectively. We claim that B is guaranteed to win iff $n$ is squarefree and odd. Case 1: $n$ is not squarefree. Proof. If $n$ is not squarefree, pick a prime $p$ such that $\nu_p(n)\geq 2$. On the first move, A will pick $n/p$. Since $\nu_p(n)\geq 2$, $p\mid n/p$. Letting $k=\nu_p(n)$, we have $p^{k-1}(p-1)$ numbers that are not multiples of $p$ remaining, which is an even number. As such, by a parity argument, B will be the first person to pick the next multiple of $p$, which gives $A$ victory. Case 2: $n\equiv 2\pmod{4}$. Proof. On the first move, A will pick $n/2$ which is odd. There are $n/2-1$ odd numbers remaining, and since $n/2-1$ is even by a parity argument, B will be the first person to pick the next multiple of $2$, which guarantees A victory. Case 3: $n$ is squarefree and odd. Proof. Let $n=p_1 p_2\dots p_k$. If A picks a number $a$, B will pick a number $b$ such that $ab$ is a multiple of $n/p_i$ and not a multiple of $p_i$ for some index $i$. WLOG, let $i=1$. Then, there are $n-n/p_1=p_2 \dots p_k(p_1-1)-2$ non-multiples of $p_1$ remaining, which is an even number. By a parity argument once more, A will pick the next multiple of $p_1$, meaning B will win.

Case 1: $n\equiv2\pmod4$ Aliceurill has a winning strategy: Let Aliceurill circle $\frac n2$. Then neither player can choose any multiple of $2$ (otherwise they lose immediately) and is a player doesn't choose a multiple of $2$, they don't lose on that turn. There are $\frac{n-2}2$ remaining numbers. Eventually, Bobsaur will have to choose a multiple of $2$ (since $\frac{n-2}2$ is even), at which point they lose. Case 2: $n$ isn't squarefree. Aliceurill has a winning strategy: Let $p^2\mid n$, and let Aliceurill circle $\frac np$ first. Then neither player can choose any multiple of $p$ (otherwise they lose immediately), and if a player doesn't choose a multiple of $p$, they don't lose on that turn. Now there are $n-\frac np=\frac n{p^2}p(p-1)$ remaining numbers. But then $\frac n{p^2}$ is an integer and $p(p-1)$ is even, so there are an even number of remaining numbers. Then Bobasaur eventually chooses a multiple of $p$, at which point they lose. Case 3: $n$ is squarefree and odd Bobasaur has a winning strategy: Suppose Aliceurill chooses $m$. If $m=n$ then Aliceuril loses, otherwise, since $n$ is squarefree, there is a prime $p$ with $p\mid n$ and $p\nmid m$. Now Bobasaur chooses $\frac np$. At this point, neither player can choose any multiple of $p$ (otherwise they lose immediately), and if a player doesn't choose a multiple of $p$, they don't lose on that turn, since $p$ doesn't divide the product of the numbers on the board yet $p\mid n$. We're left with $n-\frac np=\frac np(p-1)$ numbers on the board, which is even (since $n$ being odd implies $p$ is odd). Eventually, Aliceurill must choose a multiple of $p$, at which point they lose.

Nice one.

lol somehow this problem works out like magic The answer is all odd squarefree numbers. In this case, quite funnily, it suffices for Bobasaur to responds to Aliceurill's play of $k$ with $n-k$; this is always possible since $n$ is odd. Furthermore, for a game-ending number to be circled, said number must contain some prime factor in common with $n$ that no number circled before contained; this is not the case with $n-k$ and $k$, so Bobasaur will never end the game. If $n$ is even and squarefree, Aliceurill wins when she plays $\frac{n}{2}$. After she does this, players may only circle odd numbers, and the first player to be forced to circle an even number loses. In particular, $n$ is not a multiple of $4$; therefore, after playing $\frac{n}{2}$ (which is itself odd), there will be $\frac{n}{2} - 1$ odd numbers that can be circled. This value is even as well, hence Bobasaur will be the first player to have to draw an even number. If $n$ is an squarefull number, similarly, Aliceurill wins when she plays $\frac{n}{p}$ for some $p$ such that $p^2 \mid n$. If she does this, players may only circle a non-multiple of $p$, of which there are $n \left( \frac{p-1}{p} \right)$. (Since $p^2 \mid n$, $\frac{n}{p}$ itself is a multiple of $p$.) But the value $n \left( \frac{p-1}{p} \right)$ is always even, even when $p=2$ (since then $2^2 \mid n$), so Bobasaur will be the first player to have to draw an even number.

Solved with SuperHmm7 and Ammh4 The answer is $n$ is squarefree odd we firstly thought that $n$ is a perfect square doesn't work only but then while proving that discovered that $n$ must be squarefree. To prove the case were $n$ is a perfect square let $n=p^2$, we saw that A is favored to win if A circles $\frac{n}{p}$. After that there will be $n(1 - \frac{1}{p})$ not circled multiples of $p$, and since it's even (since $p(p-1)|\frac{n}{p}(p-1))$ we have that B loses. Now taking another look at our proof above we see that this also works on any $n$ such that $p^2|n$. So we found more numbers which guarantees A victory. Now let's prove for $n$ squarefree even. Applying the same argument, A chooses $\frac{n}{2}$, now we have $\frac{n}{2}-1$ odd numbers left, which is an even number, so B loses. Finally what is left is showing B wins otherwise. Let A circles $m$, then B circles a number $\frac{n}{q}$ such that $q$ is a prime doesn't divide $m$ Now we want A to choose a multiple of $q$. There are $\frac{n}{q}(q-1)$ not multiples which is even, so A loses.

The answer is all square-free odd numbers. Note that if one of them circles a number $k$, then the only numbers (excluding $k$) that can thence be circled are non-multiples of $\frac{n}{k}$. Aliceurill's wins: Case 1: If $v_2(n)=1$, then Aliceurill should circle $\frac{n}{2}$. Since $\frac{n}{2}$ is odd, there will remain $\frac{n}{2}-1$ odd numbers after Aliceurill's turn, and as $\frac{n}{2}-1$ is even, Aliceurill can ensure that she circles the last odd number to force Bobasaur to circle an even number and lose the game. Case 2: If $v_2(n)\geq2$, then Aliceurill should again circle $\frac{n}{2}$. Since $\frac {n}{2}$ is even, there will remain $\frac{n}{2}$ odd numbers after Aliceurill's turn, and as $\frac{n}{2}$ is even, Aliceurill can ensure that she circles the last odd number to force Bobasaur to circle an even number and lose the game. Case 3: If $n$ is odd and there exists a prime $p$ such that $p^2\mid n$, then Aliceurill should circle $\frac {n}{p}$. Since $p\mid\frac {n}{p}$, there will remain $n-\frac{n}{p}$ non-multiples of $p$, and as $n-\frac{n}{p}$ is even, Aliceurill can ensure that she circles the last non-multiple of $p$ to force Bobasaur to circle a multiple of $p$ and lose the game. $\square$ Bobasaur's wins: If $n$ is odd and square-free, then no matter what Aliceurill does on her first move, Bobasaur can guarantee his win. Suppose she circled $N$, where $1\leq N<n$. Then, only non-multiples of $\frac{n}{\gcd(n, N)}$ would be permitted. There are $n-\gcd(n, N)-1$ non-multiples of $\frac{n}{\gcd(n, N)}$ remaining (as Aliceurill had already selected $N$, which itself is a non-multiple). Clearly, $n-\gcd(n, N)-1$ is odd. Bobasaur should circle one of them. With respect to parity, there will eventually be a point where Bobasaur circles the last non-multiple, and then Aliceurill will be forced to circle a multiple of $\frac{n}{\gcd(n, N)}$, resulting in Bobasaur's win. $\square$

This is a perfect P1 difficulty problem. Here is my sol:- We claim only $n$ which are square free and odd work. First we show square free and odd works . Proof: Assume for contrary Aliceurill has a winning strategy , that would imply Aliceurill will never choose $n$ , now Bobasaur can just do the following that if Aliceurill chosses $x$ , Bobasaur chooses $n-x$ as $n$ is odd the two nos can never be equal , This would work because $gcd(n-x,n)=gcd(x,n)$ So no new prime factors will be added to the total product in Bobasaurs turns hence the final turn would have to be Aliceurill's causing contradiction Next we show no even $n$ works set $n=2k$ it suffices to show an winning strategy for Aliceurill. On Aliceurill's first turn he will chooe the number $k$, Now its basically who choses the first even number is going to lose . Now Alieurill is going to do something really simple guess what he is going to do ? If Bobasaur chooses $x$ he is going to chose $n-x$ , which is easy to finishes the problem. Now for the final one and perhaps hardest $n$ which is not square free and odd does not work . Pick any prime $p$ such that $v_p(n) \geq 2$ Aliceurill in his first turn is just going to choose the number $\frac{n}{p}$ . After this basically who choses the first multiple of $p$ loses Observe the number of numbers in the list which are not divisible by $n$ and not circled is $n(\frac{p-1}{p})$ Which is even , assuming Bobasaur plays optimally it must chose a number from those numbers Aliceurill will also choose another from the same list as there are total even number of numbers. Aliceurill will be the last person to chose a number from that list and after that Bobasaur is forced to chose a number divisible by $p$ forcing Alices victory !

Really cool problem, enjoyed this one a lot. I found it surprisingly accessible for ELMO standards, but thats good. Aliceurine and Bobasour are such unromantic names that the cultured mathematician is motivated to rename them WLOG to Alice and Bob respectively. We split the problem into several cases. Case 1 : $n=2$ Alice circles 1, Bob circles 2. Alice wins Case 2 : $n=p$ where $p$ is an odd prime. The first player to circle $p$ must lose, there are an even number of integers $p-1$ besides $p$ so Alice first runs out of moves, and is forced to pick $p$. Bob wins. Case 3 : $n=2k$ for some integer $k>1$. Alice circles $k$. The next player to circle an even integer loses. If $k$ is even, after this move there are \[2k-1-(k-1)=k\]odd integers left over, which is an even number of them so it is Bob who is forced to pick an even integer first. Alice wins. Similarly if $k$ is odd, after this move there are \[2k-k-1=k-1\]off integers left over, which is an even number of them so it is Bob who is forced to pick an even integer first. Alice wins. Case 4 : $n=p^2k$ for some odd prime $p$ and $k\equiv 1 \pmod{2}$. Alice circles $pk$. Then, the next player to circle a multiple of $p$ loses. Note that there are, \[p^2k-1-(pk-1)=pk(p-1)\]integers not divisible by $p$ after Alice's first move, which since $p\equiv 1 \pmod{2}$ is an even number of them. Again, Bob must run out of moves first. Alice wins. Case 5 : $n=p_1p_2\dots p_r$ for distinct odd primes $p_1,p_2,\dots , p_r$. We have three different strategies based on Alice's first move. If Alice circles $m$ such that $\gcd(m,n)=1$, then Bob circles $p_1p_2\dots p_{r-1}$. The first player to circle a multiple of $p_r$ loses. There are \[n-\frac{n}{p_r}-2 = \frac{n(p_r-1)}{p_r}-2\]integers not divisible by $r$ left over after this move, which since $p_r\equiv 1 \pmod{2}$ is an even number of them. Thus, it is Alice who runs out of moves first, and is forced to circle a multiple of $p_r$. Bob wins. If Alice circles $m=\frac{n}{p_i}k$ for some prime $p_i \mid n$ and $1\le k <p_i$ (if $k=p_i$ then Alice immediately loses), then the first player to circle a multiple of $p_i$ must lose. Note there are, \[n- \frac{n}{p_i}-1=\frac{n(p_i-1)}{n}-1\]integers not divisible by $p_i$ left over, which since $p_i \equiv 1 \pmod{2}$ is an odd number of them. Thus, Alice runs out of moves first and is forced to circle a multiple of $p_i$. Bob wins. Finally if Alice choses $m=p_{i_1}p_{i_2}\dots p_{i_j}k$ for some set of primes $p_{i_1},p_{i_2},\dots,p_{i_j} \mid n$ and $\gcd(k,n)=1$ (and $j<r-1$). Bob then circles $l= \frac{n}{\frac{m}{k}p_t}$ for some prime $p_t \mid n$ but $p_t \nmid m$. Clearly $l\ne m$ since $p_{i_1} \nmid l$ so this is a vlid move. But then, the next player to chose a multiple of $p_t$ will lose. There are, \[n-\frac{n}{p_t}-2=\frac{n(p_t-1)}{n}-2\]integers not divisible by $p_t$ left over after this move, which is again an even number, so Alice will run out of moves first. Bob wins.