Maths Olympiad Prep

Library / Ukrainian National Mathematical Olympiad, Third Round, Second Tour /8 of 14

Ukrainian National Mathematical Olympiad, Third Round, Second Tour

Combinatorics Difficulty 5.9 AIME, harder Prove it Ukraine

For which largest kk does there exist a permutation (a1,a2,…,a2022)(a_1, a_2, \ldots, a_{2022}) of integers (1,2,…,2022)(1, 2, \ldots, 2022) such that for some kk integers 1≤i≤20221 \le i \le 2022 the fraction a1+a2+⋯+ai1+2+⋯+i\frac{a_1 + a_2 + \cdots + a_i}{1 + 2 + \cdots + i} is an integer larger than 11?

(Oleksii Masalitin)

Solution

Denote by si=a1+a2+⋯+ais_i = a_1 + a_2 + \dots + a_i, ti=1+2+⋯+it_i = 1 + 2 + \dots + i. We will show that there exists at most one i≥1011i \ge 1011, for which si≠tis_i \ne t_i is divisible by tit_i. Indeed, note that si≤2022+2021+⋯+(2023−i)=2023i−1011s_i \le 2022 + 2021 + \dots + (2023 - i) = 2023i - 1011. Also, for i≥1011i \ge 1011 we have 2023i−1011<3ti2023i - 1011 < 3t_i, as 4ti=2i(i+1)≥2024i4t_i = 2i(i+1) \ge 2024i, so if for i≥1011i \ge 1011 tit_i is an integer larger than 11, then si=2tis_i = 2t_i.

Suppose that there exist two such i>j≥1011i > j \ge 1011, that si=2ti,sj=2tjs_i = 2t_i, s_j = 2t_j, then si−sj=2(ti−tj)=i2+j2−i−j=(i−j)(i+j+1)≥2023(i−j)s_i - s_j = 2(t_i - t_j) = i^2 + j^2 - i - j = (i-j)(i+j+1) \ge 2023(i-j), but si−sj=aj+1+aj+2+⋯+ai≤2022(i−j)s_i - s_j = a_{j+1} + a_{j+2} + \dots + a_i \le 2022(i-j), contradiction. So, there can't be more than 10111011.

Let it be ii. It's enough to note that for a permutation (2,4,…,2022,1,3,…,2021)(2, 4, \dots, 2022, 1, 3, \dots, 2021) the number of such ii is precisely 10111011, as for i=1,…,1011i = 1, \ldots, 1011 we have si=2+4+⋯+2i=2tis_i = 2+4+\dots+2i = 2t_i.

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.