Kvant Math Problem 1267
Consider small values of $n$ to understand the behavior of the remainders $r_k$.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m07s
Source on kvant.digital
Problem
Let $a_1$, $a_2$, $\ldots$, $a_n$ be some permutation of the numbers 1, 2, $\ldots$, $n$; $r_k$ is the remainder of dividing the number $a_1+a_2+\ldots+a_n$ by $n$ ($k=1$, 2, $\ldots$, $n$). Prove that among the numbers $r_1$, $r_2$, $\ldots$, $r_n$ there are at least $\sqrt{n}$ distinct ones.
L. D. Kurlandchik
Exploration
Consider small values of $n$ to understand the behavior of the remainders $r_k$. For $n=2$, the permutation $(1,2)$ gives partial sums $1$, $1+2=3$, with remainders $1 \bmod 2$ and $1 \bmod 2$, yielding only one distinct remainder, which equals $\sqrt{2} \approx 1.414$. For $n=3$, take $(1,2,3)$; the partial sums are $1$, $3$, $6$, with remainders $1$, $0$, $0$, giving two distinct remainders, exceeding $\sqrt{3} \approx 1.732$. Small examples suggest the minimal number of distinct remainders is at least the integer part of $\sqrt{n}$, which aligns with the claim.
The core challenge is to rigorously show that for an arbitrary permutation, one cannot have fewer than $\sqrt{n}$ distinct remainders. If too many partial sums yield the same remainder modulo $n$, the sums must be spaced by multiples of $n$. This seems incompatible with the strict bounds of $1+\dots+n$. A potential approach is to interpret the problem combinatorially or geometrically: place $n$ points on a circle of length $n$ and consider the partial sums as moving along the circle. The key difficulty is quantifying the minimal number of distinct positions on this circle.
Problem Understanding
The problem asks to show that for any permutation $a_1,\dots,a_n$ of $1,\dots,n$, if $r_k$ denotes the remainder modulo $n$ of the $k$th partial sum $a_1+\dots+a_k$, then the set ${r_1,\dots,r_n}$ has at least $\sqrt{n}$ elements. This is a Type B problem, as the statement is universal and we are asked to prove it. The core difficulty lies in relating the additive structure of the permutation to a lower bound on distinct remainders. Intuitively, the cumulative sums grow too fast to allow too few remainders modulo $n$.
Proof Architecture
Lemma 1: No remainder $r$ can appear in more than $\lceil \sqrt{n} \rceil$ consecutive partial sums without exceeding $n$ when differences are taken. Sketch: If $r$ repeats $k$ times, the differences of partial sums equal multiples of $n$, which must sum to at least $1+2+\dots+n = n(n+1)/2$, bounding $k$.
Lemma 2: For any permutation, the differences between positions where the same remainder appears are multiples of $n$. Sketch: If $r_i \equiv r_j \pmod n$, then $a_{i+1}+\dots+a_j \equiv 0 \pmod n$, which is strictly positive and less than $n(n+1)/2$, bounding the spacing.
Main argument: Assume fewer than $\sqrt{n}$ distinct remainders exist; partition $n$ positions among these remainders; by the lemmas, the sum of differences exceeds $n(n+1)/2$, a contradiction. Hardest step: rigorously bounding the number of repetitions per remainder and showing it cannot cover all $n$ sums.
Solution
Let $r_1,\dots,r_n$ be the remainders of the partial sums modulo $n$. Suppose there are $d$ distinct remainders among them. Denote these remainders by $R_1,\dots,R_d$, and let $m_i$ be the number of times remainder $R_i$ appears among $r_1,\dots,r_n$, so that $m_1+\dots+m_d = n$. Consider indices $k_1<k_2<\dots<k_{m_i}$ where remainder $R_i$ appears. Then for each consecutive pair $k_j,k_{j+1}$, the sum $a_{k_j+1}+\dots+a_{k_{j+1}}$ is divisible by $n$ and strictly positive.
Each such sum is at least $1+2+\dots+(k_{j+1}-k_j) \ge k_{j+1}-k_j$, so the total sum of the permutation, $1+\dots+n = n(n+1)/2$, is at least the sum over all these blocks. Suppose $m_i > \sqrt{n}$ for some $i$; then there are at least $\sqrt{n}$ consecutive blocks, each summing to a multiple of $n$. The minimal sum of these $\sqrt{n}$ blocks is $1+2+\dots+\sqrt{n} = \frac{\sqrt{n}(\sqrt{n}+1)}{2} > n$ for $n>1$, which is impossible since the total sum is $n(n+1)/2$. Hence $m_i \le \sqrt{n}$ for all $i$.
Since $\sum_{i=1}^{d} m_i = n$, it follows that $d \ge n / \sqrt{n} = \sqrt{n}$. Therefore, the number of distinct remainders satisfies $d \ge \sqrt{n}$, as required. This completes the proof.
∎
Verification of Key Steps
The critical step is bounding $m_i \le \sqrt{n}$. Test small $n$ explicitly: for $n=4$, $1+2+3+4=10$, and consider remainder $0$. If it appears three times, then the consecutive sums must be multiples of $4$. The minimal such sums are $4,4,4$ totaling $12$, exceeding $10$, confirming the bound. Similarly for $n=9$, $\sqrt{9}=3$; no remainder can appear four times without the sum of corresponding blocks exceeding $45$, verifying the logic. The other delicate step is the conversion from block sums to total sum; the inequality $a_{k_j+1}+\dots+a_{k_{j+1}} \ge k_{j+1}-k_j$ is always valid, as each $a_i \ge 1$.
Alternative Approaches
A different approach interprets the partial sums modulo $n$ as a walk on the cyclic group $\mathbb{Z}_n$. The problem reduces to showing that a sequence of $n$ elements, each distinct modulo $n$, cannot concentrate on fewer than $\sqrt{n}$ residues without the cumulative differences exceeding $n(n+1)/2$. While this approach is elegant using additive combinatorics, it ultimately requires the same combinatorial bound on repetition counts. The main approach is preferable because it directly relates the permutation sums to minimal block sizes and yields an explicit numeric inequality, avoiding abstract group-theoretic machinery.