Olympiad Maths Prep

Library / /9 of 15

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 1i20221 \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 i1011i \ge 1011, for which sitis_i \ne t_i is divisible by tit_i. Indeed, note that si2022+2021++(2023i)=2023i1011s_i \le 2022 + 2021 + \dots + (2023 - i) = 2023i - 1011. Also, for i1011i \ge 1011 we have 2023i1011<3ti2023i - 1011 < 3t_i, as 4ti=2i(i+1)2024i4t_i = 2i(i+1) \ge 2024i, so if for i1011i \ge 1011 tit_i is an integer larger than 11, then si=2tis_i = 2t_i.

Suppose that there exist two such i>j1011i > j \ge 1011, that si=2ti,sj=2tjs_i = 2t_i, s_j = 2t_j, then sisj=2(titj)=i2+j2ij=(ij)(i+j+1)2023(ij)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 sisj=aj+1+aj+2++ai2022(ij)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.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.