Wisely case bash considering $n(mod 8)$ , $n=5,7$ and all $n\geq 8 $

N odd u get ez n even consider n - 1 for 4 divided n for n = 2 mid 4 consider n - 3

solved in contest

Answer is all n except 2,3,4,6, (now assume n>=5) construction : 1,2....,n-2,n-1,n -> 1,2.....n-1,n-1 -> 1,2,.....n-2,n-2, n-1 -> ...... -> 1,2,4,n-1 -> 1,3,n-1: n odd then 1,3,n-1 -> 2, n-1 -> (n+1)/2 except n=3 for which 2=n-1 n = 4k+4 then 1,3,n-1 -> (n+2)/2, 1 -> (n+4)/4 n=4k+2 then 1,3,n-1 -> n/2, 3 -> (n+6)/4 except n=6 for which n/2=3

Alright I guess i'll post a full solution which I had in contest, with some motivation. You see that $5$ works, and after a little work, you can come up with a strategy for $7$ and $9$ as well, which quickly gives all odds. After that, the problem just falls apart. Suppose, we have $1, \dots, 2k - 1$. Take the average of $1$ and $3$, giving $2, 2, 4, 5, \dots, 2k - 1$. Take the average of $2$ and $4$, giving $2, 3, 5, 6, \dots, 2k - 1$. Take the average of $3$ and $5$, giving $2, 4, 6, 7, \dots, 2k - 1$. Essentially, we can keep taking the average of the second and third terms over and over again, which eventually yields $2, 2k - 3, 2k - 1$. Take the average of the second and third terms, giving $2, 2k - 2$ from which we get $k$. and we have that odds work, if they're more than $3$. Now, for $4 \mid n$, say we have $1, \dots, 4k - 1, 4k$. We can just convert $1, \dots, 4k - 1$ to $2k$, and we have $2k, 4k$ which gets converted to $3k$ and we're done. For $n \equiv 2 \mod{4}$, let $n = 4k + 2$. We have $1, \dots, 4k - 1, 4k, 4k + 1, 4k + 2$. Convert $1, \dots, 4k - 1$ to $2k$, we have $2k, 4k, 4k + 1, 4k + 2$. Now all we have to do is take cases. If $k \equiv 3\mod{4}$, take the average of $2k, 4k + 2$, we have $3k + 1, 4k, 4k + 1$. Take the average of $3k + 1$ and $4k$, which is clearly odd, so we're done. If $k \equiv 1\mod{4}$, take the average of $2k$ and $4k$, we get $3k, 4k + 1, 4k + 2$. Take the average of $3k, 4k + 1$, which is clearly even, and we're done. Reciprocate for $k \equiv 2, 0 \mod{4}$, and we get that all $n \geq 7$ work. $n = 1, 2, 3, 4, 6$ is left as an excercise to the reader

hover for tip I did not think I would post but since this is INMO, this is an exception! Although my answer is similar to that of alexanderhamilton124, posting for storage.

My problem I was just trying to come up with a simple game and see where something interesting happens. In this game, it was clear that the amount of freedom is so high that almost everything should work... After doing some incredibly painful work, I was indeed able to show that everything but $2,3,4,$ and $6$ are winning for Alice. I mostly thought that the problem is not too interesting but could be a useful practice problem to see if students can actually do some painful computation and work. I will not post my original solutions here and let them eventually appear... Then Tejaswi found a beautiful and short solution to the problem which made me much happier with the problem! Here's that proof (written up by me so might have errors) for showing that everything with the possible exception of $2,3,4,$ and $6$ are winning for Alice: For any $n\ge 2$, we have \[[n-1]\cup \{n+1\}\mapsto [n-2]\cup \{n\},\]thus, by repeating the above, for any $n\ge 3$, we have \[[n-2]\cup\{n\}\longmapsto \{2\}.\]Thus, for any $n\ge 5$, we have \[[n]=\left([n-3]\cup \{n-1\}\right)\cup\{n-2,n\}\longmapsto \{2,n-2,n\}\] Now, if $n\ne 6$, then these $3$ numbers are not in an AP. Now, if 1. $\mathbf{n}$ is odd: $\{2,n-2,n\}\mapsto \{2,n-1\}$ and both the numbers are even and Alice ends up with exactly one number for all odd $n\ge 5$. 2. $\mathbf{n}$ is even: Atleast one of $n$ and $n+2$ is divisible by $4$. Thus, Alice can make a move such that both the numbers on the board are even and can end up with one final number as long as $n-2\ne \frac{n+2}{2}$. This only happens when $n=6$. Thus, Alice can end up with exactly one number for all even $n\ge 8$. Remark. I do think this problem is significantly more challenging and work than this solution suggests as it is very natural to go down much more convoluted paths as I did...

Got cooked with this one but as alexander says, the motivation is quite direct. However this still requires some ingenuity . Nice problem . Computation is horrible for this

I got cooked by the computation on this one and p1

Solved in contest Solution - Case bash shows that $2,3,4,6$ do not work, $5$ easily works. We now have for $n=7$ - $(1,2,3,4,5,6,7) \rightarrow (1,3,3,5,6,7) \rightarrow (1,3,4,6,7) \rightarrow (1,3,5,7) \rightarrow (2,5,7) \rightarrow (2,6) \rightarrow (4)$ For $n=9$, we get $(1,2,3,4,5,6,7,8,9) \rightarrow (1,5,9) \rightarrow (3,9) \rightarrow (6)$ Consider $7$ and $9$ as base cases. Notice that both leave $n-3$. We now induct for all odd numbers - assume we can get $(n-3)$ from $(1,2,...,n)$. Then, for $n+4$, we have $(1,2,3,...,n+4) \rightarrow (n-3,n+1,n+2,n+3,n+4) \rightarrow (n-3,n+1,n+3,n+3) \rightarrow (n-3,n+2,n+3) \rightarrow (n,n+2) \rightarrow (n+1)$ completing the induction. So, all odd numbers $\geq 7$ work. For any even number $2k>7$, we have $(1,2,...,2k-1,2k) \rightarrow (2k-4,2k) \rightarrow (2k-2)$ which finishes. Remarks - A pretty simple and nice problem, the only reason it can be called hard is that its counterintuitive. During contest I had 4 wrong ideas (only $5$ works, only $5k$ works, only $5^k$ works, only odd works), but getting constructions for $n=7,8,9,10,12,13$ gave me the idea.

Let $a_n$ be the last number left at the end for all $n$ defined. **Claim 1:** $a_n = n - 2$ is true for $n = 5, 9, 10$. **Proof:** For $n = 5$ (numbers with $\dot{x}$ are selected): $$1\dot{,} 2, 3\dot{,} 4, 5 \to 2, 2\dot{,} 4\dot{,} 5 \to 2, 3\dot{,} 5\dot{} \to 2\dot{,} 4\dot{} \to 3$$ For $n = 9$: $$1, 2, 3\dot{,} 4, 5\dot{,} 6, 7, 8, 9 \to 1, 2\dot{,} 4\dot{,} 4, 6, 7, 8, 9 \to 1\dot{,} 3, 4, 6, 7\dot{,} 8, 9$$$$\to 3, 4, 4\dot{,} 6\dot{,} 8, 9 \to 3\dot{,} 4, 5\dot{,} 8, 9 \to 4, 4\dot{,} 8\dot{,} 9 \to 4\dot{,} 6\dot{,} 9 \to 5\dot{,} 9\dot{} \to 7$$ For $n = 10$: $$1, 2\dot{,} 3, 4\dot{,} 5, 6, 7, 8, 9, 10 \to 1, 3, 3\dot{,} 5, 6, 7, 9\dot{,} 10 \to 1, 3\dot{,} 5, 6, 6, 7\dot{,} 8, 10$$$$\to 1\dot{,} 5\dot{,} 5, 6, 6, 8, 10 \to 3\dot{,} 5\dot{,} 6, 6, 8, 10 \to 4\dot{,} 6\dot{,} 6, 8, 10 \to 5, 6\dot{,} 8\dot{,} 10 \to 5\dot{,} 7\dot{,} 10 \to 6\dot{,} 10\dot{} \to 8$$ **Claim 2:** If $a_n = n - 2$ is true for an integer $k$, then it is also true for $k + 3$. **Proof:** For $n = k$: $$a_{k+3} = (1\dot{,} 2\dot{,} \dots, k\dot{}), k+1, k+2, k+3 \to (k-2)\dot{}, k+1, (k+2)\dot{}, k+3 \to k, (k+1)\dot{}, (k+3)\dot{}$$$$\to k\dot{}, (k+2)\dot{} \to k+1 = (k+3) - 2$$ Now, if we set $k = 5$, then this is true for $k = 8$. If we put $k = 8$, then it becomes true for $k = 11$. Thus, by repeated induction, it is true for all $k$ which are $2 \pmod{3}$ and $\geq 5$. By similar logic, it is true for all $k$ which are $0 \pmod{3}$ and $\geq 9$, as well as true for all $k$ which are $1 \pmod{3}$ and $\geq 10$. Thus, we have proved that it is true for all integers in the sets: $$\{5\} \cup \{8, 9, 10, \dots, \infty\}$$ **Claim 3:** $a_7 = 4$ and $a_2, a_3, a_4, a_6$ are not defined. For $n = 7$: $$1\dot{,} 2, 3, 4, 5\dot{,} 6, 7 \to 2, 3\dot{,} 3, 4, 6, 7\dot{} \to 2, 3\dot{,} 4, 5\dot{,} 6 \to 2\dot{,} 4\dot{,} 4, 6 \to 3, 4\dot{,} 6\dot{} \to 3\dot{,} 5\dot{} \to 4$$ For $n = 2$: $$1, 2 \quad \text{cannot make any progress.}$$ For $n = 3$: $$1\dot{,} 2, 3\dot{} \to 2, 2 \quad \text{does not make any progress.}$$ For $n = 4$: $$1\dot{,} 2, 3\dot{,} 4 \to 2, 2\dot{,} 4\dot{} \to 2, 3 \quad \text{does not make any progress.}$$$$1, 2\dot{,} 3, 4\dot{} \to 1\dot{,} 3\dot{,} 3 \to 2, 3 \quad \text{does not make any progress.}$$ For $n = 6$, checking all cases, none work. Hence, all natural numbers $\geq 2$ are possible except $2, 3, 4, 6$.

Notice that: (.....((((((1+3)/2)+4)/2)+5)/2).....n)/2 = n-1 for all n>3. (This can easily be proved using induction) Now lets consider the case for an odd n >3, The set: {1,2,3...,n} can be reduced to {2,n-1} by using the above algorithm. This can further be reduced to an integer. Now consider an n that is divisible by 4 and greater than 4 the set: {1,2,3....,n} can be reduced to {2,n-2,n} by using the algorithm which can further be reduced to {n/2,n}. Now since both n and n/2 are even, this can be reduced to a singular integer. For the last case, consider an n that is divisible by 2 but not by 4. Also assume this n to be greater than 7. The set: {1,2,3,4...,n} can now be reduced to {2,n-5,n-3,n-2,n-1,n} by the algorithm which can further be reduced to an integer by the following steps: {2,n-5,n-3,(n-2),n-1,(n)} --- {2,(n-5),n-3,(n-1)n-1} --- {2,n-3,(n-3),(n-1)} --- {2,n-3,n-2} ---{n/2,n-3} Now since n/2 and n-3 both are odd, this set is further reducible to an integer. By this we have proved that for every odd n > 4 and every even n >7 is reducible. The remaining numbers {2,3,4,6} can be solved separately to yield no reducible solutions.

Cooks books. This is a rather nice problem. Reminded me a lot of 21RMM4. The answer is all $n\ge 2$ excluding $n=2,3,4$ and $6$. Obviously $n=2$ fails as we can't even do any moves at all. When $n=3$ the only possible move is $(1,3)$ after which we have no possible moves. Again, when $n=4$ the only possible move is $(1,3)$ or $(2,4)$ which reduce the board to $2,2,4$ and $1,3,3$ respectively. After this the only possible moves are $(2,4)$ and $(1,3)$ respectively, after which we cannot do any more moves. When $n=6$ the situation is a bit more involved. The following is the tree of all possible move sequences, all of which end in dead ends.

Now we provide constructions for all $n$ which do work. Case 1 : $n \equiv 2 \pmod{3}$. For $n=5$ follow the sequence, \[1,2,3,4,5 \to 2,2,4,5 \to 2,3,5 \to 2,4 \to 3\]Now, say $[3k+2]$ goes down to $3k$ for some $k\ge 1$. Then for $3k+5$ note, \[1,2,\dots , 3k+2 , 3k+3 , 3k+4 , 3k+5 \to 3k , 3k+3 , 3k+4 , 3k+5 \to 3k +2 , 3k+4 \to 3(k+1) \]which completes the induction. Case 2 : $n\equiv 1 \pmod{3}$. For $n= 7$, follow the sequence, \[1,2,3,4,5,6,7 \to 2,3,5,6,7 \to 3,4,5,7 \to 3,4,6 \to 3,5 \to 4\]For $n>7$ let $n=3k+4$ for some $k > 1$. Then, \[[3k-1] , 3k , 3k+1 , 3k+2 , 3k+3 , 3k+4 \to 3k-3 , 3k , 3k+1 , 3k+2 , 3k+3 , 3k+4 \to 3k-1 , 3k , 3k+2 , 3k+3 ,3k+4 \to 3k , 3k+1 , 3k+3 \to 3k , 3k+2 \to 3k+1\] Case 3 : For $n>6$ , let $n=3k+3$ for some $k >1$. Then, \[[3k-2] , 3k-1 , 3k ,3k+1, 3k+2 ,3k+3 \to 3k-5 , 3k-1, 3k , 3k+1, 3k+2 , 3k+3 \to 3k -2 , 3k-1 , 3k , 3k+2 , 3k+3 \to 3k -1 , 3k-1 , 3k+2 , 3k+3 \to 3k-1 , 3k+2 , 3k+2 \to 3k , 3k+2 \to 3k+1\]which finishes the problem.

This problem is pretty , nice.

Oops.