Monday, November 11, 2013

A problem on Reciprocals

(I thought I had posted this a while back but I can't find it in past blogs
so I think I did not. I DID post a diff problem on reciprocals.)

Here is the question I graded a while back on a  Maryland Math Olympiad.
I request that you do it and post your answer as a comment- I'll be curious
how your answers compare to the students who took it.
I will post the solutions the students used in my next post and comments
on how they were similar or different than yours.
The students had two hours to do five problems.
This was problem 2.

The equalities 1/2 + 1/3 + 1/6 = 1 and 1/2 + 1/3 + 1/7 + 1/42 = 1
express 1 as a sum of three (resp. four) reciprocals.

PART A: Find five distinct positive integers a,b,c,d,e  such that

       1/a + 1/b + 1/c + 1/d + 1/e = 1.


PART B: Prove that for any positive integer k  GE 3 there exists k distinct positive intgers numbers d1,...,dk such that

1/d1 + 1/d2 + ... + 1/dk = 1.

17 comments:

  1. m >= should be k >= 3.

    ReplyDelete
  2. Go inductively from (d1, d2, ..., dk) to (2, 2*d1, 2*d2, ..., 2*dk).

    ReplyDelete
  3. PART B: typo: m => k .

    ReplyDelete
  4. Seems pretty simple, unless I am missing some subtlety or making a silly mistake...

    A: Double all of the denominators in the second example, yielding 1/4 + 1/6 + 1/14 + 1/84 = 1/2. Then 1/2 + 1/4 + 1/6 + 1/14 + 1/84 = 1, so (2,4,6,14, 84) works.

    B: Same trick applied repeatedly to the first example can be used to generate sets of k such distinct integers for any k >= 3:

    1/6 + 1/3 + 1/2 --> 2,3,6
    (1/12 + 1/6 + 1/4) + 1/2 --> 2,4,6,12
    (1/24 + 1/12 + 1/8 + 1/4) + 1/2 --> 2,4,8,12, 24
    (1/48 + 1/24 + 1/16 + 1/8 + 1/4) + 1/2 --> 2, 4,8, 16, 24, 48
    ..and so on...

    From this we get the closed form: Use the set of k integers (k >= 3): 3 * 2^(k-3) , 3 * 2^(k-2) , and 2^i for i from 1 to k-2,

    My typesetting skills fail me at this point, but a simple proof by induction on k with base case k=3 should suffice to verify.


    ReplyDelete
  5. Take a solution for k. Double each number in the solution, so that the sum is 1/2, and add in 1/2. This gives a solution for k+1.

    Russell

    ReplyDelete
  6. Typos are fixed.
    Solutions give so far are correct. There is more than one solution and I'll be curious how your ccompare with the students, which I will give tommorow.

    ReplyDelete
  7. PART A:

    1/2+1/3+1/7+1/43+1/1806 = 1

    PART B:

    Suppose, for induction, it holds for all k-1 >= 3.

    Claim:

    1/d_1 + 1/d_2 + ... + 1/d_{k-2} + 1/(d_{k-1} + 1) + 1/(d_{k-1}(d_{k-1}+1)) = 1

    The last two terms of this series are clearly equal to 1/d_{k-1} since

    1/(d_{k-1} + 1) + 1/(d_{k-1}(d_{k-1}+1)) = (d_{k-1} + 1)/(d_{k-1}(d_{k-1}+1)) = 1/d_{k-1}

    Finally, by induction, the first k-2 terms are equal to 1 - d_{k-1}.

    ReplyDelete
  8. Nice problem, but almost too easy for a math olympiad.

    PART A: a=2, b=3, c=7, d= 43, e=1806(=42*43).

    PART B: By induction on k.
    For k=3 we have d_1 = 2, d_2 = 3, d_3 = 6.
    Step: Let 1/d_1 + ... + 1/d_i = 1.
    Claim: There exist x,y s.t. 1/d_i = 1/x + 1/y.
    Proof of Claim: Choose x = d_i +1. Thus 1/d_i = 1/(d_i+1) + 1/y, which yields
    1/y = 1/d_i - 1/(d_i +1) = 1/(d_i(d_i + 1)). Hence we have y = d_i(d_i +1).

    ReplyDelete
  9. It's interesting that everyone seems to be doing this by induction. It seemed most natural to me to do it directly: take the first k-2 integers as the first k-2 powers of two, i.e. 2, 4, ... 2^(k-2). Then we need two more integers such that the sum of their reciprocals is 2^(k-2); 2^(k-2)+1 and (2^(k-2))(2^(k-2)+1) will work, just as 1/7+1/42=1/6 does in the example.

    For example, this gives the answer for part A as 2, 4, 8, 9, 72(=8*9).

    ReplyDelete
  10. a typo: The inequalities - should be "The equalities"

    ReplyDelete
  11. start with
    1/2 + 1/4 + 1/8

    1/2
    3/4
    7/8
    need 1/8 or 2/16 or 3/24

    3/24 = 1/12 + 1/24

    so 1/2 + 1/4 + 1/8 + 1/12 + 1/24

    ReplyDelete
  12. The induction solution is nice. Here is an alternate solution that keeps expanding the last term:
    Start with 1/2+1/3+1/6
    Invariant: the last term is of the form 1/2d
    Repeatedly replace the last term with 1/3d and 1/6d, until you have k terms

    This gives the solutions:
    1/2+1/3+1/6
    1/2+1/3+1/9+1/18
    1/2+1/3+1/9+1/27+1/54
    1/2+1/3+1/9+1/27+1/81+1/162
    ...

    ReplyDelete
  13. 1/2, 1/3, 1/12, 1/18, 1/36, recursively using the solutions you gave to express 1/6 as the sum of 3 reciprocals. you can do this again do get andy number

    ReplyDelete
  14. 1/2 + 1/4 + 1/8 + 1/12 + 1/24 = 1

    Can prove that for any n,

    [Summation from m=1 to n-2 of (1/2^m)] + 1/(3*2^(n-1)) + 1/(3*2^n) == 1

    ReplyDelete
  15. http://math.stackexchange.com/questions/290435/unusual-5th-grade-problem-how-to-solve-it/290446

    ReplyDelete
  16. Hi,

    Part A) replace 1 / 42 with 1 / 43 + 1 / (42 *43)
    Part B)
    Lemma: For any integer "d > 0", 1 / d = 1 / (d + 1) + 1 / (d (d + 1))
    Proof: 1 / (d + 1) + 1 / (d ( d + 1)) = 1 / (d + 1) * (1 + 1 / d) = 1 / d.

    Proof of B: For some "k", we have d_1 < ... < d_k whose sum of reciprocals adds up to 1.0. Using the lemma, replace d_k with 1 / (d_k + 1) and 1 / (d_k (d_k + 1)). Now you have a seq. of k + 1 numbers adding up to 1.0 which are all distinct.

    ReplyDelete