Kvant Math Problem 1187

Let the required order be $a_1,a_2,\dots,a_{m-1}$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m53s
Source on kvant.digital

Problem

Prove that if $m$ is even, then all integers from 1 to $m-1$ can be arranged in an order such that no sum of several consecutive numbers is divisible by $m$.

F. G. Shleifer

City Tournament (Spring, 1989)

Exploration

Let the required order be $a_1,a_2,\dots,a_{m-1}$. A sum of consecutive terms from $a_i$ to $a_j$ equals

$$(a_1+\cdots+a_j)-(a_1+\cdots+a_{i-1}).$$

Hence no consecutive sum is divisible by $m$ if and only if all partial sums

$$s_k=a_1+\cdots+a_k \pmod m,\qquad k=0,1,\dots,m-1,$$

are distinct modulo $m$, where $s_0=0$.

Since there are exactly $m$ residue classes modulo $m$, distinctness means that the partial sums run through all residues modulo $m$.

For small values:

For $m=2$, the order $1$ works. The partial sums are $0,1$.

For $m=4$, the order $1,3,2$ gives partial sums $0,1,0,2$, which fails. Trying instead $1,2,3$ gives partial sums $0,1,3,2$, all distinct.

For $m=6$, the natural order $1,2,3,4,5$ gives partial sums $0,1,3,0,4,3$, which fails. The successful example $1,2,5,4,3$ gives

$$0,1,3,2,0,3,$$

which also fails.

Trying to understand the successful case $m=4$, the partial sums were exactly all residues. This suggests constructing the partial sums first and then taking differences.

Suppose $m=2n$. If the partial sums are arranged as

$$0,1,m-1,2,m-2,3,m-3,\dots,n,$$

then every residue modulo $m$ appears exactly once. Consecutive differences are

$$1,,-2,,3,,-4,,5,,-6,\dots$$

modulo $m$. Their absolute values are

$$1,2,3,\dots,m-1.$$

Thus the differences are precisely the numbers $1,2,\dots,m-1$ in some order. This looks promising.

The crucial point is to verify rigorously that these differences indeed produce every nonzero residue exactly once and that distinct partial sums imply the required property about consecutive sums.

Problem Understanding

We must arrange the integers $1,2,\dots,m-1$, where $m$ is even, into an order such that no sum of a block of consecutive terms is divisible by $m$.

This is a Type D problem. We must construct an arrangement and verify that it satisfies the required property.

The core difficulty is to encode all consecutive sums simultaneously. Passing to partial sums converts the condition into a statement about distinct residues modulo $m$. The task then becomes the construction of a sequence of partial sums whose successive differences are exactly the numbers $1,2,\dots,m-1$.

An intuitive idea is to prescribe the partial sums themselves as an alternating list of small and large residues,

$$0,1,m-1,2,m-2,\dots,$$

because consecutive differences then generate all nonzero residues modulo $m$.

Proof Architecture

The first lemma is that no consecutive sum is divisible by $m$ if and only if the partial sums modulo $m$ are pairwise distinct. This follows because every consecutive sum is the difference of two partial sums.

The second lemma is that the residues

$$0,1,m-1,2,m-2,\dots,\frac m2$$

are pairwise distinct and exhaust all residue classes modulo $m$. This follows directly from their form.

The third lemma is that consecutive differences of the sequence in the second lemma are congruent to

$$1,-2,3,-4,\dots,m-1$$

modulo $m$. Hence these differences are exactly the nonzero residues modulo $m$.

The hardest point is proving that the differences really give every nonzero residue exactly once. A mistake here would invalidate the construction.

Solution

Let

$$m=2n.$$

Consider the sequence of residues modulo $m$

$$s_0=0,\quad s_1=1,\quad s_2=m-1,\quad s_3=2,\quad s_4=m-2,\dots,\quad s_{m-1}=n.$$

In other words,

$$s_{2k-1}=k,\qquad s_{2k}=m-k$$

for $1\le k\le n-1$, and $s_{m-1}=n$.

These $m$ numbers are precisely

$$0,1,2,\dots,n,m-1,m-2,\dots,n+1,$$

written in a different order. Hence they are pairwise distinct modulo $m$ and represent all residue classes modulo $m$.

Define

$$a_i\equiv s_i-s_{i-1}\pmod m, \qquad 1\le i\le m-1,$$

and choose for each $a_i$ its representative from the set ${1,2,\dots,m-1}$.

We compute these differences.

For $1\le k\le n-1$,

$$a_{2k-1}\equiv s_{2k-1}-s_{2k-2} =k-(m-(k-1)) =2k-1-m \equiv 2k-1 \pmod m.$$

Also,

$$a_{2k}\equiv s_{2k}-s_{2k-1} =(m-k)-k =m-2k \equiv -2k \pmod m.$$

Since $0<m-2k<m$, this representative is exactly $m-2k$.

Finally,

$$a_{m-1}=s_{m-1}-s_{m-2} =n-(m-(n-1)) =2n-m-1 =m-1.$$

Therefore

$$a_1,a_2,\dots,a_{m-1} = 1,\ m-2,\ 3,\ m-4,\ 5,\ m-6,\dots,\ m-1.$$

The odd-indexed terms are

$$1,3,5,\dots,m-1,$$

and the even-indexed terms are

$$m-2,m-4,\dots,2.$$

Together they are exactly the integers $1,2,\dots,m-1$, each occurring once.

By construction,

$$s_k\equiv a_1+\cdots+a_k\pmod m$$

for every $k$. Since the residues $s_0,s_1,\dots,s_{m-1}$ are pairwise distinct, let us show that no consecutive sum is divisible by $m$.

Suppose a consecutive block from $a_i$ to $a_j$ had sum divisible by $m$. Then

$$a_i+\cdots+a_j\equiv0\pmod m.$$

Using partial sums,

$$(s_j-s_{i-1})\equiv0\pmod m,$$

so

$$s_j\equiv s_{i-1}\pmod m.$$

This contradicts the pairwise distinctness of the residues $s_0,s_1,\dots,s_{m-1}$.

Hence no sum of several consecutive terms is divisible by $m$.

The required arrangement is

$$\boxed{1,\ m-2,\ 3,\ m-4,\ 5,\ m-6,\ \dots,\ m-1}.$$

Verification of Key Steps

The first delicate step is the equivalence between consecutive sums and partial sums. For indices $i\le j$,

$$a_i+\cdots+a_j = (a_1+\cdots+a_j)-(a_1+\cdots+a_{i-1}) = s_j-s_{i-1}.$$

Thus a consecutive sum is divisible by $m$ exactly when two partial sums are congruent modulo $m$. Any argument that checks only adjacent partial sums would miss longer blocks.

The second delicate step is the computation of the differences. For odd indices,

$$s_{2k-1}=k,\qquad s_{2k-2}=m-(k-1),$$

hence

$$s_{2k-1}-s_{2k-2}\equiv2k-1\pmod m.$$

For even indices,

$$s_{2k}-s_{2k-1}=m-2k.$$

These values are respectively all odd numbers and all positive even numbers below $m$. Together they form exactly the set ${1,2,\dots,m-1}$.

The third delicate step is verifying that the residues $s_0,\dots,s_{m-1}$ are all distinct. The sequence contains every number from $0$ to $n$ and every number from $n+1$ to $m-1$ exactly once. Since there are $m$ terms and $m$ residue classes modulo $m$, no repetition occurs.

Alternative Approaches

A different approach starts from the cyclic group $\mathbb Z_m$. One seeks a Hamiltonian path through all residues such that the successive edge labels are precisely the nonzero elements of the group. If such a path exists, its edge labels give the desired ordering. For even $m$, the path

$$0,1,m-1,2,m-2,\dots,\frac m2$$

has exactly this property. The proof then proceeds in the language of group differences.

Another approach constructs the ordering directly as

$$1,m-2,3,m-4,\dots,m-1$$

and computes the partial sums explicitly. The partial sums alternate between small residues and large residues,

$$1,\ m-1,\ 2,\ m-2,\dots,$$

which are all distinct modulo $m$. This yields the same construction, but the proof through prescribed partial sums makes the structure of the argument more transparent.