7
$\begingroup$

Say $\sum_{i \in I} \frac{1}{n_i} = 2$, where $(n_i)_{i \in I}$ is a finite sequence of positive integers (not necessarily distinct). Is there a subsequence $(n_i)_{i \in J}$ of $(n_i)_{i \in I}$ such that $\sum_{i \in J} \frac{1}{n_i} = 1$?

$\endgroup$
7
  • $\begingroup$ something like $\frac{1}{2}$? $\endgroup$
    – Masacroso
    Jun 16 '15 at 3:12
  • $\begingroup$ What do you mean by $\frac{1}{2}$ ? $\endgroup$
    – pallab1234
    Jun 16 '15 at 3:19
  • $\begingroup$ It certainly appears that there always is. The condition that each $n_i$ is a positive integer, that we have a finite number of terms, and that the numerator of each term is a $1$ seems to force that upon us. I haven't spotted how to prove it yet, but perhaps try an argument based on the greatest common denominator of the terms. $\endgroup$
    – JMoravitz
    Jun 16 '15 at 3:19
  • 1
    $\begingroup$ @Anson what are you talking about? $2= \frac{1}{2}+\frac{1}{2}+\frac{1}{3}+\frac{1}{3}+\frac{1}{3}$ for trivial example. Here we have $0<\frac{1}{2} + \frac{1}{3}<1$. In this example, we could take the three $\frac{1}{3}$'s to add to one, or the two halves. If one of the $n_i$ is equal to $1$, then of course the question of finding such a subset is trivial, but we are tasked with finding it in the general case. $\endgroup$
    – JMoravitz
    Jun 16 '15 at 3:31
  • 3
    $\begingroup$ @JMoravitz I read "sum of the subset" as asking for the sum of the subset of integers. Is it asking for the sum of the reciprocals of integers in the subset? Perhaps "sum over the subset" or "subset of $\frac{1}{n_i}$" would clear that up. $\endgroup$
    – Anson
    Jun 16 '15 at 3:40
17
$\begingroup$

Here is a counterexample even when all fractions are required to be different!

$\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{7}+\frac{1}{8}+\frac{1}{9}+\frac{1}{11}+\frac{1}{13}+\frac{1}{16}+\frac{1}{17}+\frac{1}{21}+\frac{1}{1105}+\frac{1}{55692}+\frac{1}{1361360}$

This came from:

$\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{7}+\frac{1}{8}+\frac{1}{9}+\frac{1}{11}+\frac{1}{13}+\frac{1}{16}+\frac{1}{17}$ [only prime powers]

$+\frac{1}{3 \cdot 7}+\frac{1}{5 \cdot 13 \cdot 17}+\frac{1}{2^2 \cdot 3^2 \cdot 7 \cdot 13 \cdot 17}+\frac{1}{2^4 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17}$ [plus extra terms to get to $2$]

To prove it, first multiply throughout by $2^4 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17$.

Now consider any subset whose sum is $1$. We can assume that it does not include the last term. Modulo $13$ we see immediately that it cannot include any term with denominator divisible by $13$. Now modulo $7$ we see that it cannot include $\frac{1}{21}$. We can repeat this reasoning all the way, but now actually it is obvious that it is impossible because the remaining terms allowed are all prime powers and hence the term in the subset with largest denominator $p^k$ will create a contradiction modulo $p$.

$\endgroup$
8
$\begingroup$

Here is a counterexample:

$\frac{1}{2}+\frac{1}{3}+\frac{1}{3}+\frac{1}{5}+\frac{1}{5}+\frac{1}{5}+\frac{1}{5}+\frac{1}{30}$

$\endgroup$
3
  • $\begingroup$ @JMoravitz: Does this have a subset sum equal to 1? But what if the fractions are all required to be different... $\endgroup$
    – user21820
    Jun 16 '15 at 5:51
  • $\begingroup$ No subset sum equal to $1$... nice example. $\endgroup$
    – mjqxxxx
    Jun 16 '15 at 5:57
  • $\begingroup$ @mjqxxxx: I found a counterexample to the stronger question I asked. $\endgroup$
    – user21820
    Jun 16 '15 at 6:18

Not the answer you're looking for? Browse other questions tagged or ask your own question.