Prove every integer is obtained from functions

We are given the following operations:

$$f(n)=10n, g(n)=10n+4, h(n)=\frac{n}{2}$$, where $n$ is a positive integer (n must be even for $h(n)$.

Show that, beginning with $n=4$, every positive integer can be obtained using a finite number of composition of the operations in some order. For example, $5=h(f(h(h(4))))$.

I don't have any idea how to solve this question. I tried combining some of the operators to get terms like $h(g(n))=5n+2$, but that hasn't really got me anywhere. Can anyone help me with this question?

Also, is this is a well-studied area of mathematics, I would appreciate if you mentioned that in your answer. Thank you. Comes from 1991 IrMO

• Can you add and subract functions. e.g. h(h(g - f(n))) = 1 so h(h(g - f(n))) + ..... + h(h(g - f(n))) = m. Or can you only use the functions? – fleablood Oct 15 '15 at 20:33
• No, you cannot add or subtract functions, just compose them. – Cataline Oct 15 '15 at 20:49
• Hint: start with your final number and work backwards taking into account its last digit. Consider induction. – Théophile Oct 15 '15 at 20:56

Let's induct!

With a little effort, we can find that every number from 1 to 9 is attainable: \begin{align} &1 = h^2(4)\\ &2 = h(4)\\ &3 = h^3gh(4)\\ &4 = 4\\ &5 = h^3f(4)\\ &6 = h^2gh(4)\\ &7 = h^3g(4)\\ &8 = h^3gh^2gh(4)\\ &9 = h^4g^2h^2(4). \end{align}

Now assume we can attain every positive integer less than $n$, and consider the digit that $n$ ends in. Our goal will be to work backwards and show that there's an integer less than $n$ that we can attain from $n$ using the inverse of our functions. We'll do this by using $h^{-1}$ until our number ends in a 4, then using $g^{-1}$; but in the case where d = 0 or 5, we have to use $f^{-1}$.

Let $n = 10k + d, 0 \leq d \leq 9$. (Because we manually did the cases above, we can assume $k > 1$ to save us a minor headache.) We've got some cases:

\begin{align} &d=0: &f^{-1}(10k)& = k < 10k\\ &d = 1: &g^{-1}h^{-2}(10k+1)& = 4k < 10k+1\\ &d =2 : &g^{-1}h^{-1}(10k+2)& = 2k < 10k+2 \\ &d =3 : &g^{-1}h^{-3}(10k+3)& = 8k + 2 < 10k+3 \\ &d =4 : &g^{-1}(10k+4)& = k < 10k+4\\ &d =5 : &f^{-1}h^{-1}(10k+5)& = 2k+1 < 10k+5\\ &d =6 : &g^{-1}h^{-2}(10k+6)& = 4k + 2 < 10k+6\\ &d =7 : &g^{-1}h^{-1}(10k+7)& = 2k + 1 < 10k+7\\ &d =8 : &g^{-1}h^{-3}(10k+8)& = 8k + 6 < 10k+8. \end{align}

So in each of these cases, we've shown that some sequence of inverse functions gets us to a positive integer less than $n$; the reversed sequence of functions from that integer gets us to $n$. By the inductive hypothesis, we've shown that $n$ can be reached.

But there's a missing case, $d = 9$. We can obtain the result

$$g^{-1}h^{-4}(10k+9) = 16k + 14 > n.$$

I... don't actually see a clean, immediate way to get this number below $n$ without more casework on $k$, conditioning on what digit $16k+14$ ends in, and using our casework from above. Most of the even digit cases get to a number less than half of our initial number, which would get us to a number less than $8k+7$. Except for the $d=8$ case.

So for $n = 49$, we get to $g^{-1}h^{-4}(49) = 78$, and then $g^{-1}h^{-3}(78) = 62 > 49$. So we need $g^{-1}h^{-1}g^{-1}h^{-3}g^{-1}h^{-4}(49) = 12$ to get to a number less than 49. Yikes. I imagine you'd need some argument saying that you'll never get an integer that ends in nine from this process, and so you can always decrease your number by twenty percent by iterating this process, and so you'll get below $n$ in a finite number of steps. But that feels a bit disappointing.

I can't speak to how well-studied this field of mathematics is, but the problem is reminiscent of the Collatz Conjecture (sort of) and might fall within the purview of number theory?

• Thanks for the work so far. I'll try working on the $10k+9$ case – Cataline Oct 15 '15 at 21:38

Some investigation on the "ending in 9" case.

$9 \cdot 2^4 = 4 (\mod 10)$ so then we can do $g^{-1}$ which reduces a factor of 10.

The octave code:

a = ((mod((0:9)'*2.^(0:9) ,10) == 0) | (mod((0:9)'*2.^(0:9) ,10) == 4));

b = min((0:9).*a + (!a)*10,[],2)

Will give us the information lowest exponent of 2 which give either 0 or 4 mod 10.

this vector is: [0 2 1 3 0 1 2 1 3 4]

So as Ivoirians found, 9 is the only case $2^4 = 16 > 10$

b+b' now gives how many powers of 2 to be able to divide by 100. Here 6 is the magic exponent and then we are left with 9 followed by 3, 8 or 9. So if we can show that 3,8,9 don't occur after each other too often. We will probably need to investigate two-digit decimal numbers :

(((0:100)*2.^4-4)/10.*(mod((0:100),10)==9))

0 which end in 3,

2 which end in 8 and

0 which end in 9.

of the two which ended in 8 both will end in 4 and we should be done.