Problem A. 908. (May 2025)

A. 908. Let \(\displaystyle n \geq 2\) be an integer. Little Red Riding Hood and the wolf are playing a game in which the numbers \(\displaystyle \{1, 2, \ldots, n\}\) are being colored red and blue. In each round, Little Red Riding Hood selects a pair \(\displaystyle (i, j)\) such that \(\displaystyle 1 \leq i < j \leq n\), and both \(\displaystyle i\) and \(\displaystyle 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 \(\displaystyle \{1, 2, \ldots, n\}\) have been colored. Show that there exists a constant \(\displaystyle c>0\) independent of \(\displaystyle n\), and a strategy for Little Red Riding Hood such that she can ensure that at some point during the game, there exist numbers \(\displaystyle 1 \leq a \leq b \leq n\) such that the set \(\displaystyle \{a, a+1, \ldots, b\}\) contains at least \(\displaystyle c \cdot \sqrt[3]{n}\) more red numbers than blue numbers.

Proposed by: Dömötör Pálvölgyi, Budapest

(7 pont)

Deadline expired on June 10, 2025.

In our solution we will use notation \(\displaystyle [a,b]=\{a,a+1,...,b\}\) for any integers \(\displaystyle a\le b\), and we will refer to these sets as intervals. First we will solve the problem for \(\displaystyle n=k^3\), where \(\displaystyle k\ge 2\). We claim that \(\displaystyle c=1/8\) will work in this case. This is not a sharp result, instead we will focus on being less technical in our estimations.

Let's divide \(\displaystyle [1,n]\) into \(\displaystyle k\) intervals of equal length: \(\displaystyle I_1=[1,k^2]\), \(\displaystyle I_2=[k^2+1,2k^2]\),..., \(\displaystyle I_k=[(k-1)k^2+1,k^3]\). Little Red Riding Hood will only focus on the intervals, she can choose the two numbers arbitrarily from the two chosen intervals. She will count the difference of the number of the red and the blue points in each interval \(\displaystyle I_j\) (the difference being negative, if there are more blue points). If she finds two intervals with the same difference, and there are uncolored points in both of them, she will pick a point from each. At the first moment when there will be no such intervals, she will stop, and we claim that at this moment there will be appropriate \(\displaystyle a\le b\) values.

To prove this, let \(\displaystyle f_\ell(j)\) denote the difference of the red and blue points after \(\displaystyle \ell\) steps in interval \(\displaystyle I_j\). We will prove the following for every value of \(\displaystyle \ell\) until Piroska stops (we define \(\displaystyle f_0(j)\) as 0 for \(\displaystyle j=1,2,...k\)):

\(\displaystyle \sum_{j=1}^k f_{\ell}(j)^2=\sum_{j=1}^{k}f_{\ell-1}(j)^2+2. \)

in step \(\displaystyle \ell\) she will pick points from intervals \(\displaystyle I_i\) and \(\displaystyle I_j\) satisfying \(\displaystyle f_\ell(i)=f_\ell(j)\). If \(\displaystyle x\) denotes their value, after the Wolf's move one of them will be \(\displaystyle x+1\) and the other will be \(\displaystyle x-1\). Now identity \(\displaystyle (x-1)^2+(x+1)^2=2x^2+2\) proves the statement above. We will need the following conssequence of this statement which is an easy consequence of the above:

\(\displaystyle \sum_{j=1}^k f_{\ell}(j)^2\ge 2\ell. \)

Now suppose the Little Red Riding Hood stops after \(\displaystyle t\) steps and she hasn't won the game. Clearly this implies that \(\displaystyle f_t(j)\le k/8\) in every interval \(\displaystyle I_j\). Note that \(\displaystyle f_t(j)\ge -k/4\) is also true, since the number of blue and red points are the same after each move of the Wolf, therefore \(\displaystyle f_t(1)+...+f_t(k)=0\), and thus \(\displaystyle f_t(j)<k/4\) implies that in interval \(\displaystyle I_1\cup I_2\cup...\cup I_{j-1}\) or \(\displaystyle I_{j+1}\cup I_{j+2}\cup...\cup I_k\) the number of red points is at \(\displaystyle k/8\) more than the number of blue points, contradicting our assumption the Little Red Riding Hood hasn't won the game. Therefore the number of different values is \(\displaystyle k/4+k/8<k/2\).

Let's call interval \(\displaystyle I_j\) full, if every number is colored in it, otherwise let's call it useable. Since Little Red Riding Hood has stopped after \(\displaystyle t\) steps, it means that less then \(\displaystyle k/2\) can be useable, otherwise there would be two useable intervals with the same value of \(\displaystyle f_t\) (since \(\displaystyle f_t\) has less than \(\displaystyle k/2\) different values by the previous paragraph). So the number of full intervals is more than \(\displaystyle k/2\), also implying that more than the half of all the points are colored. So \(\displaystyle t\geq n/4\), and thus

\(\displaystyle \sum_{j=1}^k f_t(j)^2\geq\frac{n}2. \)

However, we have also seen that

\(\displaystyle \sum_{j=1}^k f_t(j)^2\le k\cdot \left(\frac{k}{4}\right)^2=\frac{n}{16}, \)

which is a contradiction.

Now let's prove the general case, when \(\displaystyle n\) is not a perfect cube. Let \(\displaystyle n\ge 8\), and let \(\displaystyle k\) denote the greatest positive integer satisfying \(\displaystyle k^3\le n\) (clearly, \(\displaystyle k\ge 2\)). Little Red Riding Hood can guarantee at least \(\displaystyle k/8\) more red points then blue only restricting herself to inter \(\displaystyle [1,k^3]\subseteq [1,n]\). However, \(\displaystyle n<(k+1)^3<8k^3\), therefore

\(\displaystyle \frac{1}{16}\sqrt[3]{n}\le \frac{k}{8}, \)

so with \(\displaystyle c/1/16\) the statement is true for every \(\displaystyle n\ge 8\).

Finally, \(\displaystyle c=1/16\) also works for \(\displaystyle n\le 7\): in these cases, \(\displaystyle \sqrt[3]{n}/16<1\), therefore after choosing an interval with a single red point after the first step will show that Little Red Riding Hood has won the game.

Statistics:

4 students sent a solution.
7 points:	Bodor Mátyás, Tianyue DAI, Varga Boldizsár, Xiaoyi Mo.

Problems in Mathematics of KöMaL, May 2025