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 "1996 IMO Problems/Problem 3"

(→‎Solution)
(→‎Solution)
Line 8: Line 8:
 
Plugging in m = 0, we get f(f(n)) = f(n) <math>\forall n \in S </math>.  
 
Plugging in m = 0, we get f(f(n)) = f(n) <math>\forall n \in S </math>.  
 
With m = n = 0, we get f(0) = 0.
 
With m = n = 0, we get f(0) = 0.
 +
 +
If there are no fixed points of this function greater than <math>0 </math>, then <math>f(x) = 0 \forall x \in \mathbb{N} </math>, which is a valid solution.
  
 
Let <math>n_{0} </math> be the smallest fixed point of <math>f(x) </math> such that <math>n_{0} > 0 </math>.  
 
Let <math>n_{0} </math> be the smallest fixed point of <math>f(x) </math> such that <math>n_{0} > 0 </math>.  
 
<math>\implies f(n_{0}) = n_{0} </math>.  
 
<math>\implies f(n_{0}) = n_{0} </math>.  
 
Plugging <math>m = n = n_{0} </math>, we get <math>f(2n_{0}) = 2f(n_{0}) </math>.  
 
Plugging <math>m = n = n_{0} </math>, we get <math>f(2n_{0}) = 2f(n_{0}) </math>.  
 +
  
 
By an easy induction, we get <math>f(kn_{0}) = kf(n_{0}) \forall k \in \mathbb{N} </math>.
 
By an easy induction, we get <math>f(kn_{0}) = kf(n_{0}) \forall k \in \mathbb{N} </math>.
 +
  
 
Let <math>n_{1} </math> be another fixed point greater than <math>n_{0} </math>.
 
Let <math>n_{1} </math> be another fixed point greater than <math>n_{0} </math>.
 
Let <math>n_{1} = qn_{0} + r </math>, where <math>r < n_{0} </math>.
 
Let <math>n_{1} = qn_{0} + r </math>, where <math>r < n_{0} </math>.
 +
  
 
So, <math>f(n_{1}) = f(qn_{0} + r) = f(r + f(qn_{0})) = f(r) + qn_{0} = r + qn_{0} </math>.
 
So, <math>f(n_{1}) = f(qn_{0} + r) = f(r + f(qn_{0})) = f(r) + qn_{0} = r + qn_{0} </math>.
  
−
<math>\implies f(r) = r </math>. But, <math>r < n_{0} \implies r = 0 </math>.
 
  
−
This means that the set of all fixed points of <math>f(x) </math> is
+
<math>\implies f(r) = r </math>. But, <math>r < n_{0} \implies r = 0 </math>. This means that the set of all fixed points of <math>f(x) </math> is <math>{0, n_{0}, 2n_{0}, 3n{0}, ...} </math>.
 +
 
 +
 
 +
Let <math>x < n_{0} </math> and <math>f(x) = b </math>. So, <math>b = f(x) = f(f(x)) = f(b) </math>. So, <math>b </math> is also a fixed point, which means that the functional values of non-fixed points are permutations of the fixed points. So let <math>f(k) = a_{k}n_{0} </math>, where <math>a_{k} \in \mathbb{N} </math>.
 +
 
 +
 
 +
Now let <math>n = qn_{0} + r </math>, where <math>r < n </math>.
 +
So <math>f(n) = f(qn_{0} + r) = f(r + f(qn_{0})) = f(r) + f(qn_{0}) = f(r) + qn_{0} = a_{r}n_{0} + qn_{0} = n_{0}\dot(a_{r} + q) </math>.
 +
So there are two general solutions, <math>f(x) = 0 </math> (where the only fixed point is 0) or <math>f(x) = n_{0}\dot(a_{r} + q) </math> where <math>n_{0} </math> is the smallest fixed point greater than 0 (in the second case), <math>f(r) = a_{r}n_{0} </math> and q is the quotient when <math>n </math> is divided by <math>n_{0} </math>.
  
 
==See Also==
 
==See Also==

Revision as of 12:00, 3 June 2024

Problem

Let $S$ denote the set of nonnegative integers. Find all functions $f$ from $S$ to itself such that

$f(m+f(n))=f(f(m))+f(n)$ $\forall m,n \in S$

Solution

Plugging in m = 0, we get f(f(n)) = f(n) $\forall n \in S$. With m = n = 0, we get f(0) = 0.

If there are no fixed points of this function greater than $0$, then $f(x) = 0 \forall x \in \mathbb{N}$, which is a valid solution.

Let $n_{0}$ be the smallest fixed point of $f(x)$ such that $n_{0} > 0$. $\implies f(n_{0}) = n_{0}$. Plugging $m = n = n_{0}$, we get $f(2n_{0}) = 2f(n_{0})$.


By an easy induction, we get $f(kn_{0}) = kf(n_{0}) \forall k \in \mathbb{N}$.


Let $n_{1}$ be another fixed point greater than $n_{0}$. Let $n_{1} = qn_{0} + r$, where $r < n_{0}$.


So, $f(n_{1}) = f(qn_{0} + r) = f(r + f(qn_{0})) = f(r) + qn_{0} = r + qn_{0}$.


$\implies f(r) = r$. But, $r < n_{0} \implies r = 0$. This means that the set of all fixed points of $f(x)$ is ${0, n_{0}, 2n_{0}, 3n{0}, ...}$.


Let $x < n_{0}$ and $f(x) = b$. So, $b = f(x) = f(f(x)) = f(b)$. So, $b$ is also a fixed point, which means that the functional values of non-fixed points are permutations of the fixed points. So let $f(k) = a_{k}n_{0}$, where $a_{k} \in \mathbb{N}$.


Now let $n = qn_{0} + r$, where $r < n$. So $f(n) = f(qn_{0} + r) = f(r + f(qn_{0})) = f(r) + f(qn_{0}) = f(r) + qn_{0} = a_{r}n_{0} + qn_{0} = n_{0}\dot(a_{r} + q)$. So there are two general solutions, $f(x) = 0$ (where the only fixed point is 0) or $f(x) = n_{0}\dot(a_{r} + q)$ where $n_{0}$ is the smallest fixed point greater than 0 (in the second case), $f(r) = a_{r}n_{0}$ and q is the quotient when $n$ is divided by $n_{0}$.

See Also

1996 IMO (Problems) • Resources
Preceded by
Problem 2 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 4
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1996_IMO_Problems/Problem_3&oldid=220016"