Prove that $ x_1+ \dotsb + x_k=n, \frac1{x_1}+ \dotsb + \frac1{x_k}=1$

How would one prove that there exists a positive integer $N$ such that, for every positive integer $n\gt N$, there exist $k$ (depending on $n$) positive integers $x_1,x_2,\dotsc,x_k$ such that

1) $x_1\lt x_2\lt \dotsc \lt x_k$;

2) $x_1+ x_2+ \dotsb + x_k=n$;

3) $\frac1{x_1}+ \frac1{x_2}+ \dotsb + \frac1{x_k}=1$.

I have no clue about it. Could anyone help me? Thanks a lot.

P.S. I encountered it when surfing the Internet. I only know the problem was from a math student who got a perfect score on the IMO.

Solution 1:

Graham published a proof of this for $N = 77$ in 1963 as "A Theorem on Partitions," Journal of the Australian Mathematical Society 3 (1963), pp. 435-441.

His proof is constructive and fairly short, but it does require a long table of decompositions for relatively small values of $n$. It would be interesting to see a non-constructive proof that doesn't require such a long list.

Here's his proof. First, he gives decompositions for all $n$ from 78 to 167 and all odd $n$ from 169 to 333. Then he says, "Now notice that each of the transformations $$ (a) \:\:\:\:1 = \frac{1}{d_1} + \cdots + \frac{1}{d_k} = \frac{1}{2} + \frac{1}{2d_1} + \cdots + \frac{1}{2d_k}$$ and $$ (b) \:\:\:\:1 = \frac{1}{d_1} + \cdots + \frac{1}{d_k} = \frac{1}{3} + \frac{1}{7} + \frac{1}{78} + \frac{1}{91} + \frac{1}{2d_1} + \cdots + \frac{1}{2d_k}$$ keeps the denominators distinct as long as no $d_i$ is 1 or 39. The new sums of the denominators are $2U+2$ and $2U+179$ respectively, where $$U = d_1 + d_2 + \cdots + d_k.$$ Since no 1 or 39 is used in the table, then by using (a) we can first extend the table to the even integers from $2 \cdot 88 + 2 = 168$ through $2 \cdot 166 + 2 = 334$ where none of the new denominators is 1 or 39. Then by using (a) and (b) we can next extend the table from $2 \cdot 78 + 179 = 335$ to $2 \cdot 334 + 2 = 670$. But none of the new denominators is 1 or 39 so we can again extend the table, and so on. This proves the theorem."