Vietnamese Team Selection Test for IMO

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, \dots, 2n$ on the vertices of a regular polygon $X_1X_2X_3\dots X_{2n}$, 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 \to 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 $(a_1, a_2, \dots, a_{2n})$ then for each $i = \overline{1, 2n}$, we choose $b_i \in \{1, \dots, 2n\}$ such that $b_i \equiv a_{i+1} - a_i \pmod{2n+1}$. Then all numbers $b_i$ are pairwise distinct. We denote $a_{2n+1} = a_1$ and $b_{2n+1} = b_1$.

We put all these numbers onto the circle in that order, which means $b_i$ for $X_i$. It is easy to see that
$$b_i + b_{i+n} \equiv a_{i+1} - a_i + a_{i+1+n} - a_{i+n} = 2(2n+1) \equiv 0 \pmod{2n+1}.$$
Since $0 < b_i + b_{i+n} < 2(2n+1)$, we have $b_i + b_{i+n} = 2n+1$. Furthermore, we also have
$$a_i = (a_i - a_{i-1}) + (a_{i-1} - a_{i-2}) + \dots + (a_2 - a_1) + a_1 = a_1 + \sum_{k=1}^{i-1} b_k$$
and $a_i$ are pairwise distinct modulo $2n+1$, then there does not exist two indices $i,j$ such that
$$a_j - a_i = \sum_{k=i}^{j-1} b_k \equiv 0 \pmod{2n+1}.$$
Thus, the above way of placing $b_i$ satisfies the condition of $B$. Consider a way in $B$ and $b_i$ is put on $X_i$, $i = 1, 2n$ then consider the sequences
$$a_1 = b_1, \quad a_2 = b_1 + b_2, \quad a_3 = b_1 + b_2 + b_3, \quad \dots, \quad a_i = \sum_{k=1}^{i} b_k$$
and the sum is taken modulo $2n+1$. Then, we can see that all numbers $a_i$ are positive and also pairwise distinct. Otherwise, suppose that there are some $i \neq j$ such that $a_i = a_j$ then
$$0 = a_j - a_i = \sum_{k=i}^{j-1} b_k \pmod{2n+1},$$
which is a contradiction. Furthermore, $b_i + b_{i+n} \equiv a_i - a_{i-1} + a_{i+n} - a_{i+n-1} \equiv 0 \pmod{2n+1}$ which implies that
$$a_i + a_{i+n} \equiv a_{i-1} + a_{i+n-1} \pmod{2n+1} \text{ for all } i \ge 2.$$
Hence, the sums $a_i + a_{i+n}$ for all $i = 1, 2n$ have the remainders when divided by $2n+1$ as $a \in \{0, 1, 2, \dots, 2n\}$. Note that, there are $2n$ sums like that and they are pairwise non-overlapping then
$$\sum_{k=1}^{2n} k = \sum_{i=1}^{2n} (a_i + a_{i+n}) \equiv 2na \pmod{2n+1},$$
but $\gcd(2n, 2n+1) = 1$ then we need to have $a = 0$ or $a_i + a_{i+n} = 2n+1$ for all $i = 1, 2n$. This implies that $a_i$ 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 $b_i + b_{i+n} = 2n+1$ for all $i = 1, 2n$ is $n! \cdot 2^n$ (since numbers $1 \to 2n$ belong to different pairs with the sum equal to $2n+1$ and we also can swap two numbers on $X_i, X_{i+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 \ge 3$ and if we denote $S_k$ as the subset of $S$ with $k$ elements, we have $n \cdot 2^{n-k} \cdot (n-k)! \cdot S_k$ 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 $2^{n-k} \cdot (n-k)!$.

Thus, the number of ways such that $b_i+b_{i+n} = 2n+1$ but the sum of some consecutive numbers is divisible by $2n+1$ is not more than
$$S = n \sum_{k=3}^{n} 2^{n-k}(n-k)!S_k.$$
We shall prove some estimations:

a) $S_k \le \frac{1}{k}C_{2n}^{k-1}$. Note that there are exactly $C_{2n}^{k-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 \cdot S_k \le 1 \cdot C_{2n}^{k-1}$.

b) $C_{2n}^{k-1} \le 4^{k-1}C_{n-1}^{k-1}$ for all $n \ge 5, k \ge 3, n \ge 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
$$C_{2n}^{k} \div C_{n-1}^{k} = \frac{2n-k+1}{k} C_{2n}^{k-1} \div \frac{n-k}{k} C_{n-1}^{k-1} \le \frac{2n-k+1}{n-k} 4^{k-1} < 4^k.$$

c) $\frac{x^0}{0!} + \frac{x^1}{1!} + \frac{x^2}{2!} + \dots + \frac{x^n}{n!} < e^x$ for all $n$.

Finally, we have
$$S \le n \sum_{k=3}^{n} 2^{n-k}(n-k)! \frac{1}{k} C_{2n}^{k-1} \le n \sum_{k=3}^{n} 2^{n-k}(n-k)! \frac{1}{k} C_{n-1}^{k-1} 4^{k-1} \\ = 2^n n! \frac{1}{4} \sum_{k=3}^{n} \frac{2^k}{k!} < 2^n n! \frac{e^2 - (1+2+2)}{4} < 2^n n!.$$
Therefore, $|B| \ge 2^n n! - S > 0$. This completes the proof.