I love this problem

Suppose the opposition that $\forall a\in\{1, 2, \dots, p-1\},\ \exists n\in\{1, 2, \dots, N\}$ s.t. $r(n)=a/p$. Let $n_i$ be the smallest $n$ s.t. $r(n)=i/p$. $\because p\in\mathbb P$ $\therefore n_i\in\{p, 2p, \dots, \frac 14(p^2-2)p\}$ $\because$ switching red and blue will swap $n_i$ and $n_{p-i}$. $\therefore$ WLOG assume that $n_1<n_{p-1}$. For $p>3$, let's have an induction on $k$ to prove that $\forall 1\leq k\leq\frac{p-1}2,\ n_k<n_{p-1}$. Base case $k=1$ has been assumed above. Suppose that $\forall 1\leq k\leq m-1$, $n_k<n_{p-1}$, and $\max_{1\leq i\leq m-1}(n_i)=n_j$. $\Rightarrow n_{p-1}\geq n_j\cdot\frac{1-r(n_j)}{1-r(n_{p-1})}\geq(m-1)p\cdot\frac{1-r(n_{m-1})}{1-r(n_{p-1})}=(m-1)(p-m+1)p$ If $n_m>n_{p-1}$, then $n_m\geq n_{p-1}\cdot\frac{r(n_{p-1})}{r(n_m)}\geq(m-1)(p-m+1)p\cdot\frac{p-1}m$. $\Rightarrow(m-1)(p-m+1)p\cdot\frac{p-1}m\leq\frac14(p^2-2)p$ $\Rightarrow 4(m-1)(p-m+1)(p-1)\leq(p^2-2)m$ $\Rightarrow f(m):=4(p-1)m^2-(3p^2+4p-6)m+4p^2-4\geq 0$, where $2\leq m\leq\frac{p-1}2$. $\because f$ is a quadratic function with leading coefficient $>0$ $\therefore$ the maximum of $f$ is either $f(2)$ or $f(\frac{p-1}2)$ $f(2)=-2(p-2)^2<0,\ f(\frac{p-1}2)=(p-1)(-\frac12p^2+8)<0(\because p\geq 5)$ $\therefore\forall 2\leq m\leq\frac{p-1}2,\ f(m)<0$, which is a contradiction. $\therefore n_m<n_{p-1}$ $\therefore$ by induction, $\forall 1\leq k\leq\frac{p-1}2,\ n_k<n_{p-1}$. Suppose that $\max_{1\leq i\leq\frac{p-1}2}(n_i)=n_j$. $n_{p-1}\geq n_j\cdot\frac{1-r(n_j)}{1-r(n_{p-1})}\geq\frac{p-1}2\cdot p\cdot\frac{1-r(n_{\frac{p-1}2})}{1-r_{p-1}}=N+1$, which is a contradiction. $\therefore$ there exists $a\in\{1, 2, \dots, p-1\}$ s.t. $\forall n\in\{1, 2, \dots, N\},\ r(n)\neq a/p$.

Lemma. Suppose $b_1,b_2,...,b_n$ is a sequence such that $0\leq b_i\leq p$, and for each $1\leq i\leq p-1$ there exists $1\leq m\leq n$ such that $$\frac{b_1+...+b_m}{m}=i$$then $n\geq \frac{p^2-1}{4}$. Proof. Let $c_m=\frac{b_1+...+b_m}{m}$, let $d_i$ be the smallest number such that $c_{d_i}=i$, and reorder $d_1,...,d_{p-1}$ as $y_1<...<y_{p-1}$. Let $c_{y_i}=a_i$ The main idea is that: Claim. Suppose $i<j$. If $a_i<a_j$, then $$y_j>y_i+\lceil\frac{(a_j-a_i)y_i}{p-a_j}\rceil\geq \frac{y_i(p-a_i)}{p-a_j}$$If $a_i>a_j$, then $$y_j>y_i+\lceil\frac{(a_i-a_j)y_i}{a_j}\rceil\geq \frac{y_ia_i}{a_j}$$ Proof. 1. Indeed, let $x=y_j-y_i$ $$xp>\sum_{k=y_i+1}^{y_j}b_k=(y_i+x)a_j-y_ia_i$$from which the conclusion easily follows. The proof of $2$ is similar. $\square$ Now notice that the result of the lemma is unchanged if we replace $b_1,...,b_n$ by $p-b_1,...,p-b_n$. Suppose $a_{f_i}=i$, WLOG assume $f_1<f_{p-1}$. We divide into two cases. Case I: $f_i<f_{p-1}$ for all $1\leq i\leq \frac{p+1}{2}$. Suppose $f_j=\max\{f_1,...,f_{\frac{p+1}{2}}\}$, then obviously $y_{f_j}\geq \frac{p+1}{2}$. Therefore, $$n\geq y_{f_{p-1}}\geq y_{f_j}\frac{p-j-1}{p-(p-1)}\geq \frac{p+1}{2}\cdot \frac{p-1}{2} $$Case II: $f_i>f_{p-1}$ for some $1\leq i\leq \frac{p+1}{2}$ Let $k$ be the largest number such that $f_j<f_{p-1}$ for all $1\leq j\leq k$. Then $y_{f_k}\geq k$, $y_{f_{p-1}}\geq y_{f_k}k(p-k)$ and $y_{f_{k+1}}>\frac{y_{f_{p-1}}(p-1)}{k+1}$, which implies $$n\geq y_{f_{k+1}}\geq\frac{k(p-k)(p-1)}{k+1}$$Let $f(k)=\frac{k(p-k)}{k+1}$, then $$f'(k)=-1+\frac{p+1}{(k+1)^2}$$Therefore, we can see that the minimum of $f$ on the interval $[1,\frac{p-1}{2}]$ is equal to $$\min\{f(1),f(\frac{p-1}{2})\}=\frac{p-1}{2}\geq \frac{p+1}{4}$$hence $$n\geq \frac{(p-1)(p+1)}{4}$$as desired. $\blacksquare$ We now return to the original problem. Indeed, suppose on the contrary that for every integer $a\in\{1,2,...,p-1\}$ there exists $1\leq n\leq N$ with $r(n)=\frac{a}{p}$. Obviously, $p|n$. Hence let $x_i$ be the number of red numbers in the interval $[(i-1)p+1,ip]$. Let $n=\frac{1}{4}(p^2-1)-1$, then for each $1\leq a\leq p-1$ we can find some integer $1\leq m\leq n$ such that $$\frac{x_1+...+x_m}{mp}=\frac{a}{p} $$In other words, the sequence $x_1,...,x_n$ satisfy the condition in the lemma, hence $n\geq \frac{1}{4}(p^2-1)$, contradiction.

To my initial surprise, this is actually an (almost) pure C problem. As explained in the later part of the Solution, the things that can $\textbf{actually swing}$ the average lies at the front of the pack, and no adjustment can be made for the $a/p$ that has yet to be covered. Note that $r(n) = \dfrac{a}{p}$ only if $n = kp$ for some $k \in \mathbb{N}$. Following that, naturally call a sequence of numbers $(k-1)p+1,(k-1)p+2,\ldots,kp$ as the $k^{\text{th}}$ $\color{green} \textbf{\textit{block}}$. To alleviate the pesky appearance of the phrase $r(n)$, we assign the number placeholder $r_1,r_2,\ldots,r_{p-1}$ so that $r(r_ap) = \dfrac{a}{p}$. This is equivalent to saying that each number $a \in \{1,2,\ldots,p-1\}$ is satisfied at the end of the $r_a^{\text{th}}$ block. $\color{green} \rule{6cm}{2pt}$ $\color{green} \diamondsuit$ $ \boxed{\textbf{The Order of the Extremes.}}$ $\color{green} \diamondsuit$ $\color{green} \rule{6cm}{2pt}$ Let there exists a good arrangement so that the numbers $r_1$ until $r_{p-1}$ exist. Now, we can WLOG that $p-1$ appears first; i.e. $r_{p-1} < r_1$. This is because we can flip all switches, so all reds become blues and vice versa. This will cause the old config's $r(kp) = \dfrac{a}{p}$ to change to $r(kp) = \dfrac{p-a}{p}$, so $r_1$ and $r_{p-1}$'s position will switch with one another. Now, since $r_1$ comes last, let the numbers $r_{p-1}, r_{p-2}, \ldots,r_a$ already come before $r_1$'s existence, with $a$ the lowest number which satisfies that statement. $\color{green} \rule{25cm}{0.3pt}$ $\color{red} \rule{8.65cm}{2pt}$ $\color{red} \clubsuit$ $\color{red} \boxed{\textbf{One Member from the Full-House Missing.}}$ $\color{red} \clubsuit$ $\color{red} \rule{8.65cm}{2pt}$ We claim that $a \geq \dfrac{p+3}{2}$. In other words, the house of big averages \[ r_{\frac{p+1}{2}}, r_{\frac{p+3}{2}}, \ldots, r_{p-2}, r_{p-1} \]won't be flooding the grid before the extreme small average $r_1$ comes along. $\color{green} \rule{25cm}{0.3pt}$ $\color{magenta} \blacksquare$ $\color{magenta} \text{(after conjuring the extremal, you're pretty much almost a third of the way.)}$ $\color{red} \spadesuit$ $\color{red} \boxed{\textbf{Proof.}}$ $\color{red} \spadesuit$ Now let $a \leq \dfrac{p+1}{2}$. This means that all $r_{\frac{p+1}{2}}$ up to the largest average $r_{p-1}$ has appeared (and we do not consider the averages from the smaller house $r_{\frac{p-1}{2}}$ or below.) Continuing the trend of considering the $\textsf{latest}$, consider the largest out of $r_{\frac{p+1}{2}}$ to $r_{p-1}$. That number, say it is $r_b$, must satisfy \[ r_b \geq \dfrac{p-1}{2}\]as all the numbers $r_i$, $\dfrac{p+1}{2} \leq i \leq p-1, i \ne b$ has appeared before him. So, there has existed $br_b \geq \dfrac{p-1}{2} \cdot b \geq \dfrac{p^2-1}{4}$ reds before $r_1$. This directly yields a contradiction, as we only have $\dfrac{p^2-1}{4}-1$ blocks available; meaning that the number of reds before $r_1$ must be less than $\dfrac{p^2-1}{4}$. $\blacksquare$ $\blacksquare$ $\color{red} \rule{8.5cm}{2pt}$ $\color{red} \clubsuit$ $\color{red} \boxed{\textbf{As the Member comes, the Party is Over.}}$ $\color{red} \clubsuit$ $\color{red} \rule{8.5cm}{2pt}$ We claim that after $r_{p-1}$ up to $r_a$ appears before $r_1$, $r_{a-1}$ cannot fit in due to the overflow of blue numbers. Note: we can be sure that $r_{a-1}$ cannot $\textit{sneak in}$ to the party before $r_1$ due to the minimality assumption at the end of $\color{green} \diamondsuit$ $ \boxed{\textbf{The Order of the Extremes}}$ $\color{green} \diamondsuit$. $\color{red} \rule{25cm}{0.3pt}$ $\color{red} \spadesuit$ $\color{red} \boxed{\textbf{Proof.}}$ $\color{red} \spadesuit$ This is also easily explained. Since we already have at least $(p-a)a$ red points before the end of the $r_1^{\text{th}}$, so we can be certain that at the end of the $r_1^{\text{th}} \geq (p-a)a^{\text{th}}$ block, there exists a proportionate number of reds. We will similarly prove that the existing blue points after the $r_1^{\text{th}}$ block, $(p-1)(p-a)a$, cannot warrant the existence of $r_{a-1}$ which requires a relatively large red-density $\left( \dfrac{a-1}{p}\right)$ of points before it. Since there are only less than $\dfrac{p^2-1}{4}$ blocks, the total number of blues that exist $\textbf{before}$ the $r_{a-1}^{\text{th}}$ block is less than $\dfrac{p^2-1}{4}(p-a+1)$ blues. However, $\textbf{by the end}$ of the $r_1^{\text{th}}$ block, there is already $(p-1)r_1 \geq (p-1)(p-a)a$ blues. By simple inequalities, we will derive that \begin{align*} (p-1)(p-a)a &\geq (p-1)\left( \dfrac{p-a+1}{2} \right) \left( \dfrac{p+3}{2} \right) \\ &> (p-1) \left(\dfrac{p+1}{4}\right) (p-a+1) \end{align*}utilizing $a \geq \dfrac{p+3}{2}$ from the first Claim. We are done. $\blacksquare$ $\blacksquare$ $\blacksquare$

Quote: Let $p$ be an odd prime, let $N =\tfrac14(p^3-p)-1$, and let $S$ be a subset of ${1, \ldots , N}$. Show that there exists an integer $a \in \{1, \ldots , p-1\}$ such that for all positive integers $n \le N$, \[ \frac{|S \cap \{1, \ldots , n\}|}{n}\not=\frac{a}{p}.\] Solved with dantaxyz. Suppose no such $a$ exists. For each $i=1,\ldots,N$, let $x_i$ be $1$ if $i\in S$ and $0$ if $i\not \in S$. Then there exist integers $n_1,\ldots, n_{p-1}$ such that for all $a\in \{1,\ldots,p-1\}$, \[ x_1+\cdots+x_{n_a} = \frac{n_aa}{p}. \qquad (\clubsuit)\]Consider the sorted permutation of $\{n_1,\ldots,n_{p-1}\}$; $\pi$ is a permutation of $(1,\ldots,p-1)$ for which $n_{\pi(1)} < \cdots < n_{\pi(p-1)}$. Then subtracting two consecutive $(\clubsuit)$ equations: \[ x_{n_{\pi(i)}+1} + \cdots + x_{n_{\pi(i+1)}} = \frac{\pi(i+1)n_{\pi(i+1)} - \pi(i)n_{\pi(i)}}{p}. \]The LHS above is at least $0$ and at most $\pi(i+1)-\pi(i)$. (Indeed, we have no further control on the LHS than these bounds, since we've basically split $1,\ldots,N$ into these independent intervals.) So \begin{align*} 0\le \frac{\pi(i+1)n_{\pi(i+1)} - \pi(i)n_{\pi(i)}}{p} &\implies \frac{n_{\pi(i+1)}}{n_{\pi(i)}} \ge \frac{\pi(i)}{\pi(i+1)} \\ \pi(i+1)-\pi(i) \ge \frac{\pi(i+1)n_{\pi(i+1)} - \pi(i)n_{\pi(i)}}{p} &\implies \frac{n_{\pi(i+1)}}{n_{\pi(i)}} \ge \frac{p-\pi(i)}{p-\pi(i+1)}. \end{align*}So \[ \frac{n_{\pi(i+1)}}{n_{\pi(i)}} \ge \max \left(\frac{\pi(i)}{\pi(i+1)}, \frac{p-\pi(i)}{p-\pi(i+1)} \right). \qquad (\spadesuit) \]Also, note that $p\mid n_a$ for each $a$ since $p$ is a prime. Now, we will reformulate the problem into an equivalent, but easier to read statement. For each $k=1,\ldots,p-1$, define the integers $t_k = \tfrac{1}{p} n_{\pi(k)}$ and $a_k = \pi(k)$. The new problem is: Reduced Problem wrote: Consider an arbitrary permutation $\textbf{a} = (a_1,\ldots,a_{p-1})$ of $(1,\ldots,p-1)$. Positive integers $t_1<\cdots<t_{p-1}$ satisfy \[ \frac{t_{i+1}}{t_i} \ge \max \left( \frac{a_i}{a_{i+1}}, \frac{p-a_i}{p-a_{i+1}}\right) \qquad (\spadesuit) \]for each $i=1,\ldots,p-2$. Prove $t_{p-1} \ge \tfrac14(p^2-1)$. Lemma 1: [Telescoping intervals] In fact, for any $j>i$, we have \[ \frac{t_{j}}{t_i} \ge \max \left( \frac{a_i}{a_{j}}, \frac{p-a_i}{p-a_{j}}\right).\] Proof: Note that in $(\spadesuit)$, the max expression on the RHS is always at least $1$. Multiply together the $(\spadesuit)$ inequalities for $i,i+1,\ldots,j-1$. The LHS is $t_j/t_i$ by telescoping. The RHS is at least $\max \left( \tfrac{a_i}{a_{j}}, \tfrac{p-a_i}{p-a_{j}}\right)$ since each $(\spadesuit)$ RHS's are at least 1, and $a_i/a_j$ and $(p-a_i)/(p-a_j)$ are at most the product of the max's. $\blacksquare$ Main idea: The main idea is to consider the unique number $x \in [1,p-2]$ for which in $\textbf{a}$, $1,\ldots,x$ appear before $p-1$ in some order, and $x+1$ appears after $p-1$. Lemma 2: There exists an integer $k\ge x$ for which $a_k \le x$. Proof: If no such $k$ exists, then for all $k\ge x$, we have $a_k > x$. So $a_{x},\ldots,a_{p-1} \in \{x+1,\ldots,p-1\}$, impossible by Pigeonhole. $\blacksquare$ Consider the $k$ from Lemma 2. Since $a_k \in \{1,\ldots,x\}$, $a_k$ must appear before $p-1$ in $\textbf{a}$. Define $v$ such that $t_v=p-1$. By Lemma 1, \[ \frac{t_v}{t_k} \ge \frac{p-a_k}{p-(p-1)} = p-a_k \implies t_v \ge k(p-a_k) \ge x(p-x). \qquad (\heartsuit) \]Now we have to use the fact that $x+1$ appears after $p-1$. Suppose $a_u=x+1$. Since $u>v$, by Lemma 1 we have \[ \frac{t_u}{t_v} \ge \frac{a_v}{a_u} = \frac{p-1}{x+1} \implies t_u \ge \frac{p-1}{x+1}t_v. \qquad (\diamondsuit) \] We will use the bounds $(\heartsuit)$ and $(\diamondsuit)$ to finish. Case 1: $x\ge \tfrac{p+1}{2}$. In this case, we only need $(\heartsuit)$. We can simply set $x=\tfrac{p+1}{2}$ since $\{1,\ldots,\tfrac{p+1}{2}\}$ all appear before $p-1$. Then by $(\heartsuit)$, \[ t_v\ge \left(\frac{p+1}{2}\right)\left(p-\frac{p+1}{2}\right) = \frac{p^2-1}{4}.\]Since $t_{p-1}>t_v$, we are done. Case 2: $x\le \tfrac{p-1}{2}$. Combining $(\heartsuit)$ and $(\diamondsuit)$, we have \begin{align*} t_v \ge \frac{p-1}{x+1}t_v \ge \frac{p-1}{x+1}\cdot x(p-x). \end{align*}Using the bound $\tfrac{x}{x+1}\ge \tfrac12$, the above is \[ \frac{(p-1)x(p-x)}{x+1}\ge \frac12(p-1)(p-x) \ge \frac12(p-1)\left( \frac{p+1}{2}\right) = \frac{p^2-1}{4}. \]Since $t_{p-1}>t_v$, we are done. Remark: [Equivalency of reduction] The reformulation is actually equivalent, since once we've split $\{1,\ldots,N\}$ into the intervals split by the $n_{\pi(i)}$'s, we have no control over the amount of elements of $S$ inside each; also, these are all independent to each other. Remark: [Motivation behind solving reformulated problem] We cannot just telescope multiply all the inequalities and get an expression for $t_n/t_1$ since there would not be an equality case with $t_i$'s all \textit{integers}. We know that $t_i\ge i$ due to the integer property. We can strategically use this along with some telescoping of certain intervals to finally get the desired bound. We played with a lot of ways to get the desired bound, but were only able to handle specific cases; for example, if in $\textbf{a}$, $p-1$ appears before 1 appears before $p-2$, then by Lemma 1, the total multiplier is at least $(\tfrac{p-1}{1})(\tfrac{p-1}{2})$, which is good enough. These sort of cases are very limited in scope covered, so the following setup handles any general $\textbf{a}$, and we are able to coax out the desired bound. Remark: [On Case 1 in final bounding] The idea of taking $x$ to be \textit{exactly} $\tfrac{p+1}{2}$ in Case 1 is actually a nontrivial argument, that we cannot just use the bounds $(\heartsuit)$ and $(\diamondsuit)$ as given to finish from. If we were to just use $(\heartsuit)$ with $x\ge \tfrac{p+1}{2}$, we do not know that $x(p-x) \ge \tfrac14(p^2-1)$; indeed, the inequality sign is actually in the wrong direction. The fact that $\{1,\ldots,x\}$ is contained in $\{1,\ldots,y\}$ if $x<y$ is a nontrivial fact that allows us to set $x=\tfrac{p+1}{2}$ exactly.

One of the most beautiful combinatorial sequence problem I have seen, even more so than the previous ones I encountered back then! It makes me feel compelled to write up my thoughts and post my solution here

If $r(n)=\frac{a}{p}$, then clearly $n$ must be multiple of $p$. So it suffice to check $r(ip)$ for all $1\le i\le\lfloor \frac{N}{p}\rfloor=T$. Note that $T<\frac{p^2-1}{4}$. Let's consider the number of red points in the interval $[ip+1, (i+1)p]$, call it $x_i$ for all $1\le i \le T$. Then $r(ip)=\frac{x_1+\cdots x_i}{ip}$, which we have $$r(ip)=\frac{a}{p} \iff \frac{x_1+\cdots +x_i}{i}=a$$ This allow us to reformulate the problem into the following: "Let $x_1, \cdots, x_T$ be integers between $0$ to $p$, with $T=\frac{p^2-1}{4}-1$. Then define $$y_n=\frac{x_1+\cdots +x_n}{n}$$We want to prove there is some integer $1\le a\le p-1$ that doesn't appear in any of $y_1, \cdots, y_T$." Suppose for the sake of a contradiction, that there are indices $1\le t_1, \cdots, t_{p-1} \le T$ with $y_{t_i}=i$ for all $1\le i\le p-1$. Observe that if we define $s_n=ny_n=x_1+\cdots+x_n$, then by considering $x_n\ge 0$, we get $s_n$ is non-decreasing, so $$t_i<t_j \Rightarrow s_{t_i}\le s_{t_j} \Rightarrow it_i\le jt_j \hspace{3mm} \text{and} \hspace{3mm} t_i>t_j \Rightarrow s_{t_i}\ge s_{t_j} \Rightarrow it_i\ge jt_j$$ By considering $p-x_n\ge 0$ instead, we get a symmetrical result that $np-s_n$ is non-decreasing, so $$t_i<t_j \Rightarrow pt_i-s_{t_i}\le pt_j-s_{t_j} \Rightarrow (p-i)t_i\le (p-j)t_j \hspace{3mm} \text{and} \hspace{3mm} t_i>t_j \Rightarrow pt_i-s_{t_i}\ge pt_j-s_{t_j} \Rightarrow (p-i)t_i\ge (p-j)t_j$$ We claim that $t_1, \cdots, t_{p-1} \in [1, \frac{p^2-1}{4}-1]$ is impossible. We may assume $t_1<t_{p-1}$, otherwise consider replacing $x_n$ by $p-x_n$, and $t_i$ by $t_{p-i}$. This is the same as swapping red and blue numbers in the original problem setting. Case 1: If $t_{p-1}>t_i$ for all $1\le i\le \frac{p-1}{2}$, then take the maximal $t_a$ among $t_1, \cdots, t_{\frac{p-1}{2}}$, then $$t_{p-1}>t_a \Rightarrow t_{p-1}\ge (p-a)t_a \ge (p-a)\frac{p-1}{2}\ge \frac{(p+1)(p-1)}{4}>T$$ Case 2: - For some smallest $1\le k< \frac{p-1}{2}$ we have $t_{k}<t_{p-1}<t_{k+1}$. Note $k\neq 1$ by our assumption. Now we take the maximal $t_a$ among $t_1, \cdots, t_{k}$ and observe that, $$t_{k+1}>\frac{p-1}{k+1}t_{p-1}>\frac{p-1}{k+1}(p-a)t_a\ge \frac{k}{k+1}(p-1)(p-k)\ge\frac{p^2-1}{4}>T$$ So in both cases, those numbers $t_1, \cdots, t_{p-1}$ cannot all lie within $[1, T]$, and we are done! $\blacksquare$

very nice

Surprisingly neat problem. Clearly the only values of $n$ that can have $r(n)$ with a $p$ in the denominator are multiples of $p$. Suppose the problem is false, and let $k_ip$ be the value of $n$ for which $r(n) = \frac{i}{p}$. Note that if $k_i < k_j$, then since the gap in between has at least $0$ reds and at most $(k_j - k_i)p$ reds, we get the inequalities $\frac{k_j}{k_i} \geqslant \frac{i}{j}, \frac{p-i}{p-j}$. Since $N < \frac{p^3 - p}{4}$, we have that $\max(k_1, k_2, \cdots, k_{p-1}) < \frac{p^2 - 1}{4}$. Note that flipping colors still gives a valid coloring, but with $k_i$ replaced with $p - k_i$, so WLOG assume that $k_1 < k_{p-1}$. Consider the numbers $k_1, k_2, \cdots, k_{\frac{p-1}{2}}$. I claim at least one of them is above $k_{p-1}$. If not, suppose the maximum among them is $k_j$. Clearly $k_j$ is at least $\frac{p-1}{2}$. But then $\frac{k_{p-1}}{k_j} \geqslant \frac{p-j}{1}$ giving that $k_{p-1} \geqslant (p-j)k_j \geqslant \frac{p+1}{2} \cdot \frac{p-1}{2} = \frac{p^2 - 1}{4}$ which is impossible. Now, consider the maximal index $\ell$ such that all of $k_1, k_2, \cdots, k_{\ell}$ are less than $k_{p-1}$. Then since $k_{\ell + 1} > k_{p-1}$, we have that $k_{\ell + 1} \geqslant \frac{p-1}{\ell + 1} \cdot k_{p-1}$. But since $k_{p-1} > k_{\ell}$, we also have that $k_{p-1} \geqslant \max((p-i)k_i) \geqslant \frac{p+1}{2} \cdot \ell$ because at least one value must have $k_i$ at least $\ell$ and $p-1$ is at least $\frac{p+1}{2}$. So overall, we obtain that $k_{\ell + 1} \geqslant \frac{p-1}{\ell + 1} \cdot \frac{p+1}{2} \cdot \ell = \frac{p^2 - 1}{2} \cdot \frac{\ell}{\ell + 1} \geqslant \frac{p^2 - 1}{4}$, which is again a contradiction. So it's impossible that there is a $k_i$ for every $i \in \{1,2,\cdots,p-1\}$, so the problem is proved. $\blacksquare$

. Despite this taking nearly 2 and a half hours, it turns out that the extremal principle kills most of the problem as soon as you have the first two claims. Let $a_i$ be minimal value of $n$ such that $r(n)=i/p$ for each $i$. The key claim is the following. Claim: If $a_i<a_j$, then \[ \frac{a_i}{a_j} \le \min\left(\frac{j}{i}, \frac{p-j}{p-i}\right). \]Proof. This is easy to see by considering the upper and lower bounds of the number of red integers between $a_i$ and $a_j$. Lemma: There exists an index $k \le \frac{p-1}{2}$ with the property that $a_k>a_{p-1}$. Proof. Assume for contradiction that for all $k \le \frac{p-1}{2}$, $a_k<a_{p-1}$. Then, by the prior claim, we have \[ \frac{a_k}{a_{p-1}} \le \min\left(\frac{p-1}{k}, \frac{1}{p-k}\right) = \frac{1}{p-k}, \]so \[ a_{p-1} \ge (p-k)a_k \ge \left(\frac{p+1}{2}\right)\left(p \cdot \frac{p-1}{2}\right) > N, \]a contradiction. The crux of the proof is to, in light of the extremal principle, consider the greatest index $j$ such that $a_k<a_{p-1}$ for all $k \le j$. In particular, the lemma induces the upper bound $j \le (p-1)/2$. By maximality, $a_{j+1}>a_{p-1}$, so using the key claim on $\{a_j, a_{p-1}\}$ and $\{a_{j+1}, a_{p-1}\}$, \[ a_{p-1} \ge (p-j)a_j, \]and \[ a_{j+1}\ge a_{p-1} \cdot \frac{p-1}{j+1}, \]so eliminating $a_{p-1}$ yields \[ a_{j+1} \ge \frac{(p-1)(p-j)}{j+1} \cdot a_j \ge \frac{jp(p-1)(p-j)}{j+1} \ge \frac{p^3-p}{4} > N, \]a contradiction. Therefore, there exists a positive integer $a \in \{ 1,2, \dots, p-1\}$ such that $r(n) \neq a/p$ for all $n = 1,2, \dots , N$, as desired.

We will reformulate the problem: Ashley places down marbles, each one is colored red or blue. We'll show that if for each $a\in\{1,2,\dots,p-1\}$, at some point in time the ratio of red marbles to blue marbles is $a:p-a$, then the number of marbles Ashley has placed is at least $N+1$. $~$ Suppose the order in which the desired ratio $a:p-a$ is reached is $a_1:b_1,a_2:b_2,\dots,a_{p-1}:b_{p-1}$ where $a_i+b_i=p$. The first time the ratio becomes $a_i:b_i$, let there be $A_i$ red marbles and $B_i$ blue marbles. We must have $A$ and $B$ as non-decreasing sequences. Now, we will try to construct the sequences $a$, $b$, $A$, and $B$ to achieve the minimum possible value of $A+B$. There are $A_i$ red marbles $B_i$ blue marbles, and the ratio is $a_i:b_i$. Now, consider $A_{i+1}$ and $B_{i+1}$. We need $a_{i+1}\mid A_{i+1}$ and $b_{i+1}\mid B_{i+1}$. Suppose WLOG that $a_{i+1}>a_i$, then \[B_{i+1}\ge (b_{i+1}) \left\lceil \frac{B_i}{b_{i+1}}\right\rceil\]so $A_{i+1}\ge (a_{i+1}) \left\lceil \tfrac{B_i}{b_{i+1}}\right\rceil$. It is similar when $b_{i+1}>b_i$. $~$ Given fixed sequences $a$ and $b$, choosing greedily always proves to be optimal. Inductively, this is simple. If $A_{i}$ and $B_{i}$ are greater than the value obtain greedily, then $B_{i+1}$ necessarily will be, and by proportionality so will $A_{i+1}$. In particular, the local proportionality of $A$ and $B$ ensures that our argument works regardless of whether $b_{i+1}>b_i$ or $a_{i+1}>a_i$. $~$ Thus, we can assume that the following algorithm is used to optimally construct $A$ and $B$ using a given $a$ and $b$: $A_1=a_1$ and $B_1=b_1$. Subsequently, \[B_{i+1} = \begin{cases} (b_{i+1}) \left\lceil \frac{B_i}{b_{i+1}}\right\rceil & a_{i+1}>a_i \\ (b_{i+1}) \left\lceil \frac{A_i}{a_{i+1}}\right\rceil & b_{i+1}>b_i \end{cases}\]\[A_{i+1} = \begin{cases} (a_{i+1}) \left\lceil \frac{B_i}{b_{i+1}}\right\rceil & a_{i+1}>a_i \\ (a_{i+1}) \left\lceil \frac{A_i}{a_{i+1}}\right\rceil & b_{i+1}>b_i \end{cases}\]In fact, this construction gives us an advantage. Note that at each point in time, $p=a_i+b_i\mid A_i+B_i$. Let $A_i+B_i=pc_i$ for all $i$. Look from $i$ to $i+1$: does $a$ decrease or does $b$ decrease. Assume WLOG that $a$ decreases, so we are in the case $b_{i+1}>b_i$. We have $A_{i+1}+B_{i+1}=p\left\lceil \frac{A_i}{(a_{i+1})}\right\rceil$ so \[c_{i+1}=\left\lceil \frac{A_i}{a_{i+1}}\right\rceil=\left\lceil \frac{a_i}{a_{i+1}}\cdot c_i\right\rceil\]Note that $c$ changes very predictably. We start, obviously, with $c_1=1$. We want to show that $c_{p-1}\ge \tfrac{1}{4}(p^2-1)$. $~$ Assume $1:p-1$ comes before $p-1:1$ in the sequence $a:b$. We have two facts about $c$, both are pretty obvious: $c_{i+1}>c_i$ and for $j>i$, that $c_j>\tfrac{a_j}{a_i}c_i,\tfrac{b_j}{b_i}c_i$. Now assume that $\{2:p-2,3:p-3,\dots,\tfrac{p-1}{2}:\tfrac{p+1}{2}\}$ all appear before $p-1:1$. Note that when we get to the last of that set to appear, our index is at least $\tfrac{p-1}{2}$. Thus, for some $i\ge \tfrac{p-1}{2}$ we have $b_i\ge \tfrac{p+1}{2}$ and $c_i\ge \tfrac{p-1}{2}$, implying that if $a_j=p-1,b_j=1$ that $c_j\ge \tfrac{p^2-1}{4}$, as desired. Now assume that this is not true, then suppose that $\{2:p-2,3:p-3,\dots,k:p-k\}$ all appear before $p-1:1$ but not $k+1:p-k-1$. Then, $c_j\ge k(p-k)$, $c_n\ge \frac{(p-1)(p-k)k}{k+1}\ge\tfrac{p^2-1}{4}$ as desired.

welp i didn't solve again but i will try to recreate sol i guess. Obviously define $x_1,\dots,x_{p-1}$ where $r(px_i)=\frac{i}{p}$. Realize that \[x_i>x_j\implies \frac{x_i}{x_j}\ge \text{max}\left(\frac{j}{i},\frac{p-j}{p-i}\right)\]by simple bounding. (It makes sense that $p$ prime should be irrelevant since there should be some sort of upper bound on $N$ which isn't really related.) We assume FTSOC that all $x_i$ are less than $\frac{1}{4}(p^2-1)$. It's helpful to even order \[x_{\pi(1)}\le \dots \le x_{\pi(p-1)}\]and find the equality case where $\pi$ is the identity. This case can be proven by splitting around the halfway mark and performing optimal bounds on the ceiling function. The point is that the original inequality doesn't give too much information unless we have useful information on the numbers we are plugging in. Since this seems like the only reasonable idea we may as well consider the following: \[x_{p-1}>x_j\implies \frac{x_{p-1}}{x_j}\ge p-j\]and from the original "splitting around the halfway mark" equality case we're motivated to consider when $j\le \frac{p-1}{2}$. In this case we actually must have \[x_j<\frac{p-1}{2}\]which is actually enough to imply that some $j\le \frac{p-1}{2}$ has $x_j>x_{p-1}$. Otherwise we'd have \[x_1,\dots,x_{(p-1)/2}<\frac{p-1}{2}\]which doesn't happen by PHP. In light of this, it makes sense to consider the first such value. (This feels natural because, as usual, we want more information and we have a bound on said value.) Now we actually have a bound \[\frac{x_j}{x_{p-1}}\ge \frac{p-1}{j}\]and we essentially need some other fractions to multiply this with. If $j\ge 2$ then for every $i\in \{1,\dots,j-1\}$ we have $x_i<x_{p-1}$. Importantly, we can write \[\frac{x_{p-1}}{x_i}\ge p-i\]hence \[x_j\ge x_i(p-i)\cdot \frac{p-1}{j}\]and from logic used above we can also note $x_i<j-1$ for all applicable $i$ can't happen. Use the weaker bound $i\le \frac{p-1}{2}$. Hence \[x_j\ge (j-1)(p-i)\cdot \frac{p-1}{j}\ge \frac{j-1}{j}\cdot \frac{p+1}{2}\cdot (p-1)\ge \frac{1}{2}\cdot \frac{p+1}{2}\cdot (p-1)=\frac{1}{4}(p^2-1)\]which fails. If $j=1$, then we essentially have that the ratio $\frac{1}{p}$ didn't appear before $\frac{p-1}{p}$. By a simple red-blue swap we can make sure this doesn't happen. Yay!

Let $red(n)$ be the number of red numbers among $\{ 1,2, \dots, n \}$. Then $r(n)=\frac{red(n)}{n}$. FTSOC, suppose for all positive integers $a \leq p-1$ one of $r(n)$ is equal to $a/p$. Obviously, for this $n \vdots p$ Let $a_k=red(pk)-red(p(k-1))$, $0 \leq a_k \leq p$. Then $r(pk)=\frac{red(pk)}{pk}=\frac{a_1+\ldots+a_k}{k}/p$, so among $\frac{a_1+\ldots+a_i}{i}$ there are all numbers $ \{ 1,2, \dots, p-1\}$. Also, there are $\lfloor \frac{N}{p} \rfloor=\frac{p^2-5}{4}$ a's Let $pr(pb_1)=c_1,\ldots pr(pb_{p-1})=c_{p-1}$, where $c_i$ is the permutation of $1, \ldots, p-1$ and $b_1 < b_2 < \ldots <b_{p-1}$ Then $0 \leq c_{i+1}b_{i+1}-c_ib_i=a_{b_i+1}+\ldots+a_{b_{i+1}} \leq p(b_{i+1}-b_i)$. Then $b_i(p-c_i) \leq b_{i+1}(p-c_{i+1})$ So we get two chains of inequalities: $$c_1b_1 \leq c_2b_2 \leq \ldots \leq c_{p-1}b_{p-1}$$$$(p-c_1)b_1 \leq (p-c_2)b_2 \leq \ldots \leq (p-c_{p-1})b_{p-1}$$There consider the later of $1$ and $p-1$ in $c_i$, wlog it is $1=c_a$, $b_a=m$. Let among $c_1,\ldots,c{a-1}$ appear $p-1, \ldots, p-k$, but not $p-k-1$. We know $k \geq 1$. If $k \geq \frac{p-1}{2}$, then among $p-1,\ldots,\frac{p+1}{2}$ at least one has index $\geq \frac{p-1}{2}$, because $b_i \geq i$, $m \geq \frac{p-1}{2} \frac{p+1}{2}=\frac{p^2-1}{4}>\frac{p^2-5}{4}$ - contradiction. So $k \leq \frac{p-3}{2}$. If $p=3$, $1 \leq k \leq 0$ - contradiction, so $p \geq 5$. Now also do the same argument with $p-1,\ldots,p-k$, so $m \geq k(p-k)$ Now consider the second chain of inequalities. We know that $p-k-1=c_r$, where $r>a$, so $p-c_r=k+1$. Then $(p-1)m \leq (k+1)b_r$, so $\frac{p^2-1}{4} > b_r \geq \frac{(p-1)m}{k+1} \geq \frac{(p-1)k(p-k)}{k+1}$, so $(p+1)(k+1) > 4k(p-k)$, so $$4k^2-(3p-1)k+(p+1)>0$$This function of $k$ is convex, so it's maximum on the segment $[1,\frac{p-3}{2}]$ must be in one of it's endpoints. $k=1$: $4-(3p-1)+(p+1)>0$, which rewrites as $p<3$ - false. $k=\frac{p-3}{2}$: $2(p-3)^2-(3p-1)(p-3)+2(p+1)>0$ $2p^2-12p+18-3p^2+10p-3+2p+2>0$, which rewrites as $p^2<17$ - false