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}$

  • $\begingroup$ Is this a variant of Q7 in RMO 2006? $\endgroup$ – SS_C4 Feb 23 '16 at 11:01
  • $\begingroup$ olympiads.hbcse.tifr.res.in/uploads/rmo-2006 $\endgroup$ – SS_C4 Feb 23 '16 at 11:03
  • $\begingroup$ @SS_C4 What about $a=b=4?$ $\endgroup$ – Igor Rivin Feb 23 '16 at 11:05
  • $\begingroup$ And why is $f(9) = f(8)?$ $\endgroup$ – Igor Rivin Feb 23 '16 at 11:06
  • 2
    $\begingroup$ @SatvikMashkaria So the question then basically becomes "Prove that there is such a journey for every natural number larger than $8$." $\endgroup$ – 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$

  • $\begingroup$ I think you meant y instead of x in your notes. $\endgroup$ – Evariste Feb 23 '16 at 12:56
  • $\begingroup$ 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 $\endgroup$ – Evariste Feb 23 '16 at 13:01
  • $\begingroup$ It seems that you need manual checks only for $x\in\{9,10,11,12,13,15\} $ $\endgroup$ – Hagen von Eitzen Feb 23 '16 at 13:18
  • $\begingroup$ ... 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$ $\endgroup$ – 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$,


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.