Problem 1867

Denote by $R(n)$ the number of red numbers in $\{1, 2, \dots, n\}$, i.e., $R(n) = n r(n)$. Similarly, denote by $B(n)$ and $b(n) = B(n)/n$ the number and proportion of blue numbers in $\{1, 2, \dots, n\}$, respectively. Notice that $B(n) + R(n) = n$ and $b(n) + r(n) = 1$. Therefore, the statement of the problem does not change after swapping the colors.

Arguing indirectly, for every $a \in \{1, 2, \dots, p-1\}$ choose some positive integer $n_a$ such that $r(n_a) = a/p$ and, hence, $R(n_a) = a n_a / p$. Clearly, $p \mid n_a$, so that $n_a = p m_a$ for some positive integer $m_a$, and $R(n_a) = a m_a$. Without loss of generality, we assume that $m_1 < m_{p-1}$, as otherwise one may swap the colors. Notice that
$$m_a \le \frac{N}{p} < \frac{p^2-1}{4} \quad \text{for all } a=1,2,\dots,p-1.$$
The solution is based on a repeated application of the following simple observation.

Claim. Assume that $m_a < m_b$ for some $a, b \in \{1, 2, \dots, p-1\}$. Then
$$m_b \ge \frac{a}{b} m_a \quad \text{and} \quad m_b \ge \frac{p-a}{p-b} m_a.$$
Proof. The first inequality follows from $b m_b = R(n_b) \ge R(n_a) = a m_a$. The second inequality is obtained by swapping colors.

Let $q = (p-1)/2$. We distinguish two cases.

Case 1: All $q$ numbers $m_1, m_2, \dots, m_q$ are smaller than $m_{p-1}$.
Let $m_a$ be the maximal number among $m_1, m_2, \dots, m_q$; then $m_a \ge q \ge a$. Applying the Claim, we get
$$m_{p-1} \ge \frac{p-a}{p-(p-1)} m_a \ge (p-q)q = \frac{p^2-1}{4}$$
which contradicts (1).

Case 2: There exists $k \le q$ such that $m_k > m_{p-1}$. Choose $k$ to be the smallest index satisfying $m_k > m_{p-1}$; by our assumptions, we have $1 < k \le q < p-1$.
Let $m_a$ be the maximal number among $m_1, m_2, \dots, m_{k-1}$; then $a \le k-1 \le m_a < m_{p-1}$. Applying the Claim, we get
$$\begin{align*} m_k &\ge \frac{p-1}{k} m_{p-1} \ge \frac{p-1}{k} \cdot \frac{p-a}{p-(p-1)} m_a \\ &\ge \frac{p-1}{k} \cdot (p-k+1)(k-1) \\ &\ge \frac{k-1}{k} \cdot (p-1)(p-q) \\ &\ge \frac{1}{2} \cdot \frac{p^2-1}{2} \end{align*}$$
which contradicts (1) again. $\square$