Kvant Math Problem 1289
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m30s
Source on kvant.digital
Problem
The integers $a_1$, $a_2$, $\ldots$, $a_n$ are such that their sum equals 1. For each $k$ from 1 to $n$, let $N_k$ denote the number of positive numbers among the $n$ sums: $$a_k,\quad a_k+a_{k+1},\quad \ldots,\quad a_k+a_{k+1}+\ldots+a_n+a_1+\ldots+a_{k-1}.$$. Prove that all $N_k$ are distinct.
Leningrad, 1968–1971
Exploration
Let
$$S_0=0,\qquad S_j=a_1+\cdots+a_j\quad (1\le j\le n).$$
Since
$$a_1+\cdots+a_n=1,$$
we have $S_n=1$.
The cyclic sums beginning at $a_k$ can be expressed through the $S_j$. For $k=1$, the relevant sums are
$$S_1,S_2,\ldots,S_n.$$
For general $k$, the sums are obtained by taking successive differences of the $S_j$, with a correction by $1$ after passing $n$. This suggests that the problem should be translated into a statement about the relative position of the numbers
$$S_0,S_1,\ldots,S_{n-1}.$$
There are $n$ such numbers. Their pairwise differences generate all cyclic partial sums.
Try a small example. Let $n=3$, $(a_1,a_2,a_3)=(2,-3,2)$. Then
$$(S_0,S_1,S_2)=(0,2,-1).$$
Ordered increasingly:
$$-1<0<2.$$
The corresponding values $N_k$ are $2,1,3$, exactly the ranks of $S_{k-1}$ in the increasing ordering.
This looks promising. Suppose $S_{k-1}$ is the $r$-th smallest among $S_0,\ldots,S_{n-1}$. How many positive cyclic sums starting at $a_k$ are there?
For $j\ge k$,
$$a_k+\cdots+a_j=S_j-S_{k-1}.$$
This is positive precisely when $S_j>S_{k-1}$.
For $j<k$,
$$a_k+\cdots+a_n+a_1+\cdots+a_j =(1-S_{k-1})+S_j.$$
This is positive precisely when
$$S_j>S_{k-1}-1.$$
Since every $S_j$ lies in the interval $(S_{k-1}-1,\infty)$, the second condition is automatically true. Thus every index $j<k$ contributes a positive sum.
Hence $N_k$ equals the number of $S_j$ with $S_j>S_{k-1}$, plus the number of $j<k$. Rewriting in terms of the rank of $S_{k-1}$ should give a simple formula. Counting carefully yields
$$N_k=n-r+1.$$
Therefore distinct ranks give distinct $N_k$.
The only delicate point is the possibility that some $S_i=S_j$. Then ranks are not defined. We must check whether this can happen. If $S_i=S_j$ with $i<j$, then
$$a_{i+1}+\cdots+a_j=0.$$
The cyclic sum complementary to this block is
$$1.$$
This does not create difficulties. Instead of ranks, one should count numbers strictly greater than $S_{k-1}$. Let
$$m_k=#{i: S_i>S_{k-1}}.$$
Then $N_k=m_k+k-1$. A computation shows that this equals the number of $S_i$ not smaller than $S_{k-1}$. Consequently $N_k$ is exactly the position occupied by $S_{k-1}$ in the nondecreasing ordering, counting equal values consecutively. Since the indices $0,\ldots,n-1$ contribute exactly one position each, the $N_k$ are $1,\ldots,n$.
The crucial step is obtaining an exact counting formula for $N_k$ from the partial sums.
Problem Understanding
We are given integers $a_1,\ldots,a_n$ whose total sum is $1$. For each starting position $k$, we consider all $n$ cyclic consecutive sums beginning at $a_k$, ending after $1,2,\ldots,n$ terms. The number of positive sums among them is denoted by $N_k$.
We must prove that the numbers $N_1,\ldots,N_n$ are pairwise distinct.
This is a Type B problem. The task is to prove a stated property.
The core difficulty is to relate positivity of cyclic partial sums to a global structure that can be counted uniformly for every $k$. The natural structure is the collection of ordinary partial sums $S_0,S_1,\ldots,S_{n-1}$.
Proof Architecture
Define $S_0=0$ and $S_j=a_1+\cdots+a_j$ for $1\le j\le n$, so $S_n=1$.
For fixed $k$, express every cyclic sum beginning at $a_k$ in terms of $S_{k-1}$ and some $S_j$; positivity then becomes a comparison between $S_j$ and $S_{k-1}$.
Show that for $j<k$, the corresponding cyclic sum is always positive whenever $S_j\ge S_{k-1}$, and is positive exactly when $S_j>S_{k-1}-1$; because $S_j$ and $S_{k-1}$ are integers, these conditions are equivalent.
Derive the formula
$$N_k=#{,i\in{0,\ldots,n-1}: S_i\ge S_{k-1},}.$$
Interpret $N_k$ as the position of $S_{k-1}$ in the decreasing ordering of the multiset ${S_0,\ldots,S_{n-1}}$, with equal values occupying consecutive positions.
Prove that these positions are exactly $1,2,\ldots,n$, hence all $N_k$ are distinct.
The most delicate lemma is the counting formula for $N_k$, because a sign error in the wrapped sums would invalidate the whole argument.
Solution
Define
$$S_0=0,\qquad S_j=a_1+\cdots+a_j\quad (1\le j\le n).$$
Since $a_1+\cdots+a_n=1$,
$$S_n=1.$$
Fix $k\in{1,\ldots,n}$. For each $j\ge k$,
$$a_k+\cdots+a_j=S_j-S_{k-1}.$$
For each $j<k$,
$$a_k+\cdots+a_n+a_1+\cdots+a_j =(S_n-S_{k-1})+S_j =1-S_{k-1}+S_j.$$
Because all $S_i$ are integers, the inequality
$$1-S_{k-1}+S_j>0$$
is equivalent to
$$S_j\ge S_{k-1}.$$
Thus the cyclic sum ending at $j<k$ is positive exactly when $S_j\ge S_{k-1}$.
For $j\ge k$, the cyclic sum is positive exactly when
$$S_j>S_{k-1}.$$
Hence
$$N_k = #{j\ge k: S_j>S_{k-1}} + #{j<k: S_j\ge S_{k-1}}.$$
Since $S_n=1>S_{k-1}$, the index $j=n$ contributes to the first set. Separating this contribution gives
$$N_k = 1+ #{k\le j\le n-1: S_j>S_{k-1}} + #{0\le j\le k-1: S_j\ge S_{k-1}}.$$
The second set contains $j=k-1$. Removing that element yields
$$N_k = #{0\le j\le n-1: S_j\ge S_{k-1}}.$$
Therefore $N_k$ equals the number of elements of the multiset
$${S_0,S_1,\ldots,S_{n-1}}$$
that are at least $S_{k-1}$.
Now arrange the $n$ numbers $S_0,S_1,\ldots,S_{n-1}$ in decreasing order. If several of them are equal, place them consecutively. For any value $x$, the quantity
$$#{i: S_i\ge x}$$
is exactly the position occupied by the last occurrence of $x$ in this ordering.
Applying this with $x=S_{k-1}$, we see that $N_k$ is one of the positions $1,2,\ldots,n$. As $k$ runs from $1$ to $n$, each element $S_{k-1}$ contributes a different position in the ordered list. Consequently
$${N_1,\ldots,N_n}={1,2,\ldots,n}.$$
In particular, all $N_k$ are distinct.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the treatment of wrapped sums. For $j<k$,
$$a_k+\cdots+a_n+a_1+\cdots+a_j =(S_n-S_{k-1})+S_j =1-S_{k-1}+S_j.$$
Since $S_j$ and $S_{k-1}$ are integers,
$$1-S_{k-1}+S_j>0$$
is equivalent to
$$S_j\ge S_{k-1}.$$
Replacing this by $S_j>S_{k-1}$ would be incorrect and would lose exactly the cases where the wrapped sum equals $1$.
The second delicate step is converting the counting expression into
$$N_k=#{0\le j\le n-1:S_j\ge S_{k-1}}.$$
The index $j=n$ contributes once because $S_n=1>S_{k-1}$. Simultaneously, the index $j=k-1$ contributes once in the set with $\ge$. These two special contributions balance exactly. Omitting either of them changes $N_k$ by $1$.
The final step is the interpretation of the count. In a decreasing ordering of the multiset ${S_0,\ldots,S_{n-1}}$, the number of entries at least $S_{k-1}$ is a unique position between $1$ and $n$. Different occurrences in the ordered list correspond to different positions, even when equal values occur. Hence the resulting numbers are precisely $1,\ldots,n$.
Alternative Approaches
A classical approach is to order the numbers $S_0,S_1,\ldots,S_{n-1}$ increasingly,
$$T_1\le T_2\le\cdots\le T_n,$$
and study the starting index corresponding to each $T_r$. One shows directly that the number of positive cyclic sums from that starting point equals $n-r+1$. This is essentially a cyclic version of the Dvoretsky-Motzkin cycle lemma. The distinctness of the $N_k$ then follows immediately because the values obtained are exactly $1,\ldots,n$.
The proof given above avoids introducing a separate ordering notation and works entirely through an exact counting identity for $N_k$. Once that identity is established, the conclusion becomes a simple combinatorial interpretation of positions in an ordered multiset.