Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 $i\geq 2$.

share|improve this question
3  
Please don't call it "property $A_i$" - that sounds as if it would depend on $i$. –  darij grinberg Sep 29 '11 at 12:06
    
@darji: good point, I will edit the question. –  user952949 Sep 29 '11 at 12:16

2 Answers 2

This is IMO 1989 problem 6.

http://www.cs.cornell.edu/~asdas/imo/imo/isoln/isoln896.html

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

http://www.artofproblemsolving.com/Forum/download/file.php?id=16488 (if this link dies: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=177&t=15576 post #3).

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.

share|improve this answer

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}).$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.