Las Sumas de los Subconjuntos son Distintos

Question

Deje $S$ ser un conjunto de $n$ enteros positivos tales que no hay dos subconjuntos tienen la misma suma. Demostrar que $\sum_{a \in S} \frac{1}{a} < 2$.

He encontrado un papel con una prueba interesante de la declaración de S. J. Benkoski y Paul Erdos http://renyi.hu/~p_erdos/1974-24.pdf

pero yo todavía me gustaría ver una primaria de la prueba.

Answer 1

Es suficiente para demostrar que entre todos los demás de la secuencia de satisfacciones $\sum_{i=1}^m a_i \geq 2^m - 1$ por cada $m$, la secuencia de $1,2,4,\dots$ maximiza la suma de los recíprocos. Desde $1,2,4,\dots$ también satisface que el subconjunto distinto de la suma de la propiedad, hemos terminado.

Supongamos que $a_1 < a_2 < \dots < a_n$ satisface $\sum_{i=1}^m a_i \geq 2^m - 1$ por cada $m$ $k$ es el primer índice en $\sum_{i=1}^k a_i > 2^{k} - 1$. (es decir,$a_k > 2^{k-1}$).

Entonces hay dos casos:

1. Si no es $j > k$ tal que $\sum_{i=1}^j a_i = 2^{j} - 1$. A continuación, reemplace $a_k$$a_k - 1$. Desde $\sum_{i=1}^m a_k > 2^m-1$ todos los $m \geq k$, en sustitución de $a_k$ $a_k-1$ mantiene $\sum_{i=1}^m a_k \geq 2^m-1$ todos los $m$. Desde $\frac{1}{a_k} < \frac{1}{a_k-1}$, la suma aumenta.
2. Si hay un $j > k$ tal que $\sum_{i=1}^j a_i = 2^{j} - 1$ (y supongamos $j$ es el más pequeño de ese índice). A continuación, reemplace $a_k$$a_k-1$$a_j$$a_j + 1$. Desde $\sum_{i=1}^m a_k > 2^m-1$ todos los $k \leq m < j$, en sustitución de $a_k$ $a_k - 1$ $a_j$ $a_j + 1$ mantiene los límites. Desde $a_k < a_j$, $\frac{1}{a_k} + \frac{1}{a_j} < \frac{1}{a_k-1} +\frac{1}{a_j+1}$, la suma de los aumentos.

Repita hasta que la secuencia es $1,2,4,\dots$. Desde $1 + \frac{1}{2} + \dots + \frac{1}{2^{n-1}} < 2$ y la suma de $\frac{1}{a_1} + \dots + \frac{1}{a_n}$ de aumento en cada paso, a continuación,$\frac{1}{a_1} + \dots + \frac{1}{a_n} < 2$.