Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
Where did this problem come from? What is the motivation? Is $k$ allowed to be arbitrary, or is it intended to be fixed? –  Steven Stadnicki Dec 30 '13 at 17:40
    
$k$ depond on $n$ –  ziang chen Dec 30 '13 at 17:42
1  
@ziangchen Many find the use of imperative ("show") to be rude when asking for help; please consider rewriting your post. Also, what have you tried? –  Matthew Conroy Dec 30 '13 at 21:47
1  
This seems to be a very difficult, but interesting question. –  Peter Dec 30 '13 at 21:51
    
This might help ijpam.eu/contents/2013-85-1/7/7.pdf –  leonbloy Dec 30 '13 at 23:56
add comment

1 Answer

up vote 5 down vote accepted

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."

share|improve this answer
    
Thank you very much! –  ziang chen Dec 31 '13 at 0:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.