Let $n$ be a positive integer and let $(a_1,a_2,\ldots ,a_{2n})$ be a permutation of $1,2,\ldots ,2n$ such that the numbers $|a_{i+1}-a_i|$ are pairwise distinct for $i=1,\ldots ,2n-1$. Prove that $\{a_2,a_4,\ldots ,a_{2n}\}=\{1,2,\ldots ,n\}$ if and only if $a_1-a_{2n}=n$.
Problem
Source: French TST 2002
Tags: absolute value, combinatorics proposed, combinatorics
20.06.2011 08:17
Call a pair $(a_i,a_{i+1})$ descent if $a_i > a_{i+1}$ and ascent otherwise. The absolute value of the difference is the value of the descent (ascent). Also, denote the set $\{n+1,n+2,...,2n\}$ group $A$ and the rest group $B$. We have some observations. 1) The difference $a_1-a_{2n}$ is the sum of the descents minus the sum of the ascents. 2) The set of differences of consecutive elements is $\{1,2,...,2n-1\}$. 3) The sum of the descents and ascents is $1+2+...+ 2n-1$. "If" part: if $a_1-a_{2n}=n$ then by 1) and 3) we have the sum of descents is $n^2$ and the sum of ascents is $n^2-n$. Let the descents be $(a_j,a_{j+1}), j \in J$ then the sum of descents is $\sum_{j\in J}a_j - \sum_{j\in J}a_{j+1}$. After we get rid of elements that appear on both sums, each has at most $n$ (but equal number of ) elements , hence the value is at most $2n+ (2n-1)+ ... (n+1) - (1+2+... n)= n^2$ with equality only if each element of group $A$ appear as the left element of the descent, and never as a right element of a descent. That means no two elements of group $A$ may be next to each other, because one of them would either not be a left element or be a right element (the smaller one). Because $a_1$ is in group $A$ and $a_{2n}$ is in group $B$, all the elements in group $A$ must have odd indices. "Only if" part: Because elements in group $A$ have odd indices, it follows that the sum of descents is $n^2$. By 3), the sum of ascents is $n^2-n$, and by 1) we have $a_1-a_{2n} = n$.