The Sums of the Subsets are Distinct

Question

Let $S$ be a set of $n$ positive integers such that no two subsets have the same sum. Prove that $\sum_{a \in S} \frac{1}{a} < 2$.

I have found a paper with a nice proof of the statement by S. J. Benkoski and Paul Erdos http://renyi.hu/~p_erdos/1974-24.pdf

but I'd still like to see an elementary proof.

Answer 1

It is enough to show that among every other sequence satisfying $\sum_{i=1}^m a_i \geq 2^m - 1$ for every $m$, the sequence $1,2,4,\dots$ maximizes the sum of the reciprocals. Since $1,2,4,\dots$ also satisfies that distinct subset sum property, we're done.

Suppose that $a_1 < a_2 < \dots < a_n$ satisfies $\sum_{i=1}^m a_i \geq 2^m - 1$ for every $m$ and $k$ is the first index where $\sum_{i=1}^k a_i > 2^{k} - 1$. (i.e. $a_k > 2^{k-1}$).

Then there are two cases:

1. If there is no $j > k$ such that $\sum_{i=1}^j a_i = 2^{j} - 1$. Then replace $a_k$ with $a_k - 1$. Since $\sum_{i=1}^m a_k > 2^m-1$ for all $m \geq k$, replacing $a_k$ with $a_k-1$ maintains $\sum_{i=1}^m a_k \geq 2^m-1$ for all $m$. Since $\frac{1}{a_k} < \frac{1}{a_k-1}$, the sum increases.
2. If there is a $j > k$ such that $\sum_{i=1}^j a_i = 2^{j} - 1$ (and suppose $j$ is the smallest such index). Then, replace $a_k$ with $a_k-1$ and $a_j$ with $a_j + 1$. Since $\sum_{i=1}^m a_k > 2^m-1$ for all $k \leq m < j$, replacing $a_k$ with $a_k - 1$ and $a_j$ with $a_j + 1$ maintains the bounds. Since $a_k < a_j$, $\frac{1}{a_k} + \frac{1}{a_j} < \frac{1}{a_k-1} +\frac{1}{a_j+1}$, the sum increases.

Repeat until the sequence is $1,2,4,\dots$. Since $1 + \frac{1}{2} + \dots + \frac{1}{2^{n-1}} < 2$ and the sum $\frac{1}{a_1} + \dots + \frac{1}{a_n}$ increased at each step, then $\frac{1}{a_1} + \dots + \frac{1}{a_n} < 2$.