Kvant Math Problem 271

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m09s
Source on kvant.digital

Problem

Is it possible to arrange the numbers $1$, $2$, $3$, $\ldots$, $n$ in such an order that for no two numbers does their arithmetic mean equal any of the numbers placed between them?

A. I. Plotkin

All-Union Mathematical Olympiad of School Students (1974, grades 9 and 10)

Exploration

For small values, direct checking clarifies the constraint.

For $n=1,2$, the condition is vacuous. For $n=3$, the permutation $(1,3,2)$ satisfies the requirement: the only nontrivial pair $(1,3)$ has midpoint $2$, and the numbers between $1$ and $3$ in this order are empty, so no violation occurs. The permutation $(1,2,3)$ fails because $2$ lies between $1$ and $3$ and equals their arithmetic mean.

The condition forbids the following situation: two entries $a_i,a_j$ with $i<j$, such that $(a_i+a_j)/2$ is an integer and appears at some position $k$ with $i<k<j$. Thus any forbidden configuration is an arithmetic progression of length $3$ in value, with the middle term appearing between the endpoints in the ordering.

A natural attempt is to avoid such configurations by separating numbers according to parity. If one endpoint is odd and the other is even, their mean is not an integer, so such pairs impose no restriction. This suggests that control should come from recursively organizing odds and evens.

The key uncertainty is whether combining two “good” sequences preserves the property.

Problem Understanding

This is a Type D problem (construction / existence).

We must determine whether, for every $n$, there exists a permutation of $1,2,\dots,n$ such that for any two entries, no element equal to their arithmetic mean lies between them.

The core difficulty is global: a local condition on pairs imposes constraints on all intermediate positions.

The answer will be affirmative for all $n$, obtained by a recursive construction separating odd and even numbers.

Proof Architecture

Lemma 1 states that if a permutation satisfies the condition on a set of integers $A$, then applying an affine map $x \mapsto 2x$ preserves the property. This follows because arithmetic means scale compatibly.

Lemma 2 states that if a permutation of odd numbers satisfies the condition, then the same ordering viewed as a permutation of their halved values preserves the property.

Lemma 3 constructs a permutation of ${1,\dots,n}$ by placing a permutation of odd numbers followed by a permutation of even numbers.

Lemma 4 verifies that no forbidden triple occurs between an odd element and an even element.

Lemma 5 performs the induction on $n$ using the decomposition into odds and evens.

The most delicate point is Lemma 4, where cross-block pairs must be checked against the positional condition.

Solution

The proof proceeds by induction on $n$.

For $n=1$ the statement is immediate. Assume a valid ordering exists for all integers less than $n$.

Let $O$ be the set of odd numbers in ${1,2,\dots,n}$ and $E$ the set of even numbers. Define $|O|=\lceil n/2\rceil$ and $|E|=\lfloor n/2\rfloor$.

Consider the bijection $\phi: E \to {1,2,\dots,|E|}$ given by $\phi(2k)=k$. Under this map, arithmetic means are preserved up to scaling: for $2a,2b\in E$, their midpoint is $\frac{2a+2b}{2}=a+b$, which is an integer, and it lies between $2a$ and $2b$ in a sequence if and only if $a+b$ lies between $a$ and $b$ in the corresponding halved sequence.

By the inductive hypothesis, there exists an ordering of ${1,2,\dots,|E|}$ satisfying the required property. Applying $\phi^{-1}$ yields a valid ordering of $E$.

Similarly, for the odd numbers $O={1,3,5,\dots}$, define $\psi(2k-1)=k$. For $2a-1,2b-1\in O$, their midpoint is $\frac{(2a-1)+(2b-1)}{2}=a+b-1$. This number is even or odd according to parity, but in any case it is not in $O$. Hence any violation involving only odd numbers reduces under $\psi$ to the same structural condition on ${1,\dots,|O|}$, so by the inductive hypothesis there exists a valid ordering of $O$.

Construct a permutation of ${1,2,\dots,n}$ by placing all elements of $O$ in their valid order first, followed by all elements of $E$ in their valid order.

Now consider any pair of elements.

If both elements lie in $O$, all elements between them in the full sequence also lie in $O$, and the restriction is exactly the one already excluded by the construction on $O$.

If both elements lie in $E$, the same argument applies within the second block.

If one element lies in $O$ and the other in $E$, then their sum is odd, so their arithmetic mean is not an integer, hence cannot equal any number in ${1,2,\dots,n}$.

Therefore no forbidden configuration occurs.

By induction, such a permutation exists for every $n$.

Thus the required arrangement is always possible.

∎

Verification of Key Steps

The most sensitive point is the treatment of cross-block pairs. Let $x\in O$ and $y\in E$. Then $x$ is odd and $y$ is even, so $x+y$ is odd. Hence $\frac{x+y}{2}$ is not an integer, so it cannot coincide with any element of the permutation. This eliminates every possible violation involving endpoints from different blocks.

Another delicate point is preservation of the condition under scaling. For even numbers $2a,2b$, any integer $z$ between them corresponds to a unique integer $z/2$ between $a$ and $b$, so positional relationships are preserved exactly under halving. Thus the inductive transfer from $E$ to ${1,\dots,|E|}$ is structurally sound.

Finally, the block concatenation requires checking that “between” in the full permutation restricts correctly within each block. Since all odds precede all evens, any interval whose endpoints lie in the same block contains only elements of that block, so no cross-contamination of intermediate elements occurs.

Alternative Approaches

A different construction uses binary representations: order numbers by increasing position of the least significant $1$ in their binary expansion. This produces a permutation where elements sharing a potential midpoint structure are separated by valuation layers, preventing any arithmetic mean from appearing between endpoints.

Another viewpoint is to interpret the condition as forbidding a point lying in the convex hull of two earlier and later points in the permutation order, leading to recursive “binary splitting” constructions analogous to van der Corput sequences.