34
$\begingroup$

Suppose for $a_1,a_2,\cdots ,a_n$, where $a_i$ is a positive integer $$\frac1{a_1}+\frac1{a_2}+\cdots+\frac1{a_n}=k$$, and $k$ is an integer. Is it true that there always exist $1\leq i_1<i_2<\cdots < i_m\leq n$, such that $$\frac1{a_{i_1}}+\frac1{a_{i_2}}+\cdots+\frac1{a_{i_m}}=1$$?

I couldn't find any counterexamples or prove that we can always find such subset.

$\endgroup$
  • 1
    $\begingroup$ I think I've seen something like this in one of the books from mathematical Olympiads, so i think it's true $\endgroup$ – Jakobian Jul 20 '18 at 17:50
  • $\begingroup$ yes, consider what is $k-1$ and go from there $\endgroup$ – Vasya Jul 20 '18 at 17:55
33
$\begingroup$

How about $\frac 13+4\cdot \frac 15+6\cdot \frac 17+\frac 1{105}=2$?

If we put them over a common denominator, it is $105$, so we need to find a subcollection of $1,21,21,21,21,15,15,15,15,15,15,35$ that sums to $105$. If we take all the ones ending in $1$ to get a multiple of $5$ we have $85$ and can't complete it. If we exclude all the ones ending in $1$ we are stuck again.

For a smaller list allowing repetitions, there is $\frac 12+2\cdot \frac 13+4\cdot \frac 15+\frac 1{30}=2$ I think eight terms will be hard to beat.

Added: We can find a set with no repetition. I find the reciprocals of $2,3,4,5,7,8,9,11,13,16,144,2574,30030$ add to $2$ and no subset of the reciprocals add to $1$.

$\endgroup$
  • 5
    $\begingroup$ +1 What if the $a_i$ must be distinct? (Accepted answer, so this is not what the OP asked.) $\endgroup$ – Ethan Bolker Jul 20 '18 at 18:05
  • 1
    $\begingroup$ @EthanBolker: I was just starting to think about it. My thought is to start with $\frac 12+\frac 13+\frac 14+\frac 15=\frac {77}{60}$ and be greedy-take the largest reciprocal that avoids summing to $1$ but stays below or equal to $2$. We have to skip $\frac 16$ but there aren't that many to avoid, I think. $\endgroup$ – Ross Millikan Jul 20 '18 at 18:11
  • 3
    $\begingroup$ @RossMillikan: This seems to create a bit of a mess as more primes get introduced. But if we restrict to denominators having no prime factors greater than 7 the set of denominators $(2, 3, 4, 5, 7, 8, 9, 10, 12, 14, 16, 49, 35280)$ works. $\endgroup$ – Michael Lugo Jul 20 '18 at 18:40
  • 2
    $\begingroup$ @MichaelLugo Indeed, even with an entirely greedy strategy, I obtained the set $(2,3,4,5,7,8,9,10,11,12,16,1047,1138151,3145940416080)$. $\endgroup$ – LegionMammal978 Jul 20 '18 at 18:43
  • 4
    $\begingroup$ I went with the entirely-greedy strategy, saw 1138151, and thought "oh, these numbers are going to get too big, let's start over". If only I'd known that I only needed one more step... $\endgroup$ – Michael Lugo Jul 20 '18 at 19:17
10
$\begingroup$

This is an expansion of @Michael Lugo's comment.

The proposition is not true even if all denominators have to be unique. A counterexample: $(2,3,4,5,7,8,9,10,12,14,16,49,35280)$.

Here is a Python program which checks that these numbers are different, and the sum of the reciprocals of these numbers is 2, and that there is no subset of these numbers, where the sum of the reciprocals of the numbers in the subset is 1:

import fractions, itertools
R = fractions.Fraction
D = (2,3,4,5,7,8,9,10,12,14,16,49,35280)
assert len(D) == len(set(D))  # All elements are different.
assert sum(R(1,d) for d in D) == 2  # Sum of reciprocals is 2.
for s in xrange(len(D) + 1):
  for e in itertools.combinations(D, s):
    assert sum(R(1,d) for d in e) != 1  # Sum of reciprocals in subset is not 1.
$\endgroup$
  • $\begingroup$ I ran that with my $D$. Does getting no output mean that all the assertions came out true? $\endgroup$ – Ross Millikan Jul 20 '18 at 19:39
  • $\begingroup$ @RossMillikan: Correct: no output means that assertions are true. Add assert 3 == 4 to the end of the program to get some output. $\endgroup$ – pts Jul 20 '18 at 19:45
  • $\begingroup$ Thanks. That worked. I had made a spreadsheet to check my set but appreciate an independent approach. $\endgroup$ – Ross Millikan Jul 20 '18 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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