Find the smallest positive integer n with the following property: For any sequence a1,a2,…,a2021 of real numbers satisfying 0<a1,a2,…,a2021<2anda1+a2+⋯+a2021=2021, there is a sequence b1,b2,…,bn of real numbers satisfying 0<b1,b2,…,bn<2andb1+b2+⋯+bn=n and a permutation c1,c2,…,cn+2021 of the sequence a1,a2,…,a2021,b1,b2,…,bn such that {c1+c2+⋯+cl≤l,c1+c2+⋯+cl≥l,for all 1≤l≤n+2021 oddfor all 1≤l≤n+2021 even.
Solution
Answer: n=2021. First we show that n=2021 is the minimum. Let N=2021 and m=n+N and suppose that the sequence c1,c2,…,cm satisfies {c1+c2+⋯+cl≤l,c1+c2+⋯+cl≥l,for all 1≤l≤m oddfor all 1≤l≤m even.(∗) Then c1≤1 and c2≥2−c1≥1 and similarly, we have cl≤l−(c1+⋯+cl−1)≤1 for any 1≤l≤m odd, and cl≥l−(c1+⋯+cl−1)≥1 for any 1≤l≤m even. Let X={1≤l≤m∣cl≤1} and Y={1≤l≤m∣cl>1}. Then X contains all 1≤l≤m odd, thus ∣X∣≥∣Y∣. It follows that m=∣X∣+∣Y∣≥2∣Y∣. Now let ε=N1 and consider the sequence a1=1−(N−1)ε, a2=⋯=aN=1+ε and suppose that b1,b2,…,bn and c1,c2,…,cm are chosen to satisfy the conditions of the problem. We prove that m≥2N. (i) Suppose that bk>1 for some 1≤k≤n. Then ∣Y∣≥N, therefore m≥2N. (ii) Suppose that bk≤1 for all 1≤k≤n. In this case, b1=b2=⋯=bn=1 since b1+⋯+bn=n. Thus c1,…,cm is a permutation of 1−(N−1)ε,N−11+ε,…,1+ε,n1,…,1 satisfying (∗). We claim that c2=1. Suppose on the contrary that c2=1+ε. Then c1+c2+c3≤3 implies that either c1=1−(N−1)ε or c3=1−(N−1)ε. In either case, we get the contradiction c1+c2+c3+c4≤4−(N−4)ε<4. Hence c2=1. It follows that X contains 2 and all 1≤l≤m odd, thus ∣X∣≥∣Y∣+2. Since ∣Y∣=N−1, we have m=∣X∣+∣Y∣≥2N.
This proves n≥N. Now we prove n=N satisfies the property of the problem. Let 0<a1,a2,...,aN<2 be a sequence with a1+a2+⋯+aN=N and let b1=2−a1,b2=2−a2,...,bN=2−aN. Then 0<b1,b2,...,bN<2 and b1+b2+⋯+bN=N. Changing the indices, we may assume 0<a1≤a2≤⋯≤ak≤1<ak+1≤⋯≤aN<2. Then the sequence a1,b1,a2,b2,...,ak,bk,bk+1,ak+1,...,bN,aN satisfies ⋆.
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.