Problem 1730

To prove that starting from $4$, every natural number can be constructed by performing a finite number of operations $f$, $g$, and $h$ in some order, we will use a proof by contradiction.

1. Define the operations:
- $f(n) = 10n$
- $g(n) = 10n + 4$
- $h(n) = \frac{n}{2}$ if $n$ is even

2. Assume the contrary:
Suppose there exists a smallest natural number $A$ that cannot be constructed using the operations $f$, $g$, and $h$ starting from $4$.

3. Reachability of initial numbers:
- Starting from $4$:
$$4 \xrightarrow{h} 2 \xrightarrow{h} 1$$
- Therefore, $1, 2, 4$ can be reached.

4. **Reachability of $3$:**
- Starting from $2$:
$$2 \xrightarrow{f} 20 \xrightarrow{h} 10 \xrightarrow{h} 5 \xrightarrow{h} 3$$
- Therefore, $3$ can be reached.

5. **Reachability of $5$:**
- Starting from $1$:
$$1 \xrightarrow{f} 10 \xrightarrow{h} 5$$
- Therefore, $5$ can be reached.

6. General case analysis:
- Since $1, 2, 3, 4, 5$ can be reached, $A > 5$.
- Consider the form of $A$:
- If $A = 5n$, then $0 < n < A$ can be reached, but $A = h(f(n))$, contradiction.
- If $A = 5n + 1$, then $0 < 2n < A$ can be reached, but $A = h(h(g(2n)))$, contradiction.
- If $A = 5n + 2$, then $0 < n < A$ can be reached, but $A = h(g(n))$, contradiction.
- If $A = 5n + 3$, then $0 < 4n + 2 < A$ can be reached, but $A = j(4n + 2)$, contradiction.
- If $A = 25n + 4$, then $0 < 16n + 2 < A$ can be reached, but $A = k(h(h(g(16n + 2))))$, contradiction.
- If $A = 25n + 9$, then $0 < 10n + 1 < A$ can be reached, but $A = k(g(10n + 1))$, contradiction.
- If $A = 25n + 14$, then $0 < 8n + 4 < A$ can be reached, but $A = k(h(g(8n + 4)))$, contradiction.
- If $A = 25n + 19$, then $0 < 4n + 3 < A$ can be reached, but $A = k(f(4n + 3))$, contradiction.
- If $A = 125n + 24$, then $0 < 16n + 3 < A$ can be reached, but $A = k(j(f(16n + 3)))$, contradiction.
- If $A = 125n + 49$, then $0 < 32n + 12 < A$ can be reached, but $A = k(j(h(g(32n + 12))))$, contradiction.
- If $A = 125n + 74$, then $0 < 16n + 9 < A$ can be reached, but $A = k(j(g(16n + 9)))$, contradiction.
- If $A = 125n + 99$, then $0 < 64n + 50 < A$ can be reached, but $A = k(j(h(h(g(64n + 50)))))$, contradiction.
- If $A = 625n + 124$, then $0 < 256n + 50 < A$ can be reached, but $A = k(j(j(h(h(g(256n + 50))))))$, contradiction.
- If $A = 625n + 249$, then $0 < 64n + 25 < A$ can be reached, but $A = k(j(j(g(64n + 25))))$, contradiction.
- If $A = 625n + 374$, then $0 < 128n + 76 < A$ can be reached, but $A = k(j(j(h(g(128n + 76)))))$, contradiction.
- If $A = 625n + 499$, then $0 < 64n + 51 < A$ can be reached, but $A = k(j(j(f(64n + 51))))$, contradiction.
- If $A = 625n + 624$, then $0 < 512n + 510 < A$ can be reached, but $A = k(j(j(j(512n + 510))))$, contradiction.

7. Conclusion:
Since no such $A$ exists, every natural number can indeed be reached starting from $4$ using the operations $f$, $g$, and $h$.

$\blacksquare$