Vrftsjtryk

For any positive integer $n$, a permutation $(x_1,x_2,ldots,x_{2n})$ of the set ${1,2,ldots,2n}$ satisfies the property $A$ iff for at least one $i$ in ${1,2,ldots,2n-1}$ , $|x_i - x_{i+1}|=n$.

I.e. If the difference between adjacent numbers in a permutation is equal to $n$, then this permutation has the property in the $i^text{th}$ position.

Example: For $n = 3$,
$(1,5,2,3,4,6)$ has the property (because $x_2=5$ and $x_3 = 2$ are next to each other and
$|x_2 - x_3| = |5 - 2| = 3$); similarly $(6,3,1,2,4,5)$ has the property. However, $(1,2,3,4,5,6)$ does not have the property.

I need to prove the following statement:
There are at least as many permutations with the property than permutations without it.

Can someone please point me towards how to go about this?

I tried this for small cases and can see how it is true.

I had the idea to first define an algorithm which generates all the possible permutations. Then show that the transposition from one permutation to another produces elements which are adjacent to each other and the difference between them is $n$.

The question suggests to show a bijection between the permutations that do not have this property to the permutations that do have this property, for exactly one $igeq 2$.

This is IMO 1989 problem 6.

https://web.archive.org/web/20130728125728/http://www.cs.cornell.edu/~asdas/imo/imo/isoln/isoln896.html [Note that the "this is an alternating sequence of monotonically decreasing terms" argument requires a rather subtle re-interpretation of the sum. But alternatively, the conclusion $left|Aright| geq sum_k left|A_kright| - sum_{k<l} left|A_k cap A_lright|$ can be obtained from the Bonferroni inequalities for $k=2$.]

http://www.artofproblemsolving.com/Forum/viewtopic.php?p=372274

http://www.artofproblemsolving.com/Forum/viewtopic.php?f=177&t=15576 post #3 (the djvu file in that post).

Not all of the solutions above are correct, but some are. Note that the third link is to the official solution, which is somewhat more complicated than the solutions we have nowadays, but probably the most natural approach to the question.

Here’s an argument using the hint. The initial version was flawed, as darij pointed out last night, so I deleted it and went to bed. On waking up I realized how to repair it; I’ve kept both to show how one might get from the flawed version to one that works.

Suppose that the permutation $(x_1,x_2,dots,x_{2n})$ does not have the property. Consider the number $x_2$; exactly one of the numbers $x_2+n$ and $x_2-n$ is in the set ${1,2,dots,2n}$ (why?), and that number isn’t $x_1$ or $x_3$ (why?), so it’s $x_k$ for some $k>3$. Interchange $x_3$ and $x_k$.

• Does the resulting permutation satisfy $A$?




• If $(x_1,x_2,dots,x_{2n})$ and $(y_1,y_2,dots,y_{2n})$ are different permutations of ${1,2,dots,2n}$ not having the property, and we perform this operation on both of them, do we always get different permutations?

Unfortunately, as darij pointed out, the answer to the second question is no, because after the interchange we can’t tell where the new third element came from. For example, $(1,2,3,4,5,6)$, $(1,2,3,5,4,6)$, and $(1,2,3,4,6,5)$ all produce $(1,2,5,3,4,6)$.

The trick is to reverse the idea: instead of creating the adjacent pair differing by $n$ in a known place, create it by moving something from a known place. Specifically, there is a unique $k>2$ such that $x_k$ is either $x_1+n$ or $x_1-n$ (why?); move $x_1$ to the position immediately after $x_k$. The adjacent pair $(x_k,x_1)$ ensures that the resulting permutation has the property, and the operation is reversible: if a permutation has exactly one adjacent pair $(x_i,x_{i+1})$ witnessing the property, where $i>1$, it can only have come from the pair obtained by moving $x_{i+1}$ to the beginning of the permutation to get $$(x_{i+1},x_2,dots,x_i,x_{i+2},dots,x_{2n}).$$