10
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ Is this a variant of Q7 in RMO 2006? $\endgroup$
    – SS_C4
    Feb 23, 2016 at 11:01
  • $\begingroup$ olympiads.hbcse.tifr.res.in/uploads/rmo-2006 $\endgroup$
    – SS_C4
    Feb 23, 2016 at 11:03
  • $\begingroup$ @SS_C4 What about $a=b=4?$ $\endgroup$
    – Igor Rivin
    Feb 23, 2016 at 11:05
  • $\begingroup$ And why is $f(9) = f(8)?$ $\endgroup$
    – Igor Rivin
    Feb 23, 2016 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, 2016 at 11:20

3 Answers 3

10
$\begingroup$

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$

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

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.

$\endgroup$
1
$\begingroup$

$\>$$\>$$\>$$\>$$\>$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$.

$\endgroup$

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.