Competition problem — Combinatorics

Library / /92 of 520

Combinatorics Difficulty 5.7 AIME, harder Prove it

Let $S$ be the collection of all sets of $n$ distinct positive integers, with no three in arithmetic progression. Show that there is a member of $S$ 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

Induction on $\mathrm{n}$ . For $\mathrm{n}=1,\{1\}$ is obviously maximal. Now suppose $\mathrm{a}_{1}a_{n}$ such that $\left\{a_{1}, a_{2}, \ldots, a_{n+1}\right\}$ has no three members in AP. Now consider the sequences $\mathrm{b}_{1}a_{n+1}$ . Then we have $1 / \mathrm{x}_{n+1}<1 / \mathrm{a}_{n+1}$ and, by induction, $1 / \mathrm{x}_{1}+\ldots+1 / \mathrm{x}_{n} \leq 1 / \mathrm{a}_{1}+\ldots+1 / \mathrm{a}_{n}$ , so $1 / \mathrm{x}_{1}+\ldots+1 / \mathrm{x}_{\mathrm{n}+1}$ $<1 / \mathrm{a}_{1}+\ldots+1 / \mathrm{a}_{\mathrm{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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.