Maths Olympiad Prep

Track / Stage 5 / 68 of 400 #1308 of 2604

Problem 1308

AIME late
Combinatorics Difficulty 5.1 Prove it Taiwan IMO Selection Camp · Taiwan · 2022

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.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official 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+2xi≤3xi+1x_{2021} + 2x_i \le 3x_{i+1} for all i=0,…,2020i = 0, \ldots, 2020 which gives
x2021−xi≥32(x2021−xi+1). x_{2021} - x_i \ge \frac{3}{2}(x_{2021} - x_{i+1}).
By a trivial induction we then get
x2021−xi≥(32)2020−i(x2021−x2020), 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
x2021−x0≥(32)2020(x2021−x2020)=(8116)505(x2021−x2020)>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={x∈A:(1−(2/3)k)c≤x<(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)505c≥c−1, (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+2a≥c+2(1−(2/3)k)c=(3−2(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

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty, ordering) added by this project.