5
$\begingroup$

Problem: Prove that all positive rational numbers can be expressed as the finite sum of different numbers $\displaystyle \frac {1} {n}$ ($n$ is a natural number).

Example: $\displaystyle \frac {19}{16}=1+ \frac {1}{8} + \frac {1}{16}.$

*We cant sum numbers as $\displaystyle \frac {3}{16}$ (denominator > 1) but we can sum $\displaystyle \frac {1}{8}+ \frac {1}{16}.$

Any solutions? Suggestions?

  • 2
    So, [Egyptian fractions](http://mathworld.wolfram.com/EgyptianFraction.html)?2011-05-15
  • 0
    You might want to say **positive** rational numbers since negative rationals obviously cannot be formed with numerator 1 and natural-number denominators. (The Putnam problem cited by Chandru1 specifies that the numbers be positive.)2011-05-15
  • 2
    @Fixee, natural numbers are positive.2011-05-15
  • 2
    @quanta: Exactly. Which is why it's unlikely you can form a negative **rational** number via a sum of fractions with 1 over a **natural** number.2011-05-15

1 Answers 1

6

This is a putnam problem. For a complete solution please look here.

  • Take a look at this article as well: J.C.Owings, American Mathematical Monthly Vol. 75 (1968), Pages $777-778$.
  • 1
    For those that cannot follow the link, it essentially says that a greedy algorithm works: simply keep subtracting the largest reciprocal not already used which is less than the residual, and eventually this will terminate because, once you stop using the initial terms of the harmonic series, the numerator of the residual will strictly reduce with each step until it reaches zero.2011-05-15
  • 0
    @tomerg: Please accept an answer so that this question is not in the unanswered list.2011-05-17
  • 0
    Jstor link for that article: http://www.jstor.org/stable/23152112011-11-27