11

Let $$A=\{a_{1},a_{2},\ldots,a_{n}\}\subset N$$ Suppose that for any two distinct subsets $B, C\subseteq A$, we have $$\sum_{x\in B}x\neq \sum_{x\in C}x$$

Then show that $$\dfrac{1}{a_{1}}+\dfrac{1}{a_{2}}+\dfrac{1}{a_{3}}+\cdots+\dfrac{1}{a_{n}}<2$$

Asaf Karagila
  • 393,674
math110
  • 93,304
  • Do you mean to say that any distinct subsets $B,C\subseteq A$ have different sums? – Alex Becker Apr 02 '14 at 06:25
  • @AlexBecker,yes,That's you mean.Thank you – math110 Apr 02 '14 at 06:39
  • 3
    One possible hint: the condition that $\sum\limits_{x\in B}x\neq\sum\limits_{x\in C}x$ is one way of formalizing the statement that any representable number has a unique representation as a sum of $a_i$. The 'unique representation' condition is obviously related to binary representation - but there are sequences with $a_i\lt 2a_{i=1}$ for some $i$ that still satisfy the condition (for instance, $A={1, 2, 7, 11}$). Still, this may be enough to push through a 'weight' argument. – Steven Stadnicki Apr 02 '14 at 07:02
  • 1
    Potentially helpful:

    A has $2^n$ subsets, each of which must have a distinct sum. $\Sigma A$ is the largest such sum, hence is greater than or equal to $2^n-1$.

     – G. H. Faust Apr 02 '14 at 10:25
  • 4
    Not every question where sets appears is about set theory. – Asaf Karagila Apr 02 '14 at 13:21

1 Answers1

6

This is an old conjecture of Erdos, which was subsequently proved (Ryavek from my notes) - though I cannot find a handy online reference just now. The proof goes along the following lines, IIRC:

With $0 < x< 1$, we have by the distinct sum condition: $$ \prod_{k=1}^n (1+x^{a_k}) < \sum_{k=0}^{\infty} x^k = \frac1{1-x} $$

$$\implies \sum_{k=1}^n \log(1+x^{a_k}) < - \log (1-x)$$

As both sides are positive, we can divide by $x$ and integrate to get

$$\implies \sum_{k=1}^n \int_0^1 \frac{ \log(1+x^{a_k})}x dx < - \int_0^1 \frac{\log (1-x)}x dx $$

$$\implies \sum_{k=1}^n \frac1{a_k} \cdot \int_0^1 \frac{ \log(1+t)}t dt < \frac{\pi^2}6 $$ $$\implies \sum_{k=1}^n \frac1{a_k} \cdot \frac{\pi^2}{12} < \frac{\pi^2}6 \implies \sum_{k=1}^n \frac1{a_k} < 2 $$

Macavity
  • 46,381
  • Here's a paper that proves a generalization of this result and gives some references to the question at hand: http://www.ams.org/journals/proc/1998-126-11/S0002-9939-98-04576-6/S0002-9939-98-04576-6.pdf – Steve Kass Apr 02 '14 at 15:12
  • 1
    @SteveKass Thanks. Found another reference with a couple of other ways of proving the same problem: http://books.google.co.in/books?id=RbdP7QG2MyUC&lpg=PA775&ots=bp4Xob85Aj&dq=Canadian%20Mathematical%20Bulletin%20CMB%20volume%2017&pg=PA768#v=onepage&q&f=false – Macavity Apr 02 '14 at 15:49