Solution to the reciprocals problem

In my last blog I asked you to look at this problem, try to solve it, and tell me if you think it is too hard for a HS competition. (I meant to post this on WED so I posted it at 12:06AM East Coast Time. I didn't know that the blog is on Chicago Time. So it got posted on Tuesday. Oh well.) Here is the problem:

Prove or disprove: there exist natural numbers x₁,...,x₁₀ such that

1. 2011=x₁+... +x₁₀ and
2. 1=1/x₁+... +1/x₁₀.

Several solutions and some other points of interest about this problem are here. The answer is YES and here are the solutions that I know of -- both my solution and the ones emailed to me. (The explanation of how they were obtained are at the paper pointed to above.)

1. My Solution: 2,4,5,80,80,80,160,320,640,640. This used known theorems.
2. Sam Solution: 2,4,5,40,120,160,300,300,480,600. Sam is a HS senior who is very good at these contests. It took him 30 minutes,
3. David Eppstein Solution: 3,4,7,16,16,16,20,43,80,1806. This used a bit of advanced knowledge and some hand computations that were probably above what you want for a UMCP Math Competition.
4. Matt Howell Solution: 2,4,5,50,100,100,250,500,500,500 This solution could have been found by a HS student (it is similar to Sam's solution.) Matt has a BS in Math and Engineering and did the problem in 20 minutes.
5. An anonymous commenter send me 6,6,10,10,12,15,15,15,62,1860. This solution could have been found by a HS student (it is similar to Sam's solution.)
6. Another one from same anon: 6,8,8,8,12,15,16,16,62,1860 This solution could have been found by a HS student (it is similar to Sam's solution.)
7. Mike Roman Solution: 5,5,6,8,8,12,15,32,960,960

So what to make of this?

1. Much to my surprise, enough people got it right and in ways that a HS student could have gotten it. And one did- Sam took the real exam.
2. The systematic solution that I got required very little hand calculation. All of the others, which includes the one I think a HS student could have or did get, required quite a bit of hand calculation. That may be a reason to not ask it.
3. I wonder how many solutions there are. This could be figured out by a Dynamic Program but there may be issues with large ints. (See later in this blog.)
4. I wonder if there are any that have distinct numbers. This can also be figured out by a Dynamic Program, though there may be an easier way.
5. I wonder about the computational complexity of the following problems:
   1. Problem 1 Given a,b in N, does there exist x₁,...,x_a such that x₁+...+x_a=b and 1/x₁+...+1/x_a=1. (Can also ask with the stipulation that the x's are distinct.)
   2. Problem 2 Given a,b in N and r in Q, does there exist x₁,...,x_a such that x₁+...+x_a=b and 1/x₁+...+1/x_a=r. (Can also ask with the stipulation that the x's are distinct.)

Possible Dynamic Program (more likely you would do it as a recurrence but save all answers found and check to see if you have already computed it, to avoid recomputing.) Let f(a,b,c,r) (where a,b,c are naturals and r is rational) be

num of sols to x₁+...+x_a=b and 1/x₁+...+1/x_a=r. where c ≤ x₁ ≤ ... ≤ x_a.

Note that

1. f(1,b,c,r) = 1 if r=1/b and r ≥ c
2. f(a,b,c,r) = sum as x in {c,c+1,..., min(b,floor(a/r)) } of f(a-1,b-x,x,r-1/x)

(NOTE- Use f(a-1,b-x,x+1,r-1/x) if you want to enforce distinct solutions.)

A math point: Ronald Graham showed that, for all n ≥ 78, n can be written as a sum of natural numbers whose reciprocals sum to 1. The lower bound of 78 is tight: 77 cannot be. A sketch of a proof of this is in the file pointed to. (The proof I give is inspired by one of the comments on the blog. YEAH BLOG COMMENTERS!) (ADDED LATER- Ronald Graham actually proved that for all n &ge 78 n can be written as the sum of DISTINCT natural numbers such that... . The proof I presented in the pointed to document just gives nat numbers, not necc distinct ones.)