Call the first player Frisk and the second player Sans. The answer is that the game is a draw for $n = 1, 2, 4, 6$ and Sans wins in all other cases. The cases $n = 1, 2, 4, 6$ may be done by hand. Also, in what follows we assume WLOG that Frisk's first move does not exceed $\frac12(n+1)$, by symmetry. The key observation is that if Sans picks $n$ on his first turn, then Sans will never lose. Indeed, consider Sans moving for the $k$th time. If we consider Frisk's earlier $k$ moves, they partition $\{1, \dots, n\}$ into either $k$ or $k+1$ nonempty continuous ``blocks'' (depending whether Frisk ever played $1$). Since Sans has only moved $k-1$ times, this implies there is some block that Sans hasn't touched, and he can play there. Now we claim $n > 1$ is odd that Sans will win by picking $n$ on the first turn. Indeed, the game can only draw if the protagonist manages to play $\frac{1}{2}(n+1)$ times; this means Frisk must choose all odd numbers, which is impossible since Sans already took $n$. Similarly, if $n > 2$ is even, then the game is a draw if and only if the protagonist chooses all odd numbers from $\{1, \dots, n-1\}$. For $n \ge 8$, it is easy to see that Sans can pick an odd number on his second turn, thus Frisk will lose in this case too.

Quite lengthy solution.. I didn't see a nice argument to show why n=6 works and n=8 fails... The outcome is a draw for $n=1,2,4,6$, and player $B$ wins for all other $n$. Throughout this solution, we assume $A$ do not choose $n$ in his first move due to symmetry, otherwise we may flip the numbers in desending order and do not change the outcome of the game. Let us define a game to be an $AB$-game of length $\ell\ge 2$, if players $A$ and $B$ had chosen numbers $1, \ell$ in their first move, not necessarily in this order. Before we start, we prove two lemmas. Lemma 1. Player $B$ can guarantee at least a draw in an $AB$-game of even length and of length $3$, and a win for an $AB$-game of odd length at least $5$. Proof. If $\ell \le 3$, both players cannot make another move, thus a draw. Now suppose $\ell\ge 4$, then in either case, WLOG that $1$ is chosen by $A$ and $\ell$ is chosen by $B$. Clearly, $A$ cannot make a move at $2$ anymore. Now, the strategy for $B$ is whenever $A$ makes a move at $k\ge 3$, then $B$ make a move at $k-1$. Of course, otherwise suppose for the first time this strategy do not work, which is $B$ cannot make a move at $k-1$. If it is because $k-1$ is a previously chosen number by either player, it is impossible that this player is $B$, since $B$ always make a move one less than $A$'s previous move, so if $k-1$ is chosen by $B$ before, then $k$ must be chosen by $A$ right before this move, so $A$ now cannot make another move on $k$ anymore, contradiction. If this player is $A$, then $k-1$ and $k$ are now both chosen by $A$, contradiction. So it must be because $k-1$ is a number consecutive to some moves by $B$. But $k$ is now chosen by $A$, so $k-2$ must be previously chosen by $B$. But by player $B$'s strategy, he will make this move if and only if $A$ make a move at $k-1$ before his move. Then $k$ and $k-1$ are now both chosen by $A$, contradiction. So such a scenario that player $B$ cannot follow this strategy cannot happen. So whenever $A$ makes a move, $B$ can make a move, untill $A$ cannot make a move. So for $k$ is even, $B$ can at least force a draw, and if $k$ is odd, since the number of moves is even, not all numbers are chosen, so $B$ wins. This proves Lemma $1$. Lemma 2. Player $B$ can in fact guarentee a win in an $AB$-game of length $\ell$, for $\ell\ge 8$ is even. Proof. We prove this by induction. For the base case, consider an $AB$-game for $\ell=8$, suppose again that $A$ makes his first move at $1$, and $B$ makes his first move at $8$. If $A$ make his second move at $3$, $B$ can make a move at $5$. Then regardless of $A$'s next move which must be $6$ or $7$, $B$ can make another move at $2$. Then $A$ cannot make anymore moves, so $B$ wins. If $A$ make his second move at $4$, $B$ can make a move at $6$. Then regardless of $A$'s next move which must be $7$, $B$ can make another move at $2$. Then $A$ cannot make anymore moves, so $B$ wins. If $A$ make his second move at $5$, then $B$ can make a move at $3$. Then regardless of $A$'s next move which must be $7$, $B$ can make another move at $6$. Then $A$ cannot make anymore moves, so $B$ wins. If $A$ make his second move at $6$ or $7$, then $B$ can make a move at $5$. Then regardless of $A$'s next move which must be $3$ or $4$, $B$ can make another move at $2$. Then $A$ cannot make anymore moves, so $B$ wins. So in any case, an $AB$-game of length $8$ is a $B$-win game. Now we proceed to the inductive step. Suppose an $AB$-game of length $\ell$ is a $B$-win game for all even $8\le \ell\le 2k$, $k\ge 4$. Consider an $AB$-game of length $\ell+2$ and suppose again that $A$ makes his first move at $1$, and $B$ makes his first move at $\ell+2$. if $A$ make his second move at $3$, then $B$ can make a move at $2$. Neglect the first two numbers, then this reduces to an $AB$-game of length $\ell$, so $B$ can use his winning strategy on the $AB$-game of length $\ell$ and win the whole game. Suppose now that $A$ make his second move at an odd number $k\ge 5$, then $B$ can make a move at $k-2$. Clearly, neither of the players can make a move at $k-1$. This partition the entire game into two $AB$-games. So whenever $A$ makes a move at the first game, then $B$ make the non-losing move at the first game, and vice versa for the second game. Such a non-losing strategy exists by Lemma $1$, regardless of the length of both games. So $B$ can ensure a tie, and therefore a win, since $k-1$ is not moved by either players. Similarly if $A$ make his second move at an even number $k\ge 4$, then $B$ can make a move at $k-1$. In a similar fashion, this partition the entire game into two $AB$-games. Similar to the first case, $B$ can again ensure a tie. Notice that because $k-1$ is odd, so consider the $AB$-game for numbers $1$ to $k-1$, then at least one numbers from $1$ to $k-1$ is not chosen because the number of moves in that game is even. So the entire game is a $B$-win game. This proves that an $AB$-game of length $\ell\ge 8$ and $\ell$ is even, is a $B$-win game, and proves Lemma $2$. Back to the main proof. Let us first consider $n$ is odd. Clearly $n=1$ gives a draw since $A$ can choose $1$ in his first move. For $n\ge 3$, suppose the first move of player $A$ is $k\le n-1$, then $B$ may make a move at $n$. Then whenever $A$ makes a move $m\le k-1$, then $m\neq k-1$, so $m\le k-2$. Similar to the strategy in Lemma 1, player $B$ then chooses $m+1$ whenever $A$ chooses $m$, and the reason why $B$ can always make such a move is similar as in Lemma 1. Likewise, if $A$ makes a move $m\ge k+1$, then $m\neq k+1$, so $m\ge k+2$. Then player $B$ again chooses the number $m-1$ whenever player $A$ chooses $m$. So $B$ can ensure at least a tie, in fact he ensured a win by doing so, since the number of moves is even, it is impossible for all numbers to be chosen, so $B$ wins for all odd $n$. Next, consider $n\le 6$ is even, we claim that $A$ can force a tie, without letting $B$ to win. First, for $n=2$, this is obvious, since $A$ and $B$ will pick both numbers $1,2$ in some order. For $n=4$, $A$ pick his first move at $1$, if $B$ make a move at $3$, then $A$ make his next move at $4$, then $B$ loses. Otherwise, no matter $B$ chooses $2$ or $4$, $A$ can always make his next move at $3$, and $B$ can move at the remaining number, forcing a tie. For $n=6$, $A$ make his first move at $1$, then if $B$ make his first move at $2\le i\le 3$, then $B$ cannot make a move at $i+1$ at any time. Then $A$ make a move at $i+3\le 6$, then regardless of $B$'s next move, then $A$ can always make a move at $i+1$, forcing at least a tie. If $B$ make his first move at $4\le i\le 5$, then $B$ cannot make a move at $i+1$ at any time. Then $A$ make a move at $i-1\ge 3$, then regardless of $B$'s next move, then $A$ can always make a move at $i+1$, forcing at least a tie. Finally if $B$ make his first move at $6$, then $B$ cannot move at $5$ at anytime. So $A$ moves at $3$, then regardless of $B$'s next move, then $A$ makes a move at $5$, forcing at least a tie. So we conclude that $n=2,4,6$ is a draw. Now consider $n\ge 8$ is even, we claim that player $A$ must choose $1$ as his first move to play optimally. Suppose not, WLOG let $A$ chooses $2\le k\le n-1$ in his first move. If $k$ is odd, player $B$ make his move at $1$, and at $n$ otherwise, since $A$ do not choose either $1, n$ in his first move. With appropriate fliping of the numbers, WLOG assume that $1$ is chosen by $B$, $k$ is chosen by $A$, where $k$ is odd, since otherwise if $k$ is even and $B$ chooses $n$, then flipping the numbers gives $n-k+1$ is odd and chosen by $A$, while $B$ chooses $1$ instead, so WLOG the former case is true. Now similar to the previous paragraph, whenever $A$ makes a move $m\le k-1$, then $m\neq k-1$, so $m\le k-2$. Then player $B$ then chooses $m+1$ whenever $A$ chooses $m$. Likewise, if $A$ makes a move $m\ge k+1$, then $m\neq k+1$, so $m\ge k+2$. Then player $B$ again chooses the number $m-1$ whenever player $A$ chooses $m$. So $B$ can ensure at least a tie, in fact he ensured a win by doing so, because if we consider the numbers from $1$ to $k$, the subset of moves by $A$ and $B$ at these $k$ numbers is an $AB$-game of length $k$, so by $B$'s strategy, the number of moves on the $k$ numbers is even, so not all numbers from $1$ to $k$ is chosen, so $B$ wins. This is a contradiction. So $A$ must choose $1$ as his first move to play optimally. However, then $B$ may choose to move at $n$ after the first move of $A$. This means that the original game is now an $AB$-game of length $n$, which by Lemma $2$ is a $B$-win game. So $B$ wins for $n\ge 8$, $n$ even. We conclude that the outcome is a draw for $n=1,2,4,6$, and player $B$ wins for all other $n$. Q.E.D

Hint (for sufficiently large n): Use A's picks as "dividers" that guarantee you can choose a number in between two consecutive dividers. Grab one of the end integers ASAP so you'll have enough divisions to survive.

IMO ShortList 2015 C4 wrote: Let $n$ be a positive integer. Two players $A$ and $B$ play a game in which they take turns choosing positive integers $k \le n$. The rules of the game are: (i) A player cannot choose a number that has been chosen by either player on any previous turn. (ii) A player cannot choose a number consecutive to any of those the player has already chosen on any previous turn. (iii) The game is a draw if all numbers have been chosen; otherwise the player who cannot choose a number anymore loses the game. The player $A$ takes the first turn. Determine the outcome of the game, assuming that both players use optimal strategies. Proposed by Finland Answer: For $n \in \{1,2,4,6\}$ the game ends in a draw, else $B$ wins. (Proof) Check the claim for $n \le 6$ by hand. We employ the following heuristic: $B$ should have a strategy which allows him to make a move as long as $A$ can, For $n$ odd, $B$ must mark an odd cell, For $n$ even, $B$ must mark two cells of different parity. For notational purposes, look at the game as the two players marking numbered cells on a $1 \times n$ grid with their respective signatures, $A$ and $B$. Case 1. $n \ge 5$ is odd. Let $A$ mark a cell at the start of the game; $B$ picks one of the endpoints of the board with distance $\ge 2$ from $A$'s cell, say it's the rightmost cell. In all subsequent turns of $A$, where he marks $k$, $B$ marks one of $\{k-1, k+1\}$ according to the following rule: If $k$ is to the left/right of the current string of $A$s, $B$ uses $k-1, k+1$ accordingly, If $k$ Is between two $A$s, say $A_1, A_2$ then $B$ marks $k-1, k+1$ so that it lies on the opposite side of the $B$ in $A_1A_2$ from $k$. Note that $B$ can always make a move if $A$ can, so the only possibility other than win for $B$ is a draw. However, a draw can occur only when $A$ has marked all odd cells, contrary to the assumption that $B$ marks one of the endpoints (as $n$ is odd). Case 2. $n \ge 8$ is even. As before, $B$ marks an endpoint (say $B_1$) after $A$'s first turn, which is closer to the cell he just marked. Let him mark $A_1, A_2$ at the first and second turn, in some order. WLOG, $B_1=1, A_1<A_2$, then we look at the following possibilities: Sub-Case 1. $A_2>A_1+2$. Now, $B$ marks a cell $B_2 \in \{A_1+1, A_1+2\}$, so that both blocks before $B_2$ and the remaining, contain an odd number of points. It is clear that $B$ can apply his winning strategy from the odd case, as the game proceeds on both these blocks; ensuring her a win. Sub-Case 2. $A_2=A_1+2$. As $A_2$ is not the other endpoint, $B$ marks the other one as $B_2$. Now, we see that the game is non-losing on one and winning on the other arc, for $B$ on $B_1A_1$ and $A_2B_2$ for parity reasons; hence she wins the overall game. We conclude from the previous analysis that the game has the exact same outcome as we desired. $\blacksquare$

The drawing positions are $1,2,4,6$, $B$ wins in all other positions. It is easy to check that this is true for $n<9$. We proceed by induction on $n$. Case $1$: If $A$ divides the game into two games with losing positions, then by using the fact that a sum of games with losing positions is winning, $B$ wins. Case $2$: Let the first number $A$ chooses be $a$. For the positions where $A$ divides the game into two games with drawing positions, $B$ chooses the number farthest away from $a$.WLOG, suppose $B$ chooses the rightmost number. $B$'s winning strategy is: If $A$ plays on the same side of $B$, $B$ will play to either win or draw/lose AND force $A$ to choose $a+2$ If $A$ plays on the other side, $B$ plays for a draw. It will be $A$'s turn once the left side is drawn, so $B$ wins. Case $3$: If $A$ divides the game into two games, one with a drawing position (WLOG on the right side) and one with losing position. Then $B$ chooses to play on the drawing side and chooses the number farthest to $a$ . $B$'s winning strategy is as follows: If $A$ plays on the losing side then $B$ will play to win that side If $A$ plays on the drawing side, then $B$ can either win that side, draw/lose AND force $A$ to choose $a+2$ (depending on what $A$ does) If $B$ wins the drawing side, it is $A$'s turn and $B$ wins. If $B$ draw/loses and forces $A$ to choose $a+2$ then $B$ choose $a+1$ and $B$ wins.

CantonMathGuy wrote: Let $n$ be a positive integer. Two players $A$ and $B$ play a game in which they take turns choosing positive integers $k \le n$. The rules of the game are: (i) A player cannot choose a number that has been chosen by either player on any previous turn. (ii) A player cannot choose a number consecutive to any of those the player has already chosen on any previous turn. (iii) The game is a draw if all numbers have been chosen; otherwise the player who cannot choose a number anymore loses the game. The player $A$ takes the first turn. Determine the outcome of the game, assuming that both players use optimal strategies. Proposed by Finland Consider the game with (ii) replaced by (ii)': A player cannot choose a number consecutive to any number chosen by any player on any turn. Is it true that $B$ has winning strategy iff $n = 4k$ ?

ANSWER: $B$ wins the game in all cases except for $n=1,2,4,6$, in which case it is a draw. SOLUTION: For notation's sake, we think of the game as one in which $A$ and $B$ are supposed to form a binary string of length $n$, with $A$ putting zeros and $B$ putting ones in the $n$ squares available, such that $A$ starts the game. The only restriction is that no two consecutive digits can be the same. The person who is no longer able to make a move loses the game. At any moment of time in the game, we call a square accessible to a player if he/she can make their move on that square without violating the rules. Now, we make two cases as follows-

Summarizing, $B$ wins in all possible cases. Hence, done. $\blacksquare$ REMARK 1: To be honest, even though the writeup to the case where $n$ is even looks extremely small, it took me almost 1.5 times the time it took me to do Case-1. The construction for odd $n$ is easy to get if one plays with some small cases. The main difficulty in Case-2 is to understand that it follows from Case-1 easily. Most of my time initially went in trying to find some construction for even $n$. It was only after failing for around an hour or so, that I realized my folly . REMARK 2: Another thing that perplexed me throughout the problem was why $B$ fails to win when $n=2,4,6$, but wins for other even values of $n$. It was only at the end that I realised why this was happening. When I was playing around with small cases and saw that the game was a draw for $n=2,4,6$ and a win for $B$ if $n=3,5,7$, I was about to make my mind that $B$ can win if $n$ is odd, and there is a draw otherwise. It was sheer luck that I tried $n=8$ just to get some more insight into the problem, and saw that $B$ was able to pull a win. If that had not happened, then I probably would have spent around $4$ hours on this one problem .

We claim the game is a draw for $n=1,2,4,6$, and $B$ wins for any other $n$. It is not too hard to check that there is a draw for the claimed values. Claim: $B$ never loses, i.e. $B$ can always win or draw. Proof: This is really neat. We will show that no matter what $A$ does, $B$ can move. After $A$ moves initially, there is at least one ``endpoint'' remaining, i.e. either 1 or $n$. Have $B$ capture an endpoint, WLOG 1. Now, the rest of the number line is left, except for 1. Here is the key: basically $A$'s moves are like dividers of the number line, since no two $A$'s can be adjacent. Between any two dividers, there is at least one spot for the $B$ to capture. Note that $B$ will never be forced into capturing 2, since 2 is not between two dividers. Hence, $B$ can never lose. $\square$ Claim: For $n\ge 3$ odd, $B$ can win. Proof: We need only show that $A$ cannot draw the game. The only way $A$ can draw the game is if $A$ is able to capture $\tfrac{n+1}{2}$ cells, since $A$ goes first. But this means $A$ needs to get all the odds, which is impossible since $B$ takes 1 or $n$, both of which are odd. $\square$ Claim: For $n\ge 7$ even, $B$ can win. Proof: Again, we will show that $A$ cannot draw. If there is a draw, we know $A$ ends with $\tfrac{n}{2}$ cells captured. If $A$ initially captures an odd, have $B$ capture $n$, an even. Now, $A$ needs to capture all the odds, so $A$ will capture another odd. Now, since $n\ge 7$, have $B$ capture an odd, ruining $A$'s drawing strategy. A similar logic works for if $A$ initially captures an even. $\square$

v_Enhance wrote: If we consider A's earlier $k$ moves, they partition $[n]$ into exactly $k+1$ nonempty continuous blocks, separated by one number. If $A$ chooses $1$, then wouldn't there only be $k$ continuous blocks? This would still allow $B$ to move, but now there is just at least one block instead.

You're right! I amended my post.

Asdfdangit I thought for SO LONG that the consecutive condition was each player not being able to select a number consecutive to ANY previously chosen number. v_Enhance wrote: Call the first player Frisk and the second player Sans. Frisk and Sans it is. I claim that the game ends in a draw when $n \in \{1, 2, 4, 6\}$, which can all easily be casechecked ($n = 6$ is slightly annoying). The key claim is this: Claim: Sans can always prevent loss. Proof: Write the integers $1 \to n$ out from left to right. First, note that Sans can always choose one of the endpoints $1$ or $n$ on his first pick. WLOG he is allowed to pick $1$. Suppose the game plays to a point where Frisk has made $m$ moves and Sans has made $m-1$. At this point there are $m$ Frisk numbers on the whiteboard, every two separated by at least one number. These $m$ Frisk numbers divide the numbers $1 \to n$ into at least $m$ sections of at least one number each, as no two Frisk numbers can be adjacent, where the leftmost section is occupied by Sans's first pick $1$. The remaining $m-2$ Sans numbers occupy at most $m-2$ of the remaining $m-1$ unoccupied sections, so there are at least\[m - 1 - (m-2) = 1\]empty sections with where Sans can make his $m$th pick. Thus, as long as Frisk can move, Sans can move. $\square$ For the rest of the problem, we employ a similar strategy for Sans, with him picking either $1$ or $n$ on his first move. WLOG he is allowed to pick $1$. We split cases: For odd $n \geq 3$, note that since Frisk moves first, in order for him not to lose he must be able to pick $\tfrac12(n+1)$ numbers, no two of which are consecutive. The only way he can do this is choosing $1, 3, 5, \ldots , n$ but this is impossible since $B$ has chosen $1$, so Frisk loses. For even $n \geq 8$, since Frisk goes first, in order for him to not lose he must be able to choose $\tfrac12n$ numbers from $2 \to n$ since $1$ is taken. Because $n \geq 8$ is sufficiently large, Sans can always pick an even number on his second turn to destroy Frisk's dreams, forcing Frisk to lose. Therefore, our only answers are $n \in \{1,2, 4, 6\}$, as desired. $\blacksquare$

Solved with nukelauncher. The game is a draw for \(n=1,2,4,6\), and a victory for Beus otherwise. The cases \(n=1,2,4,6\) can be handled manually. Claim: For odd \(n\ge3\), Beus wins. Proof. Suppose Athena plays card \(\le\frac{n+1}2\) on her first move. I will show that if Beus plays slot \(n\) on his first move, then he wins. Evidently the game is not a draw, since that would require Athena play both cards 1 and \(n\). Fast-forward to the end position, and suppose Athena has played a total of \(k\) cards. If Beus loses, then Beus has played \(k-1\) cards and can no longer play. However between any two of Athena's cards is at least one card that Beus can play but Athena never can. There are \(k-1\) such ``free cards,'' and Beus has already played one card, so he has \(k\) available cards he can play. This is a contradiction, so the claim is proven. \(\blacksquare\) Claim: For even \(n\ge8\), Beus wins. Proof. Suppose Athena plays card \(\le\frac n2\) on her first mvoe. Beus' strategy is as follows: On his first move, play card \(n\). On his secnod move, paly an odd card. It is easy to check that Beus can accomplish this for \(n\ge8\). Evidently the game is not a draw, since that would require all of Beus's cards to be the same parity. Now Beus's first two cards divide the remaining cards into two sections. Fast-forward to the end position, and let Athena play \(i\) cards in the left section and \(j\) cards in the right section. If Beus loses, he has played \(i+j-1\) cards and can no longer move. But Beus has \(i-1\) ``free cards'' in the left section and \(j-1\) ``free cards'' in the right section. Recall he has already played two cards, so he has \(i+j\) available cards he can play. This is a contradiction, so the claim is proven. \(\blacksquare\)

Nice problem. Replace $A$ and $B$ with Frisk and Sans. I claim that the game ends in a draw when $n = 1,2,4,6$ and Sans wins otherwise. It is easy to check the cases where the game ends in a draw by hand. Note that a draw only occurs when Frisk chooses all of the odd numbers, and Sans chooses all of the even numbers (unless $n$ is even, in which Sans may choose all of the odds, and Frisk the evens). Suppose the number Frisk chooses on his first turn is less than $n/2+1$, by symmetry. Here is the main idea: Claim: If Sans chooses $n$, then Sans cannot lose. Proof: Suppose for the sake of contradiction that Sans has lost. Frisk has moved $k$ times, whereas Sans has only moved $k-1$ times. Evidently the $k$ numbers partition the positive integer number line from $1$ to $n$ into at least $k$ non-empty disjoint sections ($k-1$ is not possible since Sans took $n$). Now Sans can play at least once in each section, so Sans can make at least $k$ moves, a contradiction. Now, for $n \geq 3$ odd with this strategy Sans wins immediately, as Frisk can only draw by choosing all of the odd numbers. For $n \geq 8$ even, if Frisk chooses an even number to begin Sans wins outright. Otherwise, Frisk must choose all the odd numbers between $1$ and $n-1$ to draw. But Sans can just choose an odd number on his second move and win.

Where did Frisk and Sans come from?

stroller wrote: Is it true that $B$ has winning strategy iff $n = 4k$ ? I tried to prove this (because I misread the original), but there is no strategy that guarantees a win for $B$ when $n=12$ and the first move of $A$ is $4$. As for $n=4$ or $8$, $B$ wins. I didn't check other multiples of $4$. I would be curious if anybody else has a solution to this version. It's clear that by the mirror strategy $A$ can win when $n$ is odd, also if $B$ has a winning strategy for $n$, then $A$ can choose $1$ and use the same strategy to win for $n+2$.

stroller wrote: Consider the game with (ii) replaced by (ii)': A player cannot choose a number consecutive to any number chosen by any player on any turn. Is it true that $B$ has winning strategy iff $n = 4k$ ? nope, by bashing , A wins when n = 12, and B wins when n = 14 samrocksnature wrote: Where did Frisk and Sans come from? it's from a game called Undertale, one is the protagonist while the other is sort of like an antagonist. I think it's nice that their initials lines up with first and second.

If $n=1,2,4,6$ then the game will draw, otherwise $B$ wins. It is easy to check the small cases so we will assume $n\geq 8$. We will consider the equivalent game of occupying cells of an $1\times n$ table. Claim 1. $B$ can guarantee that he never lost. Proof. No matter how $A$ moves, $B$ will occupy the unoccupied corner. Then, in his second turn, $B$ will occupy a cell in between the first two cells occupied by $A$. \begin{tabular}{ |c|c|c|c|c|c|c|c| } \hline ...&A&...&B&...&A&...&B\\ \hline \end{tabular}Then, afterwards, everytime $A$ make a move, there will be two $A$'s with no $B$ in between, since there is at least one empty cell, $B$ can make his move in that empty cell. This implies $B$ can guarantee a move, and hence avoiding losses. $\blacksquare$ Now, if $A$ make a move creating an two $A$ with at least $2$ cells apart and no $B$ in between, then $B$ can occupy the cell $x$(labelled in the figure) in the above described strategy, then the cell $y$ can not be occupied, therefore it is not possible for all numbers to be chosen. In other words, a draw can not occur and $B$ must win. \begin{tabular}{ |c|c|c|c|c| } \hline A&y&x&...&A\\ \hline \end{tabular}Therefore, every occupation of $A$ must be two cells away from some previous ones. In particular, if $n>1$ is odd and $A$ can enforce a draw, then it must occupy $\frac{n+1}{2}$ cells, and in particular to cells have different parity, contradiction. Therefore if $n$ is odd then $B$ wins. We now consider the case when $n$ is even. Firstly, if the first two moves of $A$ do not involve an occupation of the corner then $B$ can occupy the other corner and carry out the strategy describes in Claim 1. Therefore, $A$ must capture the first and third cell in his first turn. Now the configuration is uniquely determined. That is, $A$ must choose $1,3,5,...$ and $n,2,4,...$ in that order. However, notice that when $n=8$, after $A$ chooses $1,3$ and $B$ chooses $8$, $B$ can choose $5$ instead of $2$ and wins. Therefore, $B$ can wait until the turn after $A$ chooses $n-5$ and carry out the winning strategy of $n=8$ and wins the game.

I initially misread rule (ii) as saying a player cant choose a number adjacent to a number chosen by either player earlier. It was only when I wondered how the game was supposed to end in a draw when my eyes worked and I read it properly. Also I was for some reason convinced the answer was its a draw for all evens and $1$ and $B$ wins otherwise, until I tried $n = 8$ and couldn't get $A$ to manage a draw. Anyway here's my solution. The answer is that its a draw only for $1,2,4,6$ and $B$ wins otherwise. First, $A$ can never win since $B$ just picks one of $1,n$ on his first turn. Now, suppose $B$ cant play anymore, and say its the $k$th turn. Split the numbers from $1,2,\cdots,n$ into $k$ blocks which each have a gap of at least $1$ in them. So at least one is empty and $B$ can play, contradiction. The only way the game can end in a draw is if one person picks all odd numbers and one picks all even numbers. WLOG assume that $B$ managed to pick $1$ on his first turn, so on the next turn, he can choose one of $4,6$ and so $A$ cannot manage to pick all evens. Now, to deal with the cases when $n \le 6$. i) $n = 1,2$ are obviously draws ii) For $n = 3$, if $A$ chooses $1$ then $B$ chooses $3$ and if not, $B$ chooses anything and wins. iii) For $n = 4$, if $A$ chooses $1$, $B$ chooses $4$ and when $A$ chooses $3$, $B$ chooses $2$ and draws. If $A$ chose $2$, then $B$ chooses $3$, $A$ plays $4$ and $B$ plays $1$ to draw. iv) For $n = 5$, once $B$ chooses one of $1,5$, $A$ must pick only $2,4$ but then there's a number remaining so it cant be a draw, so $B$ wins. v) For $n = 6$, the following strings represent different possibilities because I'm too lazy to type up the whole thing - $163254, 165234, 1642, 2643, 2653, 361254, 365412$. So, its a draw exactly for $1,2,4,6$ and $B$ wins otherwise, as claimed. $\blacksquare$

Main Claim: For any $n$, if $B$'s first move is to choose an endpoint (1 or $n$), then at every point during the process, $B$ will have a valid number to choose. In particular, $B$ will not lose. Proof: After $A$'s first move, at least one endpoint is open. Have $B$ choose an endpoint. WLOG $A$ has $1$ and $B$ has $n$. At any arbitrary point in the process, suppose there are $k$ $A$'s played, and it is now $B$'s turn. The $k$ $A$'s create at least $k-1$ blocks of space, each of which contains no $A$'s. (We cannot say there are $k$ or $k+1$ blocks, since worst case, the $A$'s are at $1$ and $n-1$ by this point.) There are currently $k-1$ $B$'s played, one of which is at $n$, so there are $k-2$ $B$'s in these blocks. Now it is $B$'s turn, so he is guaranteed to have a place to play. So $B$ can't lose. $\blacksquare$ We claim if $n\ge 3$ is odd, then $B$ wins. Suppose $A$ could draw. Then the final state has to be $ABABA...BA$. So $A$ will pick some odd index, and then have $B$ pick $1$, blocking the needed end state for $A$'s draw. Since $B$ does not draw or lose, $B$ wins with this specific strategy. We claim if $n\ge 8$ is even, then $B$ wins. Suppose $A$ could draw. The final state will then be $ABAB...AB$ or $BABA...BA$, so all the $A$'s have same parity position. Simply have $B$ choose an endpoint first (at least one will be available on $B$'s first move), and then on his next move, a number of opposite parity to his first endpoint. At this point, $B$ is and can continue to follow the strategy from the Main Claim to not lose since $B$'s first move was an endpoint. Since this specific strategy makes $B$ not draw, $B$ will in fact win. (We require $n\ge 8$ since for $n=6$, the following is possible: $******\to A*****\to A****B\to A*A**B$, at which point $B$ cannot choose a cell with different parity as the right endpoint.) It is easy to check that for $n=1,2,4,6$, the result is a draw.

B wins whenever $n\neq 1,2,4,6$, and otherwise we draw. Verifying the 4 edge cases is trivial. Assume WLOG that A didn't choose $n$ (if they did, then replace $k$ with $n+1-k$). Then, B can choose $n$. Afterward, if $n$ is odd, then on B's $i$th turn, A will have chosen at most $i-1$ numbers that aren't 1, so each turn B can choose something directly below a number that A has chosen. This guarantees a win for all odd $n\ge 3$, as A already can't choose every 2nd number, which is needed to guarantee a draw. A similar strategy for even $n\ge 8$ exists. A needs the odds to draw, but if A doesn't choose in the order $1,3,5,7\ldots$ or $3,1,5,7\ldots$ B can win by choosing something 2 below a number A has chosen at some point, which evidently still works. If A plays 1,3 to start in some order, B can play 5 win on the numbers $6,7\ldots n$ with the exception that when $B$ is supposed to choose $6$, they choose $2$ instead.

How funny! If odd > 1, Bob flips both index and color and places there, and if Alice places in the middle, Bob places one space off towards the other Alice color and splits the interval of flips into two. By parity Bob wins. If even, notice if Alice picks not an edge of the interval (1 or n) then Bob can pick an edge of the interval in a way (parity) to force Alice to pick the opposite edge on turn two, since otherwise if Bob gets both interval edges he wins via the same strategy as odd > 1. So WLOG in the case where Alice picks 1 first and Bob picks n first, then Alice must have picked 3 on turn 2 since otherwise Bob can pick the number two less than Alice's pick and by the same strategy as odd > 1, Bob wins by splitting the interval and neither player can play in the square one less than Alice's second move. So if Alice picks 3, then if $n \geq 8$ Bob can picks $n - 3$, and then notice we can biject the game to the $n-1$ case since the Bob interval of space 2 is equivalent in every way to an interval of space 1 and the setup is achievable as a subcase from the odd > 1 strategy, since $n - 3 \neq 1, 3$ and is positive if $n \geq 8$. Now by checking, the only drawing strategies for Alice are $n = 1, 2, 4, 6$ and all others are wins for Bob.

Let $B$ make their first move on $1$ or $n$. Suppose A has moved $x$ times, then A has split the numbers into $x$, or $x+1$ blocks of consecutive numbers. The numbers in these blocks are able to be chosen by $B$. After A makes the $x$th move, $B$ has moved $x-1$ times, so there is one block in which $B$ has never moved before, so $A$ never wins. $A$ wins if and only if they can pick at least half of the numbers, so all of them with one parity. If $n>1$ is odd, this is not possible, because $B$ can guarantee one of $1$ or $n$. If $n>8$ is even, this is also not possible, because after $B$ chooses one of the $1$ or $n$, $B$ can choose a different parity one. Thus, the game draws when $1,2,4,6$ and $B$ wins otherwise.

Name the players Alice and Bob. Interpret the game as being played by coloring cells with $A$ or $B$ in a $1 \times n$ rectangle. The game is a draw if $n=1,2,4,6$, and Bob wins otherwise. The game is obviously a draw for $n=1,2$. To show that $n=4,6$ are draws as well, first note that with a straightforward mirroring strategy Bob can always guarantee at least a draw if $n$ is even, so it suffices to show that Alice has a strategy to prevent Bob from winning. This is not a difficult case check if we commit to having Alice always start by playing on the leftmost square and do casework on Bob's first move, with Alice's general strategy being to restrict Bob's moves as much as possible. We now show that Bob wins otherwise, beginning with the following useful claim that essentially details Bob's strategy. Claim: Suppose there is an interval of at least $2$ cells whose endpoints are colored, whose colored cells alternate order (i.e. by moving from the left to right endpoint, the colors read $ABAB\ldots$ or $BABA\ldots$), and no cells outside the interval are legal plays for the player whose turn it is. Then the other player can always make a move after the first player's turn. Proof: WLOG it is currently Alice's turn. The idea for Bob is to maintain the alternating pattern. If Alice can make a move, it must on some cell $c$ inside the interval. If the closest color to the left of $c$ (which must exist) is $A$, then the closest to the right of $c$ (which must also exist) is $B$, and then Bob can color the cell directly to the left of $c$. In the other case, Bob colors the cell directly to the right of $c$. This clearly maintains the alternating pattern, so by induction we are done. $\blacksquare$ Additionally note that, if there exists some cell which must remain empty in this scenario (which will happen if some cell borders a cell colored $A$ and a cell colored $B$), then this means that Bob can guarantee a win. Now, for $n$ odd, if Alice makes a move on the leftmost (sim. rightmost) cell, Bob makes a move on the rightmost cell, and by the claim (by taking the interval to be the entire rectangle) he can always guarantee that he can move after Alice can. Otherwise, Bob still moves on the rightmost cell no matter what. He then tracks an "interval of interest", which initially extends rightwards from Alice's first move (inclusive). If Alice moves inside this interval of interest, Bob plays according to the claim. Otherwise, Bob colors the cell directly to the right of Alice's previous turn, which is clearly always possible, and updates the "interval of interest" by moving its left end to the cell just colored by Alice (in this way, Alice always has the leftmost colored cell). In both cases, since $n$ is odd, if a draw occurs it must be immediately after Alice makes the last move, but this contradicts the fact that Bob can always play after Alice, hence Bob can guarantee a win. We now do $n \geq 8$ even. If Alice does not make her first move on an endpoint, then WLOG suppose that there are an even number of cells strictly to the right of Alice's first colored cell (since $n$ is even, we can reflect if this isn't the case). Then Bob moves on the rightmost cell and then implements the same strategy in the analogous case for $n$ odd, which means that Bob can always avoid losing. Furthermore, if a draw occurred, the cells would have to all be colored, and in an alternating fashion, but since the cells colored on the two players' first moves are separated by an odd number of cells and are different colors, this is impossible, hence Bob in fact always wins in this case. If Alice does make her first move on an endpoint (WLOG leftmost), then Bob responds by moving on the rightmost cell. If Alice's second move is on a cell which is not the third cell from the left, then Bob colors the cell two to the left from this cell and then implements the strategy in the claim. Furthermore, since the cell between the ones colored in Alice's and Bob's second turns can never be colored, Bob guarantees a win in this case. Otherwise, Bob colors the fifth cell (two to the right of Alice's second move), which is possible since $n \geq 8$. Then Alice must move to the right of the fifth cell on her third turn, and Bob colors the the second cell on his third turn. After this, Bob can follow the strategy in the claim (with the interval being the fifth to rightmost cells), and since the fourth cell always remains empty, a draw cannot happen, hence Bob wins by using this strategy. $\blacksquare$

Rename the first player to Kris and the second player to Spamton. Claim: Spamton never loses. Proof. Let Kris choses an arbitrary location. Then let Spamton place in one of $1$ or $n$. Afterwards, each time Kris chooses a number, it creates a new interval between two Kris-chosen numbers, in which Spamton can choose the first number in the interval. Repeating this means that Spamton can always move after Kris moves. $\blacksquare$ This immediately gives a win for Spamton on all $2k + 1 \ge 3$. Claim: Spamton can win for $n \ge 8$. Proof. Once again, we WLOG assume that Spamton chooses $n$ on the second turn. If Kris creates an interval with size more than $1$, then first the first turn Spamton can choose the second number in that interval. Repeating the earlier strategy then guarentees a win as the first element in the interval is always empty. Else, suppose that Kris creates an interval with size $2$. Let $a$ be the element in the interval. Then Spamton chooses the number $a_1$ either two before the interval or two after the interval. WLOG assume that $a$ is two after, or flip the entire row. From then, whenever Kris creates a new interval, if this interval already contains $a_1$, then Spamton chooses $a$. Else, Spamton chooses the first element of that interval. Once again, this guarentees a loss. $\blacksquare$ Claim: This is a draw for $n = 1, 2, 4, 6$ Proof. $n = 1$ and $2$ follows immediately. For $n = 4, 6$, it remains to show that Kris can guarentee choosing at least $\frac{n}{2}$ numbers. For $n = 4$, this is immediate by choosing $1$ on the first turn. For $n = 6$, Kris first chooses $1$. If Spamton chooses $6$, then Kris can choose $3$, then $5$. Else, Kris can then choose $6$ for the second turn, and still have something to choose for the third turn. $\blacksquare$

Call the players Mario and Luigi. The answer is that the game is draw for $n = 1, 2, 4, 6$ and otherwise won by Luigi. We can check $n. = 1, 2, 4, 6$ manually. Claim: Luigi wins for all odd $n$. Proof. Just let Luigi mirror Mario's moves. A draw is impossible as for that Mario would have to take $\frac{n+1}{2}$ tiles and the only way to do this is to take every other tile, which is prevented by Luigi's strategy. $\square$ Claim: Luigi wins for even $n > 6$. Proof. Assume that Luigi picks a number of the same parity as Mario on his first move. Then for every following move, say on the $k^{\text{th}}$ turn, Mario has played $k$ blocks. This partitions the numbers into $k$ different sections. Then there exists some subset of numbers between two of Mario's blocks that does not contain one of Luigi's blocks. Let Luigi play here. It is clear then that as long as Mario may move, Luigi may move. Also we find that a draw is impossible as for a draw to occur Mario needs to take all blocks of one parity, which Luigi has prevented. $\square$

oops did not solve (again) what am i doing unfortunately i did not really think of the main claim which is sad zzzzzzzzzzzzzzzzzzzzzzz The point is that on $n$ odd, it's not hard to see $B$ will win every time. The point, then, (which I noticed and never actually pursued) is that $B$ can force a non-draw. In fact, the crux of the problem is trying to make $B$ win by forcing a non-draw and making sure $B$ can always move after $A$ moves. (This formulated in my mind, I cannot believe how stupid I am; it should have been obvious to find ways to ensure $B$ can always move after $A$) Anyway, we suppose that $A$ has moved $k$ times, and we need to show that the $k-1$ moves by $B$ don't steal all of the available spots. It really depends on the number of endpoints which $A$ takes; it only fails if $A$ takes both endpoints, so we can just have $B$ take one at the start. Then it's trivial. bruh.

Condition 3 is silly Reinterpret the problem as writing the letters $A$ or $B$ inside a $1\times n$ grid. For a given position, define the score of player $A$ to be the number of empty squares not adjacent to any $A$ plus the number of empty squares between two $B$s, and define the score of player $B$ similarly. The difference of the two scores is equal to the number of empty squares adjacent to a $B$ plus the number of empty squares between two $B$s minus the number of empty squares adjacent to an $A$ minus the number of empty squares between two $A$s. This is equal to the number of pairs of adjacent squares with a $B$ and an empty square minus the number of pairs of adjacent squares with an $A$ and an empty square. This is equal to twice the difference of the number of $B$s and the $A$s minus the difference between the number of $B$s and $A$s on the edge. If $n=1$, the game ends in a draw. Otherwise, we claim $B$ never loses by picking either $1$ or $n$ on the first turn. During $B$'s turn, the difference between $B$'s score and $A$'s score is $2$ plus the difference between the number of $B$s and $A$s on the edge. Since there is at least one $B$ on the edge, $B$'s score is at least two plus $A$'s score. Each player's score is nonnegative, and if a player's score is positive, then there must exist a square that the player can play in. Therefore, $B$ always has a move, so $B$ cannot lose. If the game ends in a draw, then the game must end after $B$'s move, so $n$ is even. If $n\geq8$ and $n$ is even, then assume without loss of generality $B$'s first move is $1$. If $A$ does not pick $n$ on the first two moves, $B$ wins by picking $n$ because $B$'s score will always be $4$ more than $A$'s score. Otherwise, suppose $A$ picks $n$ and $x$ on the first two turns. If $x\neq n-2$, then $B$ picks $n-2$ and wins since $n-1$ can never be picked. Otherwise, $B$ picks $x-2=n-4$ since $n-3$ can never be picked. Therefore, if $n\neq1,2,4,6$, $B$ wins. If $n=2$, the game is clearly a draw. If $n=4$, $A$ draws by picking $1$ then either $3$ or $4$ on the next turn. If $n=6$, $A$ draws by picking $1$. Then, $B$ is forced to pick $6$ otherwise $A$ wins by picking $6$. After, $A$ picks $3$, then $5$ is available on the next turn. Therefore, the game is a draw if $n=1,2,4,6$ and $B$ wins otherwise.

I claim that $A$ draws for $1,2,4,6$ and for any other $n$ we have that $B$ manages to win. First if $n=1,2$ it's obvious, if $n=3$ then trivially $A$ loses, if $n=4$ then $A$ picks $1$ and then $3$ (or $4$ if $3$ is chosen), with best play this is a draw, if $n=6$ then just check all possibilities to check that $B$ can only achieve a draw, and for $n=5$ same thing, except that here $B$ manages to win because for whatever $A$ picked, $B$ picks something not consecutive to it which leaves $A$ with a forced move (either forced to pick one thing or one of two), in either case $B$ picks the closest to $A$'s pick and wins. Now we claim that for any $n \ge 7$ we can make $B$ win forcefully, first lets deal with $n$ odd, for whatever $A$ picks $B$ picks $1$ or $n$ depending on which one is the most far away from $A$'s pick, WLOG it's $n$, now the strategy will be following $A$ in a coordinated say, first if $A$ picked $\ell$ then $B$ has pick $\ell-1$ (in either this turn or in his previous we take in count the $\ell \ne 1$), now if $A$ plays something above $\ell$ then $B$ plays the consecutive to the left, this is always possible as if it weren't it means that either there is two picks of $A$ that are consecutive or that that $A$ pick must've already existed before, both can't happen so in fact $B$ always has a move to play after a move from $A$ so it cannot lose, and also $A$ has to do one more move than $B$ so it will eventually run out of moves thus no draw happens and $B$ wins here. Now if $n$ is even, note that the above strategy works as well except in the case where $A$ picks $1,3, \cdots n-1$, so after $B$ chooses $n$ (WLOG $A$ plays something at most half of $n$ by symmetry), then $B$ in the 2nd move after $A$ placed something, has to pick an odd number, if $A$ picks something even at some point then do the normal strat to win, else if $A$ decided to pick all odds, after $A$'s second pick, if it is $n-1$ then $B$ will pick $\ell+2$ (which is odd) for whatever the first pick $\ell$ of $A$, and then do the strategy of picking consecutive right of whatever $A$ picks next, notice that $B$ still always has a move and also avoided $A$ picking all odds so $B$ wins, now if $A$'s pick was an odd not equal to $n-1$ then $B$ will pick $n-1$ and then for whatever $A$ third move is we can always do the strategy of picking consecutive left again as there is no teo consecutive $A$'s and thus $B$ wins as well in this case. Therefore all cases are exhausted thus we are done .