# Prove that $f(x)=8$ for all natural numbers $x\ge{8}$

A function $f$ is such that $$f(a+b)=f(ab)$$ for all natural numbers $a,b\ge{4}$ and $f(8)=8$. Prove that $f(x)=8$ for all natural numbers $x\ge{8}$

• Is this a variant of Q7 in RMO 2006? – SS_C4 Feb 23 '16 at 11:01
• @SS_C4 What about $a=b=4?$ – Igor Rivin Feb 23 '16 at 11:05
• And why is $f(9) = f(8)?$ – Igor Rivin Feb 23 '16 at 11:06
• @SatvikMashkaria So the question then basically becomes "Prove that there is such a journey for every natural number larger than $8$." – Arthur Feb 23 '16 at 11:20

Yes. It is true that $f(x) = 8 \quad \forall\;\;\; x \in N$

Manually, we can prove this for $x \le 20$.

Now, let $x$ be even. $x = 2y$ for some $y$. $$f(2y)=f((2y-4) +(4))=f(4(2y-4))=f(8(y-2))=f(8+y-2)=f(y+6)$$ Note: This is true only if the $y-2$ factor is greater than $4$, so let $y \ge 6$.

Similarly, if $x$ is odd, $x = 2y + 1$ for some $y$. $$f(2y+1)=f((2y-4)+5)=f(5(2y-4))=f(10(y-2))=f(10 + y-2)=f(y+8)$$ Note: Similarly, this has the same condition $y \ge 6$.

And we can see that $2y > y+6$ and $2y+1 > y+8$ for $y\ge6$. ($y > 7$ for the second case). Therefore, for any $f(m)$, we can find $f(n)=f(m)$ for $n < m$. Thus after reducing, we get a number lesser than 20 which can be proved manually equal to $8$.

Therefore $f(x) = 8\;\;\; \forall \;\;\; x \in N$

• I think you meant y instead of x in your notes. – Evariste Feb 23 '16 at 12:56
• There's still the "x-2 factor" which should be "y-2" (I can't edit it myself because it's only a few characters) in your first note, no biggie though – Evariste Feb 23 '16 at 13:01
• It seems that you need manual checks only for $x\in\{9,10,11,12,13,15\}$ – Hagen von Eitzen Feb 23 '16 at 13:18
• ... and for the first few of these we have for example $8\to 16\to 64\to 20\to 9$, $20\to 100\to 25\to 10$, $20\to 96\to 28\to 11$ – Hagen von Eitzen Feb 23 '16 at 13:30

$\>$$\>$$\>$$\>$$\>$SS_C4's answer has two problems; the untrue claim that $2y>y+6$, for $y\geq 6$, and not demonstrating that $f(x)=f(8)$, for $9\leq x<17$, but SS_C4's proof can be saved as follows. The basic ideas belong to SS_C4. The value of $f(8)$ is immaterial. Lower-case Latin letters, except $f$, denote positive integers.

(A) $f(9)=f(4+5)=f(20)=f(4+16)=f(64)=f((8)(8))=f(16)=f((4)(4))=f(8)$.

(B) $f(10) = f(5+5)=f(25)=f(5+20)=f(100)=f((10)(10))=f(20)=f(8)$, by (A).

(C) $f(11)=f(4+7)=f(28)=f(4+24)=f(96)=f((8)(12))=f(20)=f(8)$, by (A).

(D) $f(12)=f(5+7)=f(35)=f(5+30)=f(150)=f((10)(15))=f(25)=f(8)$, by (B).

(E) $f(13)=f(5+8)=f(40)=f((4)(10))=f(14)=f(6+8)= f(48)=f((4)(12))=$ $\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$f(16)=f(8)$, by (A).

(F) $f(15)=f(4+11)=f(44)=f(4+40)=f(160)=f((8)(20))=f(28)=f(8)$, by (C). $\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>$$\>Suppose f(x) \neq f(8), for some x\geq9. Let m=Min\{x|x\geq9 and f(x)\neq f(8)\}. m \geq 17, by (A) - (F). \>$$\>$$\>$$\>$$\>$$\>$Suppose $m$ is even. Then, $m=2y$. Thus, $y\geq 9, y-2\geq7, 2y-4\geq14$ and $15\leq y+6<2y=m$. Therefore, by the definition of $m$,

$\>$$\>$$\>$$\>$$\>$$\>$$\>$$f(8)=f(y+6)=f(8+(y-2))=f(8(y-2))=f(4(2y-4))=f(2y)=f(m), contradicting the definition of m. Thus, m is odd. So, m=2y+1. Therefore, y\geq 8,y-2\geq6, 2y-4\geq12 and 16\leq y+8<2y+1=m. Hence, by the definition of m, \>$$\>$$\>$$\>$$\>$$\>$$f(8)=f(y+8)=f(10+(y-2))=f(10(y-2))=f(5(2y-4))= \>$$\>$$\>$$\>$$\>$$\>$$f(5+(2y-4))=f(2y+1)=f(m),$

again contradicting the definition of $m$. Thus, $f(x)=f(8)$, for $x\geq9$.

For $$x\geq 4$$, we have $$f(x+5)=f(5x)=f(4x+x)=f(4x^2)=f(2x\cdot 2x)=f(4x)=f(x+4)$$ so $$f$$ is constant over $$[8,\infty)$$ as desired.