For each integer $n>0$, a permutation $a_1,a_2,\dots ,a_{2n}$ of $1,2,\dots 2n$ is called beautiful if for every $1\leq i<j \leq 2n$, $a_i+a_{n+i}=2n+1$ and $a_i-a_{i+1}\not \equiv a_j-a_{j+1}$ (mod $2n+1$) (suppose that $a_{2n+1}=a_1$). a. For $n=6$, point out a beautiful permutation. b. Prove that there exists a beautiful permutation for every $n$.
Problem
Source:
Tags: combinatorics
27.03.2017 07:59
any solution
27.03.2017 08:33
Well, here's one for part (a): $1,2,4,8,3,6,12,11,9,5,10,7$. That's $a_{i+1}\equiv 2a_i\mod 13$, so the $a_i-a_{i+1}\equiv -a_i$ are all different. A similar idea (start with a primitive root) would work whenever $2n+1$ is prime. That's not everything. I don't have part (b) yet.
27.03.2017 19:46
Finally, here is the construction for $n\equiv_4 1$; First, we denote $di(b_1,b_2,...,b_t)$ be the collection (or set) of "absolute value" of $b_i-b_{i+1}$ where $i=1,2,...,t-1$ Since $a_i-a_{i+1}=(2n+1-a_{i+n})-(2n+1-a_{i+n+1})=a_{i+n+1}-a_{i+n}$ for all $i=1,2,...,n-1$ So if we can construct the permutation for which $di(a_1,a_2,...,a_n)=\{ 1,2,3,...,n-1\}$, we'll get that $di(a_{n+1},a_{n+2},...,a_{2n})=\{ 1,2,...,n-1\}$. Let $n=4k+1$ where $k\in \mathbb{Z}^+$. The second condition will be reduced to $di(a_1,a_2,...,a_n)=\{ 1,2,...,n-1\}$ and $\{ a_n-a_{n+1},a_{2n}-a_1\} \equiv_{2n+1} \{ n,n+1\}$. Define $a_1,a_2,...,a_{2k}$ by $a_{2i-1}=3k+2-i$ and $a_{2i}=k+1+i$ for all $i=1,2,...,k$. Then define $a_{2k+1},a_{2k+2},...,a_{4k}$ by $a_{2k+2i-1}=i$ and $a_{2k+2i}=4k+2-i$ for all $i=1,2,...,k$ And define $a_{4k+1}=k+1$ For $a_{4k+2},a_{4k+3},...,a_{8k+2}$, we let $a_{n+i}=2n+1-a_i$ for all $i=1,2,...,n$. This way, we see that $a_1,a_2,...,a_{4k+1}$ is a permutation of $1,2,...,4k+1$ and $di(a_1,a_2,...,a_{4k+1})=\{ 1,2,...,4k\}$. Moreover, $a_{4k+1}-a_{4k+2}=(k+1)-((8k+3)-(3k+1))=-4k-1\equiv_{8k+3} 4k+2,a_{8k+2}-a_1=((8k+3)-(k+1))-(3k+1)=4k+1$ . This mean that $a_1,a_2,...,a_{8k+2}$ we defined is a permutation satisfy the given two conditions, and so it's beautiful. For example, when $n=9$, we have $7,4,6,5,1,9,2,8,3,12,15,13,14,18,10,17,11,16$ and when $n=13$, we have $10,5,9,6,8,7,1,13,2,12,3,11,4,27-10,27-5,...,27-4$. Comment: I strongly believed that we can similarly construct for other $n\not\equiv_4 1$ but maybe we have to change $a_1,a_n$ and other details. And this construction shows that, at least, we don't have to get any harder idea to construct the permutation than this "linear" construction.
27.03.2017 23:50
06.04.2017 11:24
I wonder if there are exactly 2*n! beautiful permutations.
14.10.2017 14:31
the4seasons wrote: I wonder if there are exactly 2*n! beautiful permutations. Unfortunetely , your statement was failed =)). Mr Tuan challenged me for that =)) Here are another solution , highly motived by IMO SL 2002
Attachments:


