Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Tuesday, November 12, 2013
Four answers to the Recip problem
In my last post I asked you to solve the following question which
was from the Maryland Math Competition:
The inequalities 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.
Find five positive integers a,b,c,d,e such that
1/a + 1/b + 1/c + 1/d + 1/e = 1.
Prove that for any positive integer k GE 3 there exists positive intgers numbers d1,d2,...,dk
such that 1/d1 + ... + 1/dk.
The HS students had the following solutions.
I list the answers to part b first. I sketch the proofs. They are all by induction.
1) Use 1/n = 1/(n+1) + 1/n(n+1). This was the most common solution. This leads to (2,3,7,43,1806) for part a.
2) Since the question itself gives the solution for m=2 and 3 we only need P(k) --> P(k+2)
Use 1/n = 1/2n + 1/3n + 1/6n. This leads to (2,3,12,18,36).
One of the students later told me that knew the solution (i) but did it this way to
avoid having to multiply 42 by 43 which is needed to get part a using that solution.
3) Inductively that the largest denom n is even Use 1/n = 3/3n = 1/3n + 2/3n = 1/3n + 1/(3n/2)
Less than five students did 2b this way. This leads to (2,3,7,63,126) for 2a.
4) If (d1,...,dn) is a solution then so is (2,2xd1,...,2xdn).
Only two student did it this way. It leads to (2,4,6,14,84), which they both used.
NOBODY did in the non-inductive way mentioned in the last post.
There were THIRTY TWO solutions to 2b. Several people had their part 2a and 2b not
related to each other at all. This was far more solutions than I anticipated.
While grading I got good at adding reciprocals.
I list them in lex order along with how many people did that answer.
(This is likely approx- I may have miscounted a bit, but its basically right)
(2,3,7,43,1806) - 91 (linked to solution 1 above)
(2,3,7,48,336) - 3
(2,3,7,56,168) - 1
(2,3,7,63,126) - 6 (linked to solution 3 above)
(2,3,7,70,105) - 1
(2,3,8,25,600) - 1
(2,3,8,30,120) - 1
(2,3,8,32,96) - 6
(2,3,8,36,72) - 5
(2,3,8,42,56) - 11
(2,3,9,21,126) - 2
(2,3,9,24,72) - 4
(2,3,9,27,54) - 3
(2,3,10,20,60) - 5
(2,3,11,22,33) - 1
(2,3,12,15,60) - 1
(2,3,12,16,48) - 1
(2,3,12,14,84) - 2 (linked to solution 4 above)
(2,3,12,18,36) - 12 (linked to solution 2 above)
(2,4,5,25,100) - 3
(2,4,5,30,60) - 1
(2,4,6,14,84) - 3
(2,4,6,16,48) - 1
(2,4,6,18,36) - 2
(2,4,6,20,30) - 1
(2,4,7,12,42) - 4
(2,4,7,14,28) - 2
(2,4,8,12,24) - 6
(2,4,8,10,40) - 2
(2,5,6,10,30) - 1
(2,5,6,12,20) - 2
(3,4,5,6,20) - 3
This outcome is not a surprise! Approach 1) is hinted at by the given examples for k=3 and k=4.
ReplyDeleteI wonder what would have happened without providing these examples.
These concepts are well-known, see the entry "Egyptian Fraction" in wikipedia. Trigg in his "Mathematical Quickies" gave as a solution to the problem that every rational can be respresented as an Egyptian fraction: Write it as a sum of unit fractions and eliminate duplicates using 1/n = 1/(n+1) + 1/n(n+1). I think there is a problem remaining: Proof that this process terminates. Is this still a quicky?
ReplyDelete