If $n-1$ integers are so that no partial sums are divisible by $n$, then the integers are congruent mod $n$ to one number coprime to $n$.

Question

Let $a_1,a_2,...,a_{n-1}$ be integers. Suppose that there is no subset $S\ne \emptyset$ of $\{1,2,...,n-1\}$ such that $\sum_{k\in S}a_k\equiv 0\pmod{n}$. Show that there exists an integer $a$, $0< a< n$ st $\gcd(a,n)=1$ and $a_1,a_2,...,a_n\equiv a\pmod{n}$.

Source : https://artofproblemsolving.com/community/c6h626708p3759215 (mavropnevma's comment)

My attempt : Let $s_k=a_1+a_2+...+a_k$. Then $s_1,s_2,...,s_{n-1}$ form a permutation of $1,2,...,n-1$ (mod n). Let $s_0=0$ and consider the subscripts mod $n$. Then the condition that $\sum_{k\in S}a_k\ne 0\pmod{n}$ for all $S\subseteq\{1,2,...,n-1\}$ st $S\ne \emptyset$ implies $\sum_{k\in S}s_k \ne \sum_{k\in S}s_{k-1}\pmod{n}$. This is where I'm stuck.

Answer 1

For a subset $S$ of $1\ldots n-1$ let $f(S)= \{ \sum_{j\in T} a_j, \emptyset\subsetneq T\subset S\}$.

Claim: if $i\not \in S$ then $$|f(S \cup i)|\ge |f(S)|+1$$ Proof: $a_i+\sum_{j\in S} a_j$ can't be in $f(S)$, as otherwise we'd have $a_i+\sum_{j\in S} a_j=\sum_{j\in T} a_j$ for some $T\subset S$ so $a_i+\sum_{j\in S,\not \in T} a_j = 0$.

If some $a_j\ne a_1$ then $|f(\{1,j\}|=3$ so that for $1,j\not \in S$: $|f(\{1,j\}\cup S)|\ge 3+|S|$ which gives that $f(\{1,\ldots,n-1\})$ contains the whole of $0\ldots n-1$.

Answer 2

(This is essentially identical to reuns' solution, but has an easier presentation / more reasonable to come up with the solution.)

If there exists 2 element that are different from each other, WLOG $a_1 \neq a_2$, then consider the $n$ terms

$$ a_1, a_2, a_1 + a_2, a_1 + a_2 + a_3, \ldots, \sum a_i .$$

Consider their remainder mod $n$.
Since none of them are 0, there are $n-1$ possibilities.
By the PP, 2 of them have the same remainder mod $n$.
This pair of terms cannot be $a_1, a_2$.
Hence, we may taking the difference of these terms, which gives us a sequence that sums to 0 mod n.
Contradiction.

---

Note:
The solution can be arrived by thinking that it likely has a PP solution, so how can we apply PP?
Clearly we (likely) have the $n-1$ remainder as holes.
However, taking the standard $\sum_{i=1}^k a_i$, we seem to only have $n-1$ pigeons. Thus, we need to "force" out another pigeon.