KöMaL 2025 A908

Let $n \geq 2$ be an integer. Little Red Riding Hood and the wolf are playing a game in which the numbers $\{1, 2, \ldots, n\}$ are being colored red and blue. In each round, Little Red Riding Hood selects a pair $(i, j)$ such that $1 \leq i < j \leq n$, and both $i$ and $j$ are still uncolored. Then the wolf colors one of them blue and the other red. The game ends when all but at most one of the numbers from $\{1, 2, \ldots, n\}$ have been colored. Show that there exists a constant $c>0$ independent of $n$, and a strategy for Little Red Riding Hood such that she can ensure that at some point during the game, there exist numbers $1 \leq a \leq b \leq n$ such that the set $\{a, a+1, \ldots, b\}$ contains at least $c \cdot \sqrt[3]{n}$ more red numbers than blue numbers.