Maths Olympiad Prep

Library / /6 of 6

Combinatorics Difficulty 9.0 IMO level Prove it Vietnam

For a positive integer nn, consider a1,a2,,a2na_1, a_2, \dots, a_{2n} as a permutation of the first 2n2n positive integers. A permutation is called "nice" if ai+an+i=2n+1a_i + a_{n+i} = 2n+1, i=1,2,3,,ni = 1, 2, 3, \dots, n and aiai+1a_i - a_{i+1} is not congruent to ajaj+1a_j - a_{j+1} modulo 2n+12n+1 for all 1i<j2n1 \le i < j \le 2n (suppose that a2n+1=a1a_{2n+1} = a_1).

1. For n=6n = 6, give an example of the nice permutation.
2. Prove that for all nn, there always exist some nice permutation.

Solution

1) We consider the following permutation 1,2,4,8,3,6,12,11,9,5,10,71, 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+71+12=2+11=4+9=8+5=3+10=6+7. Furthermore, the difference between two consecutive numbers in modulo 1313 in order are 1,2,4,8,3,6,12,11,9,5,10,71, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, which are all distinct. Therefore, this permutation is nice.

2) Let AA be the set of nice permutations and BB be the set of ways to put numbers 1,2,,2n1, 2, \dots, 2n on the vertices of a regular polygon X1X2X3X2nX_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+12n+1;
2. There is no consecutive sequence of numbers whose sum is divisible by 2n+12n+1.

We shall prove that there is a bijection ABA \to B and then, to prove the existence of the nice permutation, we just need to prove A=B>0|A| = |B| > 0.

First step. There is a bijection from AA to BB.

Consider a nice permutation in AA, namely (a1,a2,,a2n)(a_1, a_2, \dots, a_{2n}) then for each i=1,2ni = \overline{1, 2n}, we choose bi{1,,2n}b_i \in \{1, \dots, 2n\} such that biai+1ai(mod2n+1)b_i \equiv a_{i+1} - a_i \pmod{2n+1}. Then all numbers bib_i are pairwise distinct. We denote a2n+1=a1a_{2n+1} = a_1 and b2n+1=b1b_{2n+1} = b_1.

We put all these numbers onto the circle in that order, which means bib_i for XiX_i. It is easy to see that
bi+bi+nai+1ai+ai+1+nai+n=2(2n+1)0(mod2n+1). 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<bi+bi+n<2(2n+1)0 < b_i + b_{i+n} < 2(2n+1), we have bi+bi+n=2n+1b_i + b_{i+n} = 2n+1. Furthermore, we also have
ai=(aiai1)+(ai1ai2)++(a2a1)+a1=a1+k=1i1bk 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 aia_i are pairwise distinct modulo 2n+12n+1, then there does not exist two indices i,ji,j such that
ajai=k=ij1bk0(mod2n+1). a_j - a_i = \sum_{k=i}^{j-1} b_k \equiv 0 \pmod{2n+1}.
Thus, the above way of placing bib_i satisfies the condition of BB. Consider a way in BB and bib_i is put on XiX_i, i=1,2ni = 1, 2n then consider the sequences
a1=b1,a2=b1+b2,a3=b1+b2+b3,,ai=k=1ibk 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+12n+1. Then, we can see that all numbers aia_i are positive and also pairwise distinct. Otherwise, suppose that there are some iji \neq j such that ai=aja_i = a_j then
0=ajai=k=ij1bk(mod2n+1), 0 = a_j - a_i = \sum_{k=i}^{j-1} b_k \pmod{2n+1},
which is a contradiction. Furthermore, bi+bi+naiai1+ai+nai+n10(mod2n+1)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
ai+ai+nai1+ai+n1(mod2n+1) for all i2. 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 ai+ai+na_i + a_{i+n} for all i=1,2ni = 1, 2n have the remainders when divided by 2n+12n+1 as a{0,1,2,,2n}a \in \{0, 1, 2, \dots, 2n\}. Note that, there are 2n2n sums like that and they are pairwise non-overlapping then
k=12nk=i=12n(ai+ai+n)2na(mod2n+1), \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\gcd(2n, 2n+1) = 1 then we need to have a=0a = 0 or ai+ai+n=2n+1a_i + a_{i+n} = 2n+1 for all i=1,2ni = 1, 2n. This implies that aia_i is a nice permutation, which belongs to AA. Then we can conclude that there is a bijection from AA to BB.

Second step. One can check that the number of ways to place numbers such that bi+bi+n=2n+1b_i + b_{i+n} = 2n+1 for all i=1,2ni = 1, 2n is n!2nn! \cdot 2^n (since numbers 12n1 \to 2n belong to different pairs with the sum equal to 2n+12n+1 and we also can swap two numbers on Xi,Xi+nX_i, X_{i+n}). We denote the set of all these ways by SS. Suppose that in some way of SS, there is some consecutive sequence of length kk whose sum is divisible by 2n+12n+1 then k3k \ge 3 and if we denote SkS_k as the subset of SS with kk elements, we have n2nk(nk)!Skn \cdot 2^{n-k} \cdot (n-k)! \cdot S_k ways.

Indeed, we have nn ways to choose the start position of the sequence (it is easy to see that kk symmetric numbers with respect to the center of the polygon also satisfy that property), then there are 2n2k2n-2k remaining numbers which are free to distribute, and the number of ways to put is 2nk(nk)!2^{n-k} \cdot (n-k)!.

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

a) Sk1kC2nk1S_k \le \frac{1}{k}C_{2n}^{k-1}. Note that there are exactly C2nk1C_{2n}^{k-1} subsets of size k1k-1 of the first 2n2n 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+12n+1. On the other hand, for each subset of size kk which has the sum as a multiple of 2n+12n+1, there are exactly kk subsets of size k1k-1 of the first 2n2n positive integers. Thus kSk1C2nk1k \cdot S_k \le 1 \cdot C_{2n}^{k-1}.

b) C2nk14k1Cn1k1C_{2n}^{k-1} \le 4^{k-1}C_{n-1}^{k-1} for all n5,k3,nkn \ge 5, k \ge 3, n \ge k (and for n=1,2,3,4n=1,2,3,4 we can point out a specific nice permutation). This can be proved by induction on nn with the following inequality
C2nk÷Cn1k=2nk+1kC2nk1÷nkkCn1k12nk+1nk4k1<4k. 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) x00!+x11!+x22!++xnn!<ex\frac{x^0}{0!} + \frac{x^1}{1!} + \frac{x^2}{2!} + \dots + \frac{x^n}{n!} < e^x for all nn.

Finally, we have
Snk=3n2nk(nk)!1kC2nk1nk=3n2nk(nk)!1kCn1k14k1=2nn!14k=3n2kk!<2nn!e2(1+2+2)4<2nn!. 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, B2nn!S>0|B| \ge 2^n n! - S > 0. This completes the proof.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.