Problem 2126. Split bread like the Pharaohs - Egyptian fractions and greedy algorithm

Created by Muthu Annamalai

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>How would you split 5 loaves of bread among 8 people in all fairness? Get a hint from the Pharaohs. 5/8 = 4/8 + 1/8 , i.e. each receives 1/2 of loaf plus 1/8 - splitting 4 loaves into 1/2 and then the last loaf into 8 pieces.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Egyptian fraction is writing any rational number p/q in terms of unity fractions;</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[e.g. \n\n 3/4 = 1/2 + 1/4, OR \n = 1/3 + 1/4 + 1/6\n\n 13/48 = 1/4 + 1/48]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Write a program to return the Egyptian fraction of a given rational number p, q. You outputs in the above cases should be the series of denominator values,</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ i.e. egyptian_fraction( 13, 48) should return [4,48],]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>You can use simple greedy algorithm or alternatives.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>References</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr></w:pPr><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Egyptian_fraction\"><w:r><w:t>http://en.wikipedia.org/wiki/Egyptian_fraction</w:t></w:r></w:hyperlink></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr></w:pPr><w:r><w:t>AMS blog post by Tyler Clark (@tylermath12)</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://blogs.ams.org/jmm2014/2014/01/17/friday-morning-math-fun/\"><w:r><w:t>http://blogs.ams.org/jmm2014/2014/01/17/friday-morning-math-fun/</w:t></w:r></w:hyperlink></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr></w:pPr><w:r><w:t>Bonus points if you can enumerate all possible Egyptian fractions of (p,q), but thats a problem for another day.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>P.S: Updated test suite to check for proper solutions only</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

How would you split 5 loaves of bread among 8 people in all fairness? Get a hint from the Pharaohs. 5/8 = 4/8 + 1/8 , i.e. each receives 1/2 of loaf plus 1/8 - splitting 4 loaves into 1/2 and then the last loaf into 8 pieces.Egyptian fraction is writing any rational number p/q in terms of unity fractions;<pre class="language-matlab">e.g. 
</pre><pre> 3/4 = 1/2 + 1/4, OR 
 = 1/3 + 1/4 + 1/6</pre><pre> 13/48 = 1/4 + 1/48</pre>Write a program to return the Egyptian fraction of a given rational number p, q. You outputs in the above cases should be the series of denominator values,<pre> i.e. egyptian_fraction( 13, 48) should return [4,48],</pre>You can use simple greedy algorithm or alternatives.References<ol><li><a href = "http://en.wikipedia.org/wiki/Egyptian_fraction">http://en.wikipedia.org/wiki/Egyptian_fraction</a></li><li>AMS blog post by Tyler Clark (@tylermath12) <a href = "http://blogs.ams.org/jmm2014/2014/01/17/friday-morning-math-fun/">http://blogs.ams.org/jmm2014/2014/01/17/friday-morning-math-fun/</a></li><li>Bonus points if you can enumerate all possible Egyptian fractions of (p,q), but thats a problem for another day.</li></ol>P.S: Updated test suite to check for proper solutions only

Solve

Solution Stats

186 Solutions
55 Solvers

Last Solution submitted on Aug 25, 2020

Last 200 Solutions

Problem Comments

3 Comments

3 Comments

J.R.! Menzinger on 4 Feb 2014

Try to use "unique(floor(..." in the test cases. Isn't it Alfonso?? ;-)

David Verrelli on 26 Apr 2018

This problem is quite well constructed and described. However, per the WP article linked to, it is important to specify two additional requirements: 〔1〕 Denominators must be positive. This is not explicitly mentioned in the Problem Statement [although perhaps it's implied], and moreover it's not checked in the Test Suite. That means 3/4 = 1/(1) + 1/(-4) would be erroneously accepted. 〔2〕 Each of the denominators must be different/unique. That is enforced in the Test Suite, but there's no mention of it in the Problem Statement. —DIV

Jean-Marie Sainthillier on 16 Jul 2018

Can't submit a solution to this problem (temporary unavailability of MATLAB Service).

Solution Comments

Solution 389904

3 Comments

3 Comments

Marco Castelli on 23 Jan 2014

Sorry this is not the solution. Output is not an integer

James on 23 Jan 2014

Time to update the test suite again...

Muthu Annamalai on 24 Jan 2014

I'm always happy to have a learning opportunity

Solution 388965

2 Comments

2 Comments

Jon on 21 Jan 2014

While this meets the letter of the problem requirements, it clearly violates the spirit. I recommend using "unique(denom = egyptian_fraction(Vmin,Vmax));" to prevent this.

Muthu Annamalai on 21 Jan 2014

Interesting observation.

Solution 388505

1 Comment

1 Comment

Muthu Annamalai on 20 Jan 2014

Please resubmit your solution; previous test suite was buggy.

Problem Recent Solvers55

Problem Tags

egyptian fraction rats

Problem 2126. Split bread like the Pharaohs - Egyptian fractions and greedy algorithm

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers55

Suggested Problems

More from this Author10

Problem Tags

Problem 2126. Split bread like the Pharaohs - Egyptian fractions and greedy algorithm

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers55

Suggested Problems

More from this Author10

Problem Tags

Players