Minivan and Megavan play a game. For a positive integer $n$, Minivan selects a sequence of integers $a_1,a_2,\ldots,a_n$. An \textit{operation} on $a_1,a_2,\ldots,a_n$ means selecting an $a_i$ and increasing it by $1$. Minivan and Megavan take turns, with Minivan going first. On Minivan's turn, he performs at most $2025$ operations, and he may choose the same integer repeatedly. On Megavan's turn, he performs exactly $1$ operation instead. Megavan wins if at any point in the game, including in the middle of Minivan's operations, two numbers in the sequence are equal. (Proposed by Ho Janson)
Problem
Source: JOM 2025 P3
Tags: combinatorics
GreekIdiot
26.01.2025 21:24
fix the latex
CatinoBarbaraCombinatoric
26.01.2025 22:14
I think the problem asks for which $n$ Minivan can garanties to win in a finite number of move. For $n=2026$ Megavan chooses $(a_1,a_2,...,a_n)=(0,1,3,...,2n-3)$ and increases every number from $a_2$ to $a_2026$ of $1$. So there are numbers $(0,2,4,...,2n-2)$. After every move of Minivan, Megavan increases all the other numbers. So the differnce between $2$ consecutive numbers is always $2$. The same strategy works for every $n<2026$ because Megavan can do less than $2025$ moves. For $n>2026$ Minivan has a winning strategy. WLOG assume $a_1<a_2<...<a_n$. And assume for contradiction that Megavan has a strategy such that this inequalities are always verified At every Minivan's move he increases $a_1$. Consider the quantity $X=\sum_{i=2}^{n}a_i-a_1$. For the assumption that Megavan has a winning strategy, $X>0$ at every moment. After that Minivan increases $a_1$, $X$ decreases by $n-1$. At every Megavan's move $X$ increases by at most $2025$. After $2$ consecutive moves of Megavan and Minivan $X$ has decreased by at least $n-1-2025\geq1$. Contradiction because $X>0$ after every step.