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

Difference between revisions of "2008 Indonesia MO Problems/Problem 8"

(→‎Solution 1)
(→‎Solution 1)
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://artofproblemsolving.com/wiki/index.php?title=2008_Indonesia_MO_Problems/Problem_8&oldid=227425"