Maths Olympiad Prep

Library / /68 of 397

, 2022

Combinatorics Difficulty 5.1 AIME, harder Prove it Taiwan

Prove that for any subset AA of {1,2,3,...,5505}\{1, 2, 3, ..., 5^{505}\} with exactly 20222022 elements, there must exist three elements a,b,ca, b, c satisfying a<b<ca < b < c and c+2a>3bc + 2a > 3b.

Solution

Reference Solution 1 (By contradiction). Suppose that there exist 20222022 positive integers x0<x1<<x2021x_0 < x_1 < \ldots < x_{2021} that violate the problem statement. Then in particular x2021+2xi3xi+1x_{2021} + 2x_i \le 3x_{i+1} for all i=0,,2020i = 0, \ldots, 2020 which gives
x2021xi32(x2021xi+1). x_{2021} - x_i \ge \frac{3}{2}(x_{2021} - x_{i+1}).
By a trivial induction we then get
x2021xi(32)2020i(x2021x2020), x_{2021} - x_i \ge \left(\frac{3}{2}\right)^{2020-i} (x_{2021} - x_{2020}),
which for i=0i = 0 yields the contradiction since
x2021x0(32)2020(x2021x2020)=(8116)505(x2021x2020)>5505. x_{2021} - x_0 \ge \left(\frac{3}{2}\right)^{2020} (x_{2021} - x_{2020}) = \left(\frac{81}{16}\right)^{505} (x_{2021} - x_{2020}) > 5^{505}.
Therefore, the proof is complete. \square

Reference Solution 2. Denote the maximum element of AA by cc. For k=0,,2019k = 0, \ldots, 2019, let
Ak={xA:(1(2/3)k)cx<(1(2/3)k+1)c}. A_k = \{x \in A : (1 - (2/3)^k)c \le x < (1 - (2/3)^{k+1})c\}.
Note that
(1(2/3)2020)c=c(16/81)505c>c(1/5)505cc1, (1 - (2/3)^{2020})c = c - (16/81)^{505}c > c - (1/5)^{505}c \ge c - 1,
which shows that the sets A0,A1,,A2019A_0, A_1, \ldots, A_{2019} form a partition of A{c}A\setminus\{c\}. Since A{c}A\setminus\{c\} has 20212021 elements, by the pigeonhole principle some set AkA_k does contain at least two elements of A{c}A\setminus\{c\}. Denote these two elements aa and bb and assume a<ba < b, so that a<b<ca < b < c. Then
c+2ac+2(1(2/3)k)c=(32(2/3)k)c=3(1(2/3)k+1)c>3b, c + 2a \ge c + 2(1 - (2/3)^k)c = (3 - 2(2/3)^k)c = 3(1 - (2/3)^{k+1})c > 3b,
as desired. \square

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 translated into English from zh; metadata (topic, difficulty) added by this project.