Problem 1582

To prove the given statement, we will use a combinatorial argument and properties of fractions. Let's break down the problem step by step.

1. Define the Problem and Variables:
Let $p$ be an odd prime, and define $N = \frac{1}{4}(p^3 - p) - 1$. The numbers $1, 2, \ldots, N$ are painted in two colors, red and blue. For any positive integer $n \leq N$, let $r(n)$ be the fraction of integers $\{1, 2, \ldots, n\}$ that are red.

2. Objective:
We need to prove that there exists a positive integer $a \in \{1, 2, \ldots, p-1\}$ such that $r(n) \neq \frac{a}{p}$ for all $n = 1, 2, \ldots, N$.

3. Initial Observations:
Note that $r(n) = \frac{a}{p}$ only if $n = kp$ for some $k \in \mathbb{N}$. This is because $\frac{a}{p}$ is a fraction with denominator $p$, and $n$ must be a multiple of $p$ for $r(n)$ to be exactly $\frac{a}{p}$.

4. Block Division:
Divide the sequence $1, 2, \ldots, N$ into blocks of size $p$. Each block will be of the form $(k-1)p + 1, (k-1)p + 2, \ldots, kp$.

5. Red and Blue Distribution:
Consider the distribution of red and blue numbers within each block. Let $r_i$ be the number of red numbers in the $i$-th block. The fraction $r(n)$ can be written as:
$$r(n) = \frac{\text{number of red numbers in } \{1, 2, \ldots, n\}}{n}$$

6. Contradiction Argument:
Assume for contradiction that for every $a \in \{1, 2, \ldots, p-1\}$, there exists some $n \leq N$ such that $r(n) = \frac{a}{p}$.

7. Summing Red Numbers:
Let $R$ be the total number of red numbers among $1, 2, \ldots, N$. Then:
$$R = \sum_{i=1}^{N} r_i$$
Since $N = \frac{1}{4}(p^3 - p) - 1$, we have:
$$R = \frac{a}{p} \cdot N$$

8. **Bounding $R$:**
Since $R$ must be an integer, and $\frac{a}{p} \cdot N$ must also be an integer, we need to check the divisibility conditions. However, $N$ is not necessarily divisible by $p$, leading to a contradiction.

9. Conclusion:
Therefore, there must exist some $a \in \{1, 2, \ldots, p-1\}$ such that $r(n) \neq \frac{a}{p}$ for all $n = 1, 2, \ldots, N$.

$\blacksquare$