1994 OIM Problems/Problem 6

Revision as of 13:37, 13 December 2023 by Tomasdiaz (talk | contribs) (Created page with "== Problem == Show that every natural number <math>n \le 2^{1,000,000}</math> can be obtained after 1 by doing less than 1,100,000 additions; more precisely, there is a finite...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Problem

Show that every natural number $n \le 2^{1,000,000}$ can be obtained after 1 by doing less than 1,100,000 additions; more precisely, there is a finite sequence of natural numbers

\[x_0, x_1, \cdots , x_k \; \text{with }\; k \le 1,100,000,\; x_0=1,\; x_k=n,\]

such that for each $i=1,2, \cdots ,k$, there exist $r$, $s$, with $0 \le r < i$, $0 \le s$, $0 \le i$, and $x_i=x_r+x_s$.

~translated into English by Tomas Diaz. ~orders@tomasdiaz.com

Solution

This problem needs a solution. If you have a solution for it, please help us out by adding it.

See also

https://www.oma.org.ar/enunciados/ibe9.htm