Results 1 to 6 of 6

Math Help - Help proving if this algorithm terminates

  1. #1
    Junior Member
    Joined
    Nov 2008
    Posts
    36

    Help proving if this algorithm terminates

    Ancient Egyptians were fond of writing general fractions as sums of fractions with unit numerator. Specifically, they would write 2/3 = 1/2 + 1/6,3/4 = 1/2 + 1/4 and, more exotically,6/7 = 1/2 + 1/3 + 1/42 . To be precise, we say that a rational number in the interval is written as an Egyptian fraction if it is written as a sum of a finite number of distinct unit fractions (so 2/17 = 1/17 + 1/17 is forbidden). Consider the following algorithm for writing a rational number (between 0 and 1) as an Egyptian fraction:

    Algorithm E: If for some r = 1/d, output "1/d". Otherwise, find the largest unit fraction 1/d that is less than r ; output "1/d +"; repeat with the rational number r - 1/d .

    Prove, using induction, that this process always terminates. (Hint: Try using induction on the numerator of the fraction.)



    Alright, this is what I have so far :

    Base case: R is of the form 1/d.
    If R is of the form 1/d, then the program terminates by the algorithm's definition

    So assume R = a/d, a != 0 and d > 0

    If a is 1, then the program terminates
    else a is greater than 1 and we apply r - 1/d

    Examine the case for a + 1, since a + 1 > 1, we apply the second part of the algorithm, namely we repeat with the new fraction r2 = r - 1/d
    since r = (a+1)/d,

    r2 = (a+1)/d - 1/d
    r2 = a/d +1/d - 1/d
    r2 = a/d

    Since we assume a/d is true, thus the algorithm terminates for all valid input.


    I know I am probably way of, because this part of computer science is not my strong part, so I ask for help any guidance will be greatly appreciated. Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    That does not work because the greatest unit fraction less than (or equal to) (a+1)/d is not in general 1/d. For example the greatest unit fraction less than 2/9 is 1/5, not 1/9. Actually I think it's never 1/d.

    Strong induction, a bit tricky

    Proof that the greedy algorithm for egyptian fractions terminates@Everything2.com
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2008
    Posts
    36
    Thanks for the reply and the link. I really do not want to copy other people's work.
    If one can provide me some foundation or some hints to work with, then I will greatly appreciate it.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Matter_Math View Post
    Thanks for the reply and the link. I really do not want to copy other people's work.
    If one can provide me some foundation or some hints to work with, then I will greatly appreciate it.
    Sounds like a good way to go. Hints then: don't try to reduce (a+1)/d to a/d. Rather, write an arbitrary rational 0 < x/y < 1 and assume x does not divide y, then specify an inequality that expresses "1/d is the largest unit fraction less than x/y" and proceed to show that x/y - 1/d has a numerator less than x.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2008
    Posts
    36
    So I am back to this problem. I skipped it until it was the last one left.

    So here is what I have so far.

    Base Case :
    If input r, is of the form 1/d, for some number d, then the algorithm haults.

    Inductive step :
    Assume the input r, is of the form x/y where not x|y and x != 1. Then 0 < x/y < 1.
    Now assume 1/d is the largest unit fraction less than x/y. Thus
    x/y - 1/d < x/y < 1
    x - y/d < x < y


    Am I taking the correct step? I am kind of stuck. I am reading your hints and I get it, but I cannot put it into proper notation. Thanks
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Matter_Math View Post
    So I am back to this problem. I skipped it until it was the last one left.

    So here is what I have so far.

    Base Case :
    If input r, is of the form 1/d, for some number d, then the algorithm haults.

    Inductive step :
    Assume the input r, is of the form x/y where not x|y and x != 1. Then 0 < x/y < 1.
    Now assume 1/d is the largest unit fraction less than x/y. Thus
    x/y - 1/d < x/y < 1
    x - y/d < x < y


    Am I taking the correct step? I am kind of stuck. I am reading your hints and I get it, but I cannot put it into proper notation. Thanks
    I'd say you're going in the right direction but should reformulate the inequality. Translating "1/d is the largest unit fraction less than x/y" will entail sandwiching x/y between two unit fractions, one of which is less than x/y, one of which is greater...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: June 19th 2010, 02:49 PM
  2. Proving an identity that's proving to be complex
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: July 21st 2009, 01:30 PM
  3. Proving division algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 1st 2009, 02:14 PM
  4. X Terminates in What Quadrant?
    Posted in the Trigonometry Forum
    Replies: 8
    Last Post: April 30th 2009, 09:58 AM
  5. Replies: 1
    Last Post: September 7th 2008, 07:47 AM

Search Tags


/mathhelpforum @mathhelpforum