We will induct on the stronger condition with $\frac{51}{100}N$ replaced with $\frac{N+p}2$. Case 1: some value appears at least $\frac N2$ times WLOG $a_1=\cdots=a_k\neq a_{k+1}$. Let $p\mid za_1+a_{k+1}$. Apply the inductive hypothesis on $a_{z+1}$, $\ldots$, $a_k$, $a_{k+2}$, $\ldots$, $a_N$ to get $b_{z+2}$, $\ldots$, $b_N$, and let $b_1$, $\ldots$, $b_{z+1}$ be a permutation of the others. If $b_{z+1}\neq b_{z+2}$, then swapping $b_{z+1}$ and $b_{z+2}$ gives the desired permutation. This is always possible since no proper subset of $b$ sums to $0$ mod $p$ and $b$ contains two distinct values. Case 2: no value appears at least $\frac N2$ times By Cauchy-Davenport, there exists a subset of size at most $p-1$ adding to a multiple of $p$, so split $a$ into two sets such that one set adds to a multiple of $p$ and has minimal size. Apply the inductive hypothesis on the other set, then repeat the same procedure from case 1. The problem follows from the bound $\frac{51}{100}N<\frac{N+p}2$ for $N<50p$.

We will use a competitive programming-style solution: Step one: repeatedly, find smallest $i$ such that $\sum_{k \le i} a_i = 0$, and find smallest $j > i$ with $a_j \not = a_i$ (or stop if no such $j$) After this, all errors are confined to a single block of identical numbers at the end of the permutation. Use modular division, WLOG the final block consists of $1$s. Essentially convert all non-$1$ numbers to negatives and move $1$s from the end to cancel out negatives until there is no longer issues with the sums at the end the $\frac{N+p}{2}$ condition guarantees this to work

I'll just point out that I already set a problem on this setting before (editorial contains complete criteria and proof for when such permutation exists): https://atcoder.jp/contests/agc052/tasks/agc052_c

Key Lemma: Let $c_{i} \in \left\{1,2,\ldots,p-1\right\}$ for $1 \leq i \leq n$ such that each specific value occurs at most $\frac{n+1}{2}$ times. Fix a residue $r \not\equiv c_1+\cdots+c_{n} \pmod{p}$ then it is possible to construct a permutation $\left(d_i\right)_{1 \leq i \leq n}$ of the $c_i$ such that $r \not \equiv d_1+\cdots+d_k \pmod{p}$ for $1 \leq k \leq n$. Proof: We go by induction on $n$. $n=1$ is clear. Let $a$ be the residue that occurs the most times amongst the $c_{i}$. If $a \not \equiv r \pmod{p}$ then we set $d_{1}=a$ and complete the rest of the list using the inductive hypothesis as any residue will occur amongst the remaining $c_i$ at most: $$ \frac{n+1}{2}-1=\frac{n-1}{2}<\frac{(n-1)+1}{2} $$times. If $a \equiv r \pmod{p}$ then let $b \not \equiv a \pmod{p}$ be another residue amongst the $c_i$ (which is possible as $\frac{n+1}{2}<n$). Set $d_{1}=b$ and $d_{2}=a$ noting that: $$ a+b \equiv r+b \not \equiv r \pmod{p} $$Each residue occurs amongst the remaining $c_i$ at most: $$ \frac{n+1}{2}-1=\frac{n-1}{2}=\frac{(n-2)+1}{2} $$times so we can again use the inductive hypothesis to complete the list. Now back to the main problem. If each residue occurs at most $\frac{N+1}{2}$ times then we can just apply the above Key Lemma. Otherwise, let $a$ be the residue that occurs $M>\frac{N+1}{2}$ times amongst the $a_i$. We set $b_{i}=a$ for $1 \leq i \leq k$ where $k \leq p-1$ is an integer we will determine. As $p$ is prime, this will ensure that none of the first $k$ partial sums is divisible by $p$. We will then complete the rest of the list using the Key Lemma which requires us to show each residue occurs at most $\frac{N-k+1}{2}$ times amongst the remaining $a_i$. Residue $a$: $a$ occurs amongst the remaining $a_i$ exactly $M-k$ times so we require: $$ M-k \leq \frac{N-k+1}{2} \Leftrightarrow k \geq 2M-N-1 \quad \quad (\blacktriangle) $$times. Observe that: $$ 2M-N-1 \leq \frac{102N}{100}-N-1=\frac{N}{50}-1<p-1 $$So this will not force us to violate the $k \leq p-1$ condition. Other residues: The other residues occur at most $N-M$ times so we want: $$ N-M \leq \frac{N-k+1}{2} \Leftrightarrow k \leq 2M+1-N \quad \quad (\blacksquare) $$And observe $2M+1-N>2\cdot \frac{N+1}{2}+1-N \geq 1$. So observe if we choose $k=2M-N$ we satisfying the two conditions $(\blacktriangle)$, $(\blacksquare)$ and $1 \leq k \leq p-1$ so the conditions of the Key Lemma are satisfied.

Greedy algorithm works. Let $c_1, c_2, \dots c_{p-1}$ be the number of $1, 2, \dots, p-1$ among $a_1, a_2, \ldots , a_N$ respectively. First we determine the greatest $c_i$ and we let $b_1 = i$, then we set $c_i= c_i-1$ ( because we used 1 $i$) Then at step $j$ we determine the greatest $c_i$, if $(\sum_{ k=1}^{j-1} b_k )+ i \not \equiv 0 (mod p) $ we let $b_j=i$ and $c_i= c_i-1$ ; if $(\sum_{ k=1}^{j-1} b_k )+ i \equiv 0 (mod p) $ then we take the second greatest $c_i$ and do the same. Note that this algorithm fails if and only if we have just 1 type of number left and we cannot add it to our sequence. Call this number $m$. Suppose we have the sequence $b_1,b_2, \dots b_{N-t} $ and t $m$'s. We have $(\sum_{ k=1}^{N-t} b_k )+ m \equiv 0 (mod p) $ we also know, $\sum_{ k=1}^{N} a_k \not \equiv 0 (mod p) $ hence $t\geq2$. Now consider the number $b_{N-t}$. We claim $b_{N-t}=m$. Suppose $b_{N-t}=n \not=m $, we have $\sum_{ k=1}^{N-t} b_k \equiv -m (mod p) $ so $\sum_{ k=1}^{N-t-1} b_k \not \equiv -m (mod p) $ but we also have $ t=c_m> c_n =1$, thus $b_{N-t}=m$. Now take the biggest $s$ such that $b_s \not=m$. We must have $\sum_{ k=1}^{s-1} b_k \equiv -m (mod p) $, but then we have $\sum_{ k=1}^{s-2} b_k \not \equiv -m (mod p) $ so $b_{s-1}=m$. If we apply this procedure repeatedly, we get: at least one of the two consecutive numbers is $m$, since obviously $c_m> c_i $ for each $i$ at each step. We also know that $b_1=b_2=\dots b_{p-1}=m$. But then the total number of $m\geq $ $ p-1 + \frac{N-t-(p-1)}{2}+t \geq p-1+ \frac{N-2-(p-1)}{2}+2 > \frac {51N}{100} \Leftrightarrow N + p+1> \frac{102N}{100}$ $\Leftrightarrow p+1>\frac{2N}{100} \Leftrightarrow 50p+50>50p>N$ We reached contradiction, hence the algorithm works.

My Solution

Attachments:
2024 RMM Problem 2 Day 1.pdf (146kb)

this can also be approached via combinatorial designs no?

Let multiset $A = \{a_i|1 \leq i \leq N\}$ We imagine permuting $a$ as taking elements one by one from $A$ until $A = \emptyset$ Say that we permuted $b_1$ to $b_{i-1}$ and are choosing $b_i$. We present the following algorithm: (1) Let $t$ be the element with highest frequency in $A$. If $\Sigma_{1 \leq j \leq i-1} b_j + t$ is not divisible by $p$, let $b_i = t$ (2) Otherwise, select the element with second highest frequency $k$ and let $b_i = k$ We make the following trivial observations - After an operation (2) we can always do (1) at least once more before having to resort to (2) again - If there is one element whose frequency is above all others by a margin larger than $(p-1)$, we can use (1) $(p-1)$ continuous times on this element - The only way for this algorithm to fail is if, at the end, we have only one type of number remaining in $A$ with a frequency larger than $1$ If the condition in observation 2 doesn't apply, then we're done as we immediately obtain two numbers with equal frequency, and thus condition 3 is impossible Otherwise, if the maximal frequency in $A$ is $f$ then note that $$f - (p-1) - \frac{49}{100}N \leq \frac{2}{100}N - (p-1) < p - (p-1) = 1$$Thus, condition $3$ is impossible and the algorithm unconditionally works

The following solution is similar to the official one, but it emphasizes on a constructive algorithm. Suppose we initially have a multiset $A$ of residues modulo $p$ (we allow $0\in A$) that satisfies the condition $$\text{Each value in }A\text{ occurs at most } \left\lceil \frac{|A|}{2}\right\rceil \text{ times.}\qquad(1) $$Then $A$ can be arranged in a row $b_1,b_2,\dots,b_N, N:=|A|$ that satisfies the problem's condition. This arrangement can be done via a greedy algorithm with a little bit common sense. Here it is. Because of condition $(1)$ there are at least two distinct values in $A$. So, we start putting the elements of $A$ in a row, each time picking a residue that avoids a certain residue, i.e. it avoids the sum of the already arranged residues taken with a negative sign. Assume at some moment, we have a multiset $A'$ and some of its values, say $r$ occurs exactly $\left\lceil {|A'|}/{2}\right\rceil$ times. We try to pick this value, and if we cannot do this, because we would hit $0$, then we pick another residue $r_1$ and and we put $r$ immediately after $r_1$. Thus, we comply with the given condition and we are at position with a multiset $A''$ that consists of $|A'|-2$ elements. The point is that $A''$ still satisfies $(1)$, so we can continue with the same algorithm. It remains to see what to do when initially some value $r$ in $A$ occurs $k$ times and $k>\left\lceil {|A|}/{2}\right\rceil$ times. This time we want $0\notin A$. So, $$\left\lceil {|A|}/{2}\right\rceil < k<\frac{51}{100}|A|\qquad (2).$$Now, we put all the elements equal to $r$, but no more than $p-1$ of them, one after another in a row. Any partial sum of this row is not $0$, since $0\notin A$. Because of $(2)$ and the fact that $|A|<50p$, the remaining elements form a multiset $A'$ that satisfies $(1)$. Further, we proceed with the above algorithm, avoiding a certain residue each time.

We will prove the following greedy algorithm. If there exists $\tfrac{N+k}{2}$ ($0<k$) $a_i$ all equal to each other then place $k$ of them at the beginning of the permutation. Out of all the residues that would not make the sum divisible by $p$ take the one that occurs the most out of the remaining elements. Repeat this step until the sequence ${b_i}$ is finished. Because of the bound we must have $k<p$ so the first $k$ terms in the sequence are fine. After that notice that no more than just over half of the remaining elements are equal. Now for any set of equal $a_i$ once they become the largest then they will get placed in the sequence at worst every other move and thus will fit in.