1) We consider the following permutation 1,2,4,8,3,6,12,11,9,5,10,7.
It is easy to check that 1+12=2+11=4+9=8+5=3+10=6+7. Furthermore, the difference between two consecutive numbers in modulo 13 in order are 1,2,4,8,3,6,12,11,9,5,10,7, which are all distinct. Therefore, this permutation is nice.
2) Let A be the set of nice permutations and B be the set of ways to put numbers 1,2,…,2n on the vertices of a regular polygon X1X2X3…X2n, in such a way that:
1. The sum of two numbers belonging to the endpoints of a diameter of the circumcircle of this polygon is 2n+1;
2. There is no consecutive sequence of numbers whose sum is divisible by 2n+1.
We shall prove that there is a bijection A→B and then, to prove the existence of the nice permutation, we just need to prove ∣A∣=∣B∣>0.
First step. There is a bijection from A to B.
Consider a nice permutation in A, namely (a1,a2,…,a2n) then for each i=1,2n, we choose bi∈{1,…,2n} such that bi≡ai+1−ai(mod2n+1). Then all numbers bi are pairwise distinct. We denote a2n+1=a1 and b2n+1=b1.
We put all these numbers onto the circle in that order, which means bi for Xi. It is easy to see that
bi+bi+n≡ai+1−ai+ai+1+n−ai+n=2(2n+1)≡0(mod2n+1).
Since 0<bi+bi+n<2(2n+1), we have bi+bi+n=2n+1. Furthermore, we also have
ai=(ai−ai−1)+(ai−1−ai−2)+⋯+(a2−a1)+a1=a1+k=1∑i−1bk
and ai are pairwise distinct modulo 2n+1, then there does not exist two indices i,j such that
aj−ai=k=i∑j−1bk≡0(mod2n+1).
Thus, the above way of placing bi satisfies the condition of B. Consider a way in B and bi is put on Xi, i=1,2n then consider the sequences
a1=b1,a2=b1+b2,a3=b1+b2+b3,…,ai=k=1∑ibk
and the sum is taken modulo 2n+1. Then, we can see that all numbers ai are positive and also pairwise distinct. Otherwise, suppose that there are some i=j such that ai=aj then
0=aj−ai=k=i∑j−1bk(mod2n+1),
which is a contradiction. Furthermore, bi+bi+n≡ai−ai−1+ai+n−ai+n−1≡0(mod2n+1) which implies that
ai+ai+n≡ai−1+ai+n−1(mod2n+1) for all i≥2.
Hence, the sums ai+ai+n for all i=1,2n have the remainders when divided by 2n+1 as a∈{0,1,2,…,2n}. Note that, there are 2n sums like that and they are pairwise non-overlapping then
k=1∑2nk=i=1∑2n(ai+ai+n)≡2na(mod2n+1),
but gcd(2n,2n+1)=1 then we need to have a=0 or ai+ai+n=2n+1 for all i=1,2n. This implies that ai is a nice permutation, which belongs to A. Then we can conclude that there is a bijection from A to B.
Second step. One can check that the number of ways to place numbers such that bi+bi+n=2n+1 for all i=1,2n is n!⋅2n (since numbers 1→2n belong to different pairs with the sum equal to 2n+1 and we also can swap two numbers on Xi,Xi+n). We denote the set of all these ways by S. Suppose that in some way of S, there is some consecutive sequence of length k whose sum is divisible by 2n+1 then k≥3 and if we denote Sk as the subset of S with k elements, we have n⋅2n−k⋅(n−k)!⋅Sk ways.
Indeed, we have n ways to choose the start position of the sequence (it is easy to see that k symmetric numbers with respect to the center of the polygon also satisfy that property), then there are 2n−2k remaining numbers which are free to distribute, and the number of ways to put is 2n−k⋅(n−k)!.
Thus, the number of ways such that bi+bi+n=2n+1 but the sum of some consecutive numbers is divisible by 2n+1 is not more than
S=nk=3∑n2n−k(n−k)!Sk.
We shall prove some estimations:
a) Sk≤k1C2nk−1. Note that there are exactly C2nk−1 subsets of size k−1 of the first 2n positive integers. For each set, there is no more than one way to add one more number such that the sum of these numbers is a multiple of 2n+1. On the other hand, for each subset of size k which has the sum as a multiple of 2n+1, there are exactly k subsets of size k−1 of the first 2n positive integers. Thus k⋅Sk≤1⋅C2nk−1.
b) C2nk−1≤4k−1Cn−1k−1 for all n≥5,k≥3,n≥k (and for n=1,2,3,4 we can point out a specific nice permutation). This can be proved by induction on n with the following inequality
C2nk÷Cn−1k=k2n−k+1C2nk−1÷kn−kCn−1k−1≤n−k2n−k+14k−1<4k.
c) 0!x0+1!x1+2!x2+⋯+n!xn<ex for all n.
Finally, we have
S≤nk=3∑n2n−k(n−k)!k1C2nk−1≤nk=3∑n2n−k(n−k)!k1Cn−1k−14k−1=2nn!41k=3∑nk!2k<2nn!4e2−(1+2+2)<2nn!.
Therefore, ∣B∣≥2nn!−S>0. This completes the proof.