Maths Olympiad Prep

Library / /38 of 61

Combinatorics Difficulty 5.9 AIME, harder Prove it Ibero-American Mathematical Olympiad

Problem:

Let SS be the collection of all sets of nn distinct positive integers, with no three in arithmetic progression. Show that there is a member of SS which has the largest sum of the inverses of its elements (you do not have to find it or to show that it is unique).

Solution

Solution:

Induction on nn.

For n=1n = 1, {1}\{1\} is obviously maximal.

Now suppose a1<a2<<ana_1 < a_2 < \ldots < a_n is a maximal set for nn.

Take an+1a_{n+1} to be the smallest integer >an> a_n such that {a1,a2,,an+1}\{a_1, a_2, \ldots, a_{n+1}\} has no three members in arithmetic progression.

Now consider the sequences b1<b2<<bnb_1 < b_2 < \ldots < b_n which have no three in arithmetic progression and bn+1an+1b_{n+1} \leq a_{n+1}. There are only finitely many such sequences. So we can find one which is maximal. Suppose it is c1<c2<<cn+1c_1 < c_2 < \ldots < c_{n+1}.

Now take whichever of aia_i, cic_i has the larger sum of inverses. It is clearly maximal with respect to sequences whose largest member is an+1\leq a_{n+1}.

Suppose we have a sequence x1<x2<<xn+1x_1 < x_2 < \ldots < x_{n+1} with no three in arithmetic progression and xn+1>an+1x_{n+1} > a_{n+1}. Then we have 1/xn+1<1/an+11 / x_{n+1} < 1 / a_{n+1} and, by induction, 1/x1++1/xn1/a1++1/an1 / x_1 + \ldots + 1 / x_n \leq 1 / a_1 + \ldots + 1 / a_n, so 1/x1++1/xn+1<1/a1++1/an+11 / x_1 + \ldots + 1 / x_{n+1} < 1 / a_1 + \ldots + 1 / a_{n+1}, so it is worse than the sequence we have chosen.

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.