Art of Problem Solving
Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2008 Indonesia MO Problems/Problem 8: Difference between revisions

← Older editNewer edit →
Victorzwkao (talk | contribs)
editor
21 edits
Victorzwkao (talk | contribs)
editor
21 edits
Line 13: Line 13:
From the last 2 equations, we get that <math>\frac{1}{2}(f(2)^2+1)=f(4)=f(3)(f(1)-1)+1</math>
From the last 2 equations, we get that <math>\frac{1}{2}(f(2)^2+1)=f(4)=f(3)(f(1)-1)+1</math>


Since <math>f(3) = f(2)(f(1)-1)+1</math>, substituting, we get <math>\frac{1}{2}(f(2)^2+1)=(f(2)(f(1)-1)+1)(f(1)-1)+1</math>
Since <math>f(3) = f(2)(f(1)-1)+1</math>, substituting, we get  


Expanding the right side, we get
<cmath>\frac{1}{2}(f(2)^2+1)=(f(2)(f(1)-1)+1)(f(1)-1)+1</cmath>
 
<cmath>\frac{1}{2}(f(2)^2+1)=f(2)f(1)^2-f(2)f(1)+f(1)-f(2)f(1)-f(2)-1+1</cmath>
<math>\frac{1}{2}(f(2)^2+1)=f(2)f(1)^2-f(2)f(1)+f(1)-f(2)f(1)-f(2)-1+1</math>
<cmath>f(2)^2+1=2f(2)f(1)^2-2f(2)f(1)+2f(1)-2f(2)f(1)-2f(2)</cmath>
 
Simplifying and multiplying both sides by 2, we get
 
<math>f(2)^2+1=2f(2)f(1)^2-2f(2)f(1)+2f(1)-2f(2)f(1)-2f(2)</math>


If we take modulo of f(2) on both sides, we get
If we take modulo of f(2) on both sides, we get

Revision as of 15:18, 17 September 2024

Solution 1

Since $f: \mathbb{N}\rightarrow\mathbb{N}$, we know that $f(n)\ge 1$.

Let $m$, $n$ be $1$, $1$, respectively. Then, $f(1) + f(2) = f(1)f(1) + 1$.

Let $m$, $n$ be $1$, $2$, respectively. Then, $f(2) + f(3) = f(1)f(2)+1$

Let $m$, $n$ be $1$, $3$, respectively. Then, $f(3) + f(4) = f(1)f(3)+1$

Let $m$, $n$ be $2$, $2$, respectively. Then, $f(4) + f(4) = f(2)f(2)+1$

From the last 2 equations, we get that $\frac{1}{2}(f(2)^2+1)=f(4)=f(3)(f(1)-1)+1$

Since $f(3) = f(2)(f(1)-1)+1$, substituting, we get

\[\frac{1}{2}(f(2)^2+1)=(f(2)(f(1)-1)+1)(f(1)-1)+1\] \[\frac{1}{2}(f(2)^2+1)=f(2)f(1)^2-f(2)f(1)+f(1)-f(2)f(1)-f(2)-1+1\] \[f(2)^2+1=2f(2)f(1)^2-2f(2)f(1)+2f(1)-2f(2)f(1)-2f(2)\]

If we take modulo of f(2) on both sides, we get

\[1 \equiv 2f(1) \mod f(2)\]

\[2f(1)-1 \equiv 0 \mod f(2)\]

Because $f(1) + f(2) = f(1)f(1) + 1$, we also know that $f(2) = f(1)f(1)-f(1)+1 = f(1)(f(1)-1)+1$. If $f(1)>1$, then $f(2)>f(1)$.


Suppose $f(1)>1$:

since $f(2)>f(1)$, we have $2f(2)>2f(1)-1>0$. Or that $2>\frac{2f(1)-1}{f(2)}>0$. Thus, \[\frac{2f(1)-1}{f(2)}=1\] \[2f(1)-1=f(2)=f(1)f(1)-f(1)+1\] \[f(1)^2-3f(1)+2=0\] \[(f(1)-2)(f(1)-1)=0\] Thus, $f(1)=1$ or $f(1)=2$.


case 1: $f(1)=1$

Let $m=1$, and $n$ be an arbitrary integer $\ge 1$. Then, \[f(n) + f(n+1) = f(1)f(n) + 1\] \[f(n) + f(n+1) = f(n) + 1\] \[f(n+1) = 1\] Thus, $f(n) = 1$.


case 2: $f(1)=2$

Let $m=1$, and $n$ be an arbitrary integer $\ge 1$. Then, \[f(n) + f(n+1) = f(1)f(n) + 1\] \[f(n) + f(n+1) = 2f(n) + 1\] \[f(n+1) = f(n)+1\] This forms a linear line where $f(1)=2$ Thus, $f(n)=n+1$

Upon verification for $f(n) = 1$, we get \[f(mn)+f(m+n)=f(m)f(n)+1\] \[1+1=1+1\]

Upon verification for $f(n) = n+1$, we get \[f(mn)+f(m+n)=f(m)f(n)+1\] \[mn+1+m+n+1=(m+1)(n+1)+1\] \[mn+m+n+2=mn+m+n+2\]

Thus, both equations, $f(n) = 1$ and $f(n) = n+1$ are valid

Retrieved from "https://wiki.aopstest.com/wiki/index.php?title=2008_Indonesia_MO_Problems/Problem_8&oldid=227425"