Let $\alpha, \beta$ be two rational numbers strictly between 0 and 1. Alice and Bob play a game. At the start of the game, Alice chooses a positive integer $n$. Knowing that, Bob then chooses a positive integer $T$. They then do the following for $T$ rounds: at the $i$th round, Bob chooses a set $X_i$ of $n$ positive integers that form a complete residue system modulo $n$. Then Alice chooses a subset $Y_i$ of $X_i$ such that the sum of elements in $Y_i$ is at most $\alpha$ times the sum of elements in $X_i$. After the $T$ rounds, Alice wins if it is possible to pick an integer $s$ between 0 and $n-1$ such that there are at least $\beta T$ positive integers among the elements in $Y_1, Y_2, . . . , Y_T$ (counted with multiplicities) that are equal to $s \pmod n$, and Bob wins otherwise. Find all pairs $(\alpha, \beta)$ of rational numbers strictly between 0 and 1 such that Alice has a winning strategy. Proposed by Hans
Problem
Source: 2024 IRN-SGP-TWN Friendly Math Competition P6
Tags: game
02.08.2024 20:29
Very intimidating statement, but the solution is kinda cute. Solved with Rohan and Atul. Alice has a winning strategy iff $\boxed{\alpha \geq \beta}$. First the easy part: assume $\alpha \geq \beta$. Alice chooses $n$ such that $\alpha n, \beta n$ are both integers. Now, for any $X_i$ chosen by Bob, Alice choses the $\alpha n$ smallest elements as $Y_i$. Clearly by pigeonhole principle, some residue occurs at least $\alpha T \geq \beta T$ times among $Y_1, \dots, Y_T$, so ALice wins! Now assume $\beta>\alpha$. Choose a rational number $\lambda=1+\varepsilon>1$ such that $\lambda^\beta>\alpha \lambda + (1-\alpha)$. This can be done because $(1+\varepsilon)^\beta \approx 1+\beta \varepsilon > 1+ \alpha \varepsilon$ for small $\varepsilon$. Suppose $t>0$ is such that $\lambda^\beta>(\alpha \lambda + (1-\alpha))(1+t)$. We give a strategy for Bob. After Alice chooses $n$, Bob chooses a large enough $T$ such that $\left(\frac{\lambda^\beta}{(\alpha \lambda + (1-\alpha))(1+t)}\right)^T>n$. For the first step, Bob chooses the set $X_1=\{1,2, \dots, n\}$. For the subsequent turns, Bob gives a weighting to each residue modulo $n$ and chooses his set based on these weightings. Suppose $m$ rounds have been played so far, and residue $j$ occurs $c_j$ times among $Y_1, \dots, Y_m$. Then the weight assigned to residue $j$ is $\lambda^{c_j}$. Bob's strategy is to represent each residue with a positive integer approximately proportional to its weight. More precisely, Bob first chooses a positive integer $A>\frac{n}{t}$ such $A \lambda^{c_j}$ is an integer for each $j$. Then he chooses integers $b_j$ in the interval $[0,n-1]$ such that $A \lambda^{c_j} + b_j$ form a complete residue system modulo $n$, and presents this set as $X_{m+1}$. Define the score $S_m$ as the sum of weights after round $m$. Let us see how the score changes between rounds. Weight of every residue gets multiplied by either $\lambda$ or $1$ depending on whether Alice chose it or not in $Y_{m+1}$. Let $T_1$ be sum of elements in $X_{m+1}$, and let $T_0$ be sum of elements in $Y_{m+1}$. Then $T_0 \leq \alpha T_1$, which implies $T_1-T_0+\lambda T_0 \leq (\alpha \lambda + (1-\alpha))T_1$. Now, $T_1-T_0+\lambda T_0$ is just $AS_{m+1}$ plus some terms of the form $b_j$ or $\lambda b_j$, so it is at least $AS_{m+1}$. On the other hand, $T_1$ is just $AS_m$ plus sum of all the $b_j$, so it is at most $AS_m+n^2$. Hence, dividing by $A$, we get $$S_{m+1} \leq (\alpha \lambda + (1-\alpha))\left(S_m+\frac{n^2}{A}\right)<(\alpha \lambda + (1-\alpha))(1+t)S_m.$$The last inequality holds because $S_m \geq n$ (since it is sum of $n$ weights each of which are at least $1$), and $\frac{n}{A}<t$. Note that $S_0=n$ since there are no residues initially, so all weights are $\lambda^0=1$. Hence after $T$ rounds, the score is $$S_T \leq (\alpha \lambda + (1-\alpha))^T(1+t)^T S_0 = (\alpha \lambda + (1-\alpha))^T(1+t)^T n < \lambda^{\beta T}.$$Now assume FTSOC some residue occurs at least $\beta T$ times in $Y_1, \dots, Y_T$. Then the weight of that residue is at least $\lambda^{\beta T}$, so $S_T \geq \lambda^{\beta T}$, contradiction!