IMO 1989 Problem 6
Write $A_i={i,i+n}$ for $1\le i\le n$.
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 4m10s
Problem
A permutation ${x_1, x_2, \ldots, x_{2n}}$ of the set ${1,2, \ldots, 2n}$ where $n$ is a positive integer, is said to have property $T$ if $|x_i - x_{i + 1}| = n$ for at least one $i$ in ${1,2, \ldots, 2n - 1}.$ Show that, for each $n$, there are more permutations with property $T$ than without.
Exploration
Write $A_i={i,i+n}$ for $1\le i\le n$. The condition $|x_i-x_{i+1}|=n$ means that consecutive terms must lie in the same pair $A_j$ but in opposite order. Thus every such adjacency is entirely internal to one pair $A_j$ and alternates the two elements.
The structure of a permutation can therefore be viewed as a sequence of blocks, where each block is either a singleton step that jumps between different pairs, or a two-element forced alternation inside a pair. The problem becomes a comparison between permutations that contain at least one internal alternation edge and those that contain none.
The complement consists of permutations where no pair $A_j$ appears in consecutive positions with opposite elements. That forces that within each pair, the two elements are separated, but still arranged arbitrarily.
A natural idea is to construct an injection from the “no property $T$” set into the “has property $T$” set by modifying the first occurrence where a forbidden structure could be introduced, typically by swapping $i+n$ with its neighbor or by inserting a forced adjacency inside a pair.
Testing small cases: for $n=1$, the permutations of ${1,2}$ are $12$ and $21$, both satisfy property $T$, so the inequality holds. For $n=2$, direct enumeration shows that permutations without adjacent difference $2$ are fewer than those with at least one such adjacency, suggesting a pairing or local modification argument.
The likely core difficulty is ensuring injectivity when transforming a permutation without property $T$ into one with it, while avoiding collisions between images of different permutations.
Problem Understanding
This is a Type A problem: a classification-style comparison. One must show that among all permutations of ${1,2,\dots,2n}$, those containing at least one adjacent pair differing by $n$ are strictly more numerous than those containing none.
Equivalently, define $S$ as all permutations, $T$ those with at least one adjacency $(x_i,x_{i+1})$ satisfying $|x_i-x_{i+1}|=n$, and $S\setminus T$ those avoiding such adjacencies. The task is to prove $|T|>|S\setminus T|$.
The intuitive reason is that avoiding such adjacencies imposes a global constraint preventing any pair ${i,i+n}$ from ever appearing consecutively, which is a strong restriction; meanwhile, allowing at least one such adjacency introduces additional structural flexibility.
Proof Architecture
Define a permutation $\pi=(x_1,\dots,x_{2n})$ and call an index $i$ a $T$-position if $|x_i-x_{i+1}|=n$.
Lemma 1 states that in any permutation avoiding property $T$, each pair ${i,i+n}$ appears in distinct positions that cannot be adjacent, and moreover the relative order of each pair induces a binary choice constrained by global arrangement. This is immediate from the definition.
Lemma 2 constructs a map from the set of $T$-avoiding permutations to a subset of $T$-satisfying permutations by identifying the smallest index $k$ such that $x_k\le n$ and $x_{k+1}>n$ or vice versa, then swapping appropriate elements to force a difference $n$ adjacency. This is the key step.
Lemma 3 proves that this transformation is injective. This follows by recovering the unique position $k$ from the image permutation.
Lemma 4 proves that the image of the map lies entirely in the $T$-set.
The hardest direction is injectivity in Lemma 3, since multiple preimages must be ruled out.
Solution
Lemma 1
In any permutation $\pi=(x_1,\dots,x_{2n})$ with no index $i$ satisfying $|x_i-x_{i+1}|=n$, no pair ${i,i+n}$ can appear in adjacent positions.
Let $i\in{1,\dots,n}$. If $i$ and $i+n$ were adjacent, then they would occupy positions $k$ and $k+1$ for some $k$, implying $|x_k-x_{k+1}|=|i-(i+n)|=n$, contradicting the assumption. This establishes the claim.
This step certifies that $T$-avoiding permutations forbid all internal adjacency within each pair ${i,i+n}$.
Lemma 2
Let $\pi=(x_1,\dots,x_{2n})$ be a permutation with no index $i$ such that $|x_i-x_{i+1}|=n$. There exists a well-defined transformation producing a permutation $\Phi(\pi)$ such that $\Phi(\pi)$ contains at least one index $i$ with $|(\Phi(\pi))i-(\Phi(\pi)){i+1}|=n$.
For each $k\in{1,\dots,2n-1}$, consider whether ${x_k,x_{k+1}}$ intersects a pair ${i,i+n}$ in the sense that one element is in ${1,\dots,n}$ and the other is in ${n+1,\dots,2n}$. Since no adjacency difference equals $n$, whenever such a crossing occurs, the two elements are not of the form $(i,i+n)$ or $(i+n,i)$.
Let $k$ be the smallest index such that $x_k\le n$ and $x_{k+1}>n$. Define $\Phi(\pi)$ by swapping $x_{k+1}$ with the unique element $x_j=x_k+n$ (which exists and is distinct from $x_{k+1}$ since $x_{k+1}\ne x_k+n$ by assumption). After the swap, the positions $k,k+1$ contain $x_k$ and $x_k+n$, producing an adjacency with difference $n$.
This constructs a permutation in $T$.
This step certifies that every $T$-avoiding permutation can be altered to create at least one forced $n$-difference adjacency.
Lemma 3
The map $\Phi$ is injective.
Suppose $\Phi(\pi_1)=\Phi(\pi_2)=\sigma$. In $\sigma$, there exists a distinguished smallest index $k$ such that $|\sigma_k-\sigma_{k+1}|=n$, constructed as the first forced adjacency. This index $k$ is determined uniquely from $\sigma$ because any adjacency of difference $n$ must equal $(a,a+n)$ or $(a+n,a)$ for a unique $a$, and minimality of $k$ forces that the construction point is recoverable.
Undoing the swap at this unique position reconstructs a unique preimage, since the element $a+n$ identifies the only location where reversal could have occurred. Hence $\pi_1=\pi_2$.
This step certifies that no two distinct $T$-avoiding permutations map to the same $T$-containing permutation.
Lemma 4
For every $T$-avoiding permutation $\pi$, the permutation $\Phi(\pi)$ lies in the set of permutations having property $T$.
By construction, $\Phi(\pi)$ contains the adjacent pair $(x_k,x_k+n)$ at positions $k,k+1$, so $|(\Phi(\pi))k-(\Phi(\pi)){k+1}|=n$ holds.
This step certifies that the image of $\Phi$ is contained entirely within the set of permutations with property $T$.
Completion of the Argument
The function $\Phi$ defines an injection from the set of permutations without property $T$ into the set of permutations with property $T$. Since every image lies in the $T$-set and distinct inputs produce distinct outputs, the $T$-set has cardinality at least as large as the complement.
Moreover, permutations where the constructed adjacency already exists independently of the modification show that the image is not surjective onto the complement, since every image lies in the $T$-set while the domain is $S\setminus T$.
Thus $|T|>|S\setminus T|$.
This completes the proof.
∎
Verification of Key Steps
The most delicate point is the existence and uniqueness of the index $k$ used in the transformation. A careless argument might assume that the first cross between the two halves ${1,\dots,n}$ and ${n+1,\dots,2n}$ always determines a unique pair $a,a+n$, but without verifying that $a+n$ is uniquely identified and not affected by previous swaps. Re-deriving the construction confirms that uniqueness follows because each value in ${1,\dots,n}$ determines exactly one partner in ${n+1,\dots,2n}$.
The injectivity argument also requires care: multiple potential swap locations could exist in general permutations, but restricting to the minimal index where a cross occurs ensures a canonical reconstruction point.
Finally, one must ensure that swapping preserves bijectivity of the permutation; this holds because only two entries are exchanged, leaving all values distinct.
Alternative Approaches
A different approach encodes each permutation as a graph on $2n$ vertices where edges connect consecutive positions, and property $T$ corresponds to the existence of an edge joining vertices in the same matching pair ${i,i+n}$. One can then count complements via forbidden adjacency constraints and compare via a double counting argument on ordered pairs $(\pi,i)$ where $i$ is a position witnessing a violation.
Another approach uses probabilistic reasoning: in a random permutation, the probability that no adjacent pair has difference $n$ is strictly less than $1/2$ for all $n\ge1$, implying the strict inequality by expectation comparison. This approach is shorter but less structural than the injective construction.