China Mathematical Olympiad

We are going to prove a more general result: For any positive integer $r\ge 2$, there exists $N(r)\in \mathbb{N}$ such that for every $n\ge N(r)$, there are positive integers $a_1,a_2,\dots ,a_r$ satisfying $$\begin{array}{rl}n& =a_1+a_2+\cdots +a_r,1\le a_1<a_2<\dots \\ & <a_r,a_i\mid a_{i+1},i=1,2,\dots ,r-1.\end{array}$$

For $r=2$, we have $n=1+n-1$, then $N(2)=3$.

Suppose it is true for $r=k$, then for $r=k+1$ let $N(k+1)=4N(k{)}^3$. For any positive integer $n=2^{\alpha }(2l+1)\ge N(k+1)=4N(k{)}^3$, we have either $2^{\alpha }\ge 2N(k{)}^2$ or $2l+1>2N(k)$.

If $2^{\alpha }\ge 2N(k{)}^2$, there exists an even positive integer $2t\le \alpha$ such that $2^{2t}\ge N(k{)}^2$, then $2^t+1\ge N(k)$. By induction we get positive integers $b_1,b_2,\dots ,b_k$ such that $$2^t+1=b_1+b_2+\cdots +b_k,1\le b_1<b_2<\cdots <b_k,b_i\mid b_{i+1},i=1,2,\dots ,k-1.$$ Then $$\begin{array}{rl}{2}^{\alpha }=2^{\alpha -2t}\cdot 2^{2t}& =2^{\alpha -2t}[1+(2^t-1)](2^t+1)\\ & =2^{\alpha -2t}+2^{\alpha -2t}(2^t-1)b_1+2^{\alpha -2t}(2^t-1)b_2\\ & +\cdots +2^{\alpha -2t}(2^t-1)b_k.\end{array}$$ $$\begin{gathered} n=2^{\alpha -2t}(2l+1)+2^{\alpha -2t}(2^t-1)b_1(2l+1) \\ +\cdots +2^{\alpha -2t}(2^t-1)b_k(2l+1). \end{gathered}$$

If $2l+1>2N(k)$, then $l>N(k)$. By induction there exist positive integers $c_1,c_2,\dots ,c_k$ such that $l=c_1+c_2+\cdots +c_k$, $1\le c_1<c_2<\cdots <c_k$, $c_i\mid c_{i+1}$, $i=1,2,\dots ,k-1$. Then $$n=2^{\alpha }+2^{\alpha +1}{c}_1+2^{\alpha +1}{c}_2+\cdots +2^{\alpha +1}{c}_k,$$ which is what we want. This completes the proof.