Maths Olympiad Prep

Library / Round 3 /9 of 9

Round 3

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Mongolia

Find the smallest positive integer nn with the following property:
For any sequence a1,a2,…,a2021a_1, a_2, \dots, a_{2021} of real numbers satisfying
0<a1,a2,…,a2021<2anda1+a2+⋯+a2021=2021, 0 < a_1, a_2, \dots, a_{2021} < 2 \quad \text{and} \quad a_1 + a_2 + \dots + a_{2021} = 2021,
there is a sequence b1,b2,…,bnb_1, b_2, \dots, b_n of real numbers satisfying
0<b1,b2,…,bn<2andb1+b2+⋯+bn=n 0 < b_1, b_2, \dots, b_n < 2 \quad \text{and} \quad b_1 + b_2 + \dots + b_n = n
and a permutation c1,c2,…,cn+2021c_1, c_2, \dots, c_{n+2021} of the sequence a1,a2,…,a2021,b1,b2,…,bna_1, a_2, \dots, a_{2021}, b_1, b_2, \dots, b_n such that
{c1+c2+⋯+cl≤l,for all 1≤l≤n+2021 oddc1+c2+⋯+cl≥l,for all 1≤l≤n+2021 even. \begin{cases} c_1 + c_2 + \dots + c_l \le l, & \text{for all } 1 \le l \le n + 2021 \text{ odd} \\ c_1 + c_2 + \dots + c_l \ge l, & \text{for all } 1 \le l \le n + 2021 \text{ even}. \end{cases}

Solution

Answer: n=2021n = 2021.
First we show that n=2021n = 2021 is the minimum.
Let N=2021N = 2021 and m=n+Nm = n + N and suppose that the sequence c1,c2,…,cmc_1, c_2, \dots, c_m satisfies
{c1+c2+⋯+cl≤l,for all 1≤l≤m oddc1+c2+⋯+cl≥l,for all 1≤l≤m even.(∗) \begin{cases} c_1 + c_2 + \dots + c_l \le l, & \text{for all } 1 \le l \le m \text{ odd} \\ c_1 + c_2 + \dots + c_l \ge l, & \text{for all } 1 \le l \le m \text{ even.} \end{cases} \quad (*)
Then c1≤1c_1 \le 1 and c2≥2−c1≥1c_2 \ge 2 - c_1 \ge 1 and similarly, we have cl≤l−(c1+⋯+cl−1)≤1c_l \le l - (c_1 + \dots + c_{l-1}) \le 1 for any 1≤l≤m1 \le l \le m odd, and cl≥l−(c1+⋯+cl−1)≥1c_l \ge l - (c_1 + \dots + c_{l-1}) \ge 1 for any 1≤l≤m1 \le l \le m even.
Let X={1≤l≤m∣cl≤1}X = \{1 \le l \le m \mid c_l \le 1\} and Y={1≤l≤m∣cl>1}Y = \{1 \le l \le m \mid c_l > 1\}. Then XX contains all 1≤l≤m1 \le l \le m odd, thus ∣X∣≥∣Y∣|X| \ge |Y|. It follows that m=∣X∣+∣Y∣≥2∣Y∣m = |X| + |Y| \ge 2|Y|.
Now let ε=1N\varepsilon = \frac{1}{N} and consider the sequence a1=1−(N−1)εa_1 = 1 - (N-1)\varepsilon, a2=⋯=aN=1+εa_2 = \dots = a_N = 1 + \varepsilon and suppose that b1,b2,…,bnb_1, b_2, \dots, b_n and c1,c2,…,cmc_1, c_2, \dots, c_m are chosen to satisfy the conditions of the problem. We prove that m≥2Nm \ge 2N.
(i) Suppose that bk>1b_k > 1 for some 1≤k≤n1 \le k \le n. Then ∣Y∣≥N|Y| \ge N, therefore m≥2Nm \ge 2N.
(ii) Suppose that bk≤1b_k \le 1 for all 1≤k≤n1 \le k \le n. In this case, b1=b2=⋯=bn=1b_1 = b_2 = \dots = b_n = 1 since b1+⋯+bn=nb_1 + \dots + b_n = n. Thus c1,…,cmc_1, \dots, c_m is a permutation of
1−(N−1)ε,1+ε,…,1+ε⏟N−1,1,…,1⏟n 1 - (N - 1)\varepsilon, \underbrace{1 + \varepsilon, \dots, 1 + \varepsilon}_{N-1}, \underbrace{1, \dots, 1}_{n}
satisfying (∗)(*). We claim that c2=1c_2 = 1. Suppose on the contrary that c2=1+εc_2 = 1 + \varepsilon. Then c1+c2+c3≤3c_1+c_2+c_3 \le 3 implies that either c1=1−(N−1)εc_1 = 1 - (N-1)\varepsilon or c3=1−(N−1)εc_3 = 1 - (N-1)\varepsilon. In either case, we get the contradiction c1+c2+c3+c4≤4−(N−4)ε<4c_1 + c_2 + c_3 + c_4 \le 4 - (N-4)\varepsilon < 4. Hence c2=1c_2 = 1.
It follows that XX contains 22 and all 1≤l≤m1 \le l \le m odd, thus ∣X∣≥∣Y∣+2|X| \ge |Y| + 2. Since ∣Y∣=N−1|Y| = N - 1, we have m=∣X∣+∣Y∣≥2Nm = |X| + |Y| \ge 2N.

This proves n≥Nn \ge N. Now we prove n=Nn = N satisfies the property of the problem. Let 0<a1,a2,...,aN<20 < a_1, a_2, ..., a_N < 2 be a sequence with a1+a2+⋯+aN=Na_1 + a_2 + \dots + a_N = N and let b1=2−a1,b2=2−a2,...,bN=2−aNb_1 = 2 - a_1, b_2 = 2 - a_2, ..., b_N = 2 - a_N. Then 0<b1,b2,...,bN<20 < b_1, b_2, ..., b_N < 2 and b1+b2+⋯+bN=Nb_1 + b_2 + \dots + b_N = N.
Changing the indices, we may assume
0<a1≤a2≤⋯≤ak≤1<ak+1≤⋯≤aN<2. 0 < a_1 \le a_2 \le \dots \le a_k \le 1 < a_{k+1} \le \dots \le a_N < 2.
Then the sequence a1,b1,a2,b2,...,ak,bk,bk+1,ak+1,...,bN,aNa_1, b_1, a_2, b_2, ..., a_k, b_k, b_{k+1}, a_{k+1}, ..., b_N, a_N satisfies ⋆\star.

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

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