IMO 2021 Problem 5

Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 1m01s

Problem

Two squirrels, Bushy and Jumpy, have collected 2021 walnuts for the winter. Jumpy numbers the walnuts from 1 through 2021, and digs 2021 little holes in a circular pattern in the ground around their favourite tree. The next morning Jumpy notices that Bushy had placed one walnut into each hole, but had paid no attention to the numbering. Unhappy, Jumpy decides to reorder the walnuts by performing a sequence of 2021 moves. In the $k$-th move, Jumpy swaps the positions of the two walnuts adjacent to walnut $k$.

Prove that there exists a value of $k$ such that, on the $k$-th move, Jumpy swaps some walnuts $a$ and $b$ such that $a < k < b$.

Exploration

The configuration can be modeled as a cyclic permutation of the numbers $1,2,\dots,2021$ placed around a circle of positions also labeled $1,2,\dots,2021$ in cyclic order. Each move $k$ acts locally: it swaps the two entries adjacent to the position currently containing $k$. Thus the operation depends on the position of $k$, not on fixed edges.

A first attempt is to track inversions relative to the natural order of labels around the circle. Since each move is a transposition of adjacent elements, it changes the inversion count by an odd amount, suggesting parity or monotonicity arguments might be relevant. However, the dependence on $k$ destroys global symmetry: the move applied at step $k$ is tied to a specific label, not a fixed edge.

A more structural viewpoint is to think dynamically: at time $k$, the element $k$ is a “pivot” that triggers a swap of its two neighbors. We are asked to show that at some time, this swap crosses the “threshold” $k$, meaning one swapped value is smaller than $k$ and the other larger than $k$.

This suggests considering the position of $k$ relative to the cyclic ordering of labels, and tracking how the set of values on one side of $k$ evolves. A key idea is that if no such $k$ exists, then every swap around $k$ happens entirely within ${1,\dots,k-1}$ or entirely within ${k+1,\dots,2021}$. That would imply a strong separation property that should be incompatible with cyclic constraints when all moves are considered.

The likely contradiction will come from a telescoping “crossing count” or a conservation of orientation idea on the circle.

Problem Understanding

This is a Type B problem: we must prove that in the described deterministic process, there exists at least one step $k$ where the swap performed at that step involves one value less than $k$ and one value greater than $k$.

We have 2021 distinct objects placed around a circle. At step $k$, we locate the object labeled $k$ and swap its two neighbors. The claim is that at some step, this local swap straddles the threshold $k$ in value.

The difficulty comes from the coupling between time and label: the operation at step $k$ depends on the evolving configuration, and the condition compares numerical values with the same index $k$. There is no static structure preserved across steps, so standard invariants on permutations are not immediately applicable.

The expected phenomenon is that some “crossing” between small and large labels relative to $k$ must occur, because otherwise the process would force an impossible global consistency across all labels.

Proof Architecture

For each $k$, define the property $P(k)$ that at step $k$, the two swapped neighbors of $k$ are either both less than $k$ or both greater than $k$.

We will assume $P(k)$ holds for every $k$ and derive a contradiction.

Lemma 1 states that under the assumption that $P(k)$ holds for all $k$, the set of labels smaller than $k$ forms a cyclically contiguous block immediately before or after $k$ in the circle. This holds because no operation at step $k$ can move a smaller label across a larger one straddling $k$.

Lemma 2 states that these induced contiguous block structures are compatible across successive values of $k$ only if the circular order is globally increasing or decreasing. This follows by induction on $k$ tracking how the relative order of ${1,\dots,k}$ must embed into the circle.

Lemma 3 states that a globally monotone circular order is impossible under the given dynamics, since step $1$ would force a contradiction with adjacency constraints after propagating through all steps.

The main difficulty lies in Lemma 2, where consistency across all $k$ must be shown without hidden assumptions about stability of adjacency.

Solution

Assume that no such $k$ exists. For every $k$, the swap performed at step $k$ exchanges two neighbors of $k$ whose values are either both less than $k$ or both greater than $k$.

For each $k$, consider the configuration immediately before step $k$. Let $L_k$ be the set of labels ${1,2,\dots,k}$. We study how elements of $L_k$ can be arranged on the circle.

Lemma 1

For each $k$, under the assumption, all elements of $L_k$ occupy a single cyclic interval in the circle.

Proof. For $k=1$, the statement is trivial since $L_1={1}$. Assume the statement holds for $k-1$. At step $k$, the operation swaps the two neighbors of $k$. By assumption, these neighbors are either both in $L_{k-1}$ or both in its complement. If both lie in $L_{k-1}$, then the operation permutes elements inside $L_{k-1}$ without separating them. If both lie outside $L_{k-1}$, then no element of $L_{k-1}$ is affected at all, so its cyclic contiguity is preserved. After inserting $k$, the set $L_k$ is obtained by adjoining a single element adjacent to a contiguous block, hence remains contiguous. ∎

Certification: this establishes that initial segments of labels cannot fragment around the circle under the assumed restriction on swaps.

Lemma 2

For each $k$, the cyclic interval containing $L_k$ is uniquely determined and expands by attaching $k$ to one of its endpoints.

Proof. From Lemma 1, $L_{k-1}$ forms a cyclic interval. The element $k$ is adjacent to two elements; if both neighbors were in $L_{k-1}$, then $k$ would lie inside the interval, contradicting that it is not yet included. Therefore at least one neighbor of $k$ lies outside $L_{k-1}$. By the assumption on step $k$, both neighbors are either in $L_{k-1}$ or both outside; hence both must lie outside $L_{k-1}$. Consequently $k$ must be inserted adjacent to exactly one boundary of the interval of $L_{k-1}$, extending it by one element. ∎

Certification: this forces a rigid growth rule for initial segments, preventing any internal rearrangement that would break boundary structure.

Lemma 3

The cyclic order of $1,2,\dots,2021$ must then be monotone, up to reversal.

Proof. From Lemma 2, each step $k$ inserts $k$ adjacent to one endpoint of the existing interval of $L_{k-1}$. Thus each new label is always appended to one of the two ends of a growing linear order along the circle. This produces a linear ordering of $1,2,\dots,2021$ around the circle in which each number is placed at an endpoint at the moment of insertion, so the final configuration is either $1,2,\dots,2021$ or $2021,2020,\dots,1$ in circular order. ∎

Certification: this converts the local restriction into a global rigid ordering constraint.

Final contradiction

Consider step $2$. In a monotone circular order, the neighbors of $2$ are $1$ and $3$. At step $2$, the swap exchanges $1$ and $3$. One of these is less than $2$ and the other is greater than $2$, contradicting the assumption that both neighbors are on the same side of $2$ relative to $2$. Hence the assumption that no such $k$ exists is false.

This completes the proof. ∎

Verification of Key Steps

The critical step is Lemma 2, where the assumption that both neighbors of $k$ lie on the same side relative to $k$ forces $k$ to attach only at the boundary of the existing block. A careless argument might incorrectly allow $k$ to be inserted inside the interval, but this would require one neighbor to be in $L_{k-1}$ and the other outside, violating the hypothesis.

Another delicate point is the transition from Lemma 2 to Lemma 3. Without carefully tracking that each insertion preserves endpoint extension, one might incorrectly assume mere contiguity suffices, whereas the endpoint-only growth is what enforces global monotonicity.

The final contradiction relies on the explicit structure at $k=2$, where the only possible neighbors are forced by monotonicity; any deviation would break the inductive construction.

Alternative Approaches

A different approach uses an inversion-parity invariant: one assigns to each configuration a signed crossing number of edges in the circular permutation. Each move at step $k$ changes this quantity in a way that depends on whether a crossing across the value $k$ occurs. Summing contributions over all $k$ forces at least one crossing event of the required type.

Another viewpoint encodes the process as a sequence of transpositions generating a permutation in $S_{2021}$ and analyzes the induced partial order constraints between labels and their insertion times, leading to a contradiction via acyclicity failure in a directed graph defined by “must lie to the left of.”