Maths Olympiad Prep

Library / /10 of 10

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++cll,for all 1ln+2021 oddc1+c2++cll,for all 1ln+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++cll,for all 1lm oddc1+c2++cll,for all 1lm 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 c11c_1 \le 1 and c22c11c_2 \ge 2 - c_1 \ge 1 and similarly, we have cll(c1++cl1)1c_l \le l - (c_1 + \dots + c_{l-1}) \le 1 for any 1lm1 \le l \le m odd, and cll(c1++cl1)1c_l \ge l - (c_1 + \dots + c_{l-1}) \ge 1 for any 1lm1 \le l \le m even.
Let X={1lmcl1}X = \{1 \le l \le m \mid c_l \le 1\} and Y={1lmcl>1}Y = \{1 \le l \le m \mid c_l > 1\}. Then XX contains all 1lm1 \le l \le m odd, thus XY|X| \ge |Y|. It follows that m=X+Y2Ym = |X| + |Y| \ge 2|Y|.
Now let ε=1N\varepsilon = \frac{1}{N} and consider the sequence a1=1(N1)ε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 m2Nm \ge 2N.
(i) Suppose that bk>1b_k > 1 for some 1kn1 \le k \le n. Then YN|Y| \ge N, therefore m2Nm \ge 2N.
(ii) Suppose that bk1b_k \le 1 for all 1kn1 \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(N1)ε,1+ε,,1+εN1,1,,1n 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+c33c_1+c_2+c_3 \le 3 implies that either c1=1(N1)εc_1 = 1 - (N-1)\varepsilon or c3=1(N1)εc_3 = 1 - (N-1)\varepsilon. In either case, we get the contradiction c1+c2+c3+c44(N4)ε<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 1lm1 \le l \le m odd, thus XY+2|X| \ge |Y| + 2. Since Y=N1|Y| = N - 1, we have m=X+Y2Nm = |X| + |Y| \ge 2N.

This proves nNn \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=2a1,b2=2a2,...,bN=2aNb_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<a1a2ak1<ak+1aN<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,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.