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"

(Created page with "==Solution 1== Since <math>f: \mathbb{N}\rightarrow\mathbb{N}</math>, we know that <math>f(n)\ge 1</math>. Let <math>m</math>, <math>n</math> be <math>1</math>, <math>2</ma...")
 
(→‎Solution 1)
Line 29: Line 29:
 
<cmath>2f(1)-1 \equiv 0 \mod f(2)</cmath>
 
<cmath>2f(1)-1 \equiv 0 \mod f(2)</cmath>
  
−
We also know that <math>f(2) = f(1)f(1)-f(1)+1 = f(1)(f(1)-1)+1</math>. If <math>f(1)>1</math>, then <math>f(2)>f(1)</math>.  
+
Because <math>f(1) + f(2) = f(1)f(1) + 1</math>, we also know that <math>f(2) = f(1)f(1)-f(1)+1 = f(1)(f(1)-1)+1</math>. If <math>f(1)>1</math>, then <math>f(2)>f(1)</math>.  
  
  

Revision as of 15:09, 17 September 2024

Solution 1

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

Let $m$, $n$ be $1$, $2$, 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$

Expanding the right side, we get

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

Simplifying and multiplying both sides by 2, we get

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

\[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=227422"