Maths Olympiad Prep

Library / /17 of 29

Combinatorics Difficulty 5.7 AIME, harder Prove it Croatia

Let kk be an arbitrary nonnegative integer. Prove that we can find 42k4 \cdot 2^k distinct positive integers not greater than 53k5 \cdot 3^k, such that no three of them are consecutive terms of an arithmetic progression.

Solution

We will prove the statement using induction on kk.

For k=0k = 0 we need to choose four numbers from {1,2,3,4,5}\{1, 2, 3, 4, 5\} so that among them don't exist three consecutive members of an arithmetic progression. The only such choice is {1,2,4,5}\{1, 2, 4, 5\}.

Assume that for some k0k \ge 0 we found a set SkS_k that contains 42k4 \cdot 2^k positive integers not greater than 53k5 \cdot 3^k so that among them don't exist three consecutive members of an arithmetic progression.

Let Tk={103k+s:sSk}T_k = \{10 \cdot 3^k + s : s \in S_k\}. Sets SkS_k and TkT_k have the same number of elements. We claim that Sk+1=SkTkS_{k+1} = S_k \cup T_k satisfies the conditions for k+1k+1.

The set Sk+1S_{k+1} has 2(42k)=42k+12 \cdot (4 \cdot 2^k) = 4 \cdot 2^{k+1} elements, and none of them is greater than 103k+53k=53k+110 \cdot 3^k + 5 \cdot 3^k = 5 \cdot 3^{k+1}. If we take three arbitrary numbers a,b,cSk+1a, b, c \in S_{k+1} such that a<b<ca < b < c, exactly one of the following possibilities is true:
1a,b,cSk 1^\circ \quad a, b, c \in S_k
2a,bSk,cTk 2^\circ \quad a, b \in S_k, \quad c \in T_k
3aSk,b,cTk 3^\circ \quad a \in S_k, \quad b, c \in T_k
4a,b,cTk. 4^\circ \quad a, b, c \in T_k.
To prove that the statement holds for k+1k+1 it is sufficient to show that in each case a+c2ba+c \neq 2b.

a+c2ba+c \neq 2b because of the induction hypothesis for SkS_k.

2a+c1+(103k+1)>103k2b, 2^\circ \quad a+c \ge 1 + (10 \cdot 3^k + 1) > 10 \cdot 3^k \ge 2b,
3a+c53k+53k+1=203k<2b. 3^\circ \quad a+c \le 5 \cdot 3^k + 5 \cdot 3^{k+1} = 20 \cdot 3^k < 2b.
a103k,b103ka - 10 \cdot 3^k, b - 10 \cdot 3^k and c103kc - 10 \cdot 3^k are elements of the set SkS_k. Therefore
(a103k)+(c103k)2(b103k), (a - 10 \cdot 3^k) + (c - 10 \cdot 3^k) \neq 2 (b - 10 \cdot 3^k),
so a+c2ba+c \neq 2b.

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.