Difference between revisions of "1996 IMO Problems/Problem 3"

Revision as of 10:20, 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.

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}$ (Error compiling LaTeX. Unknown error_msg), 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$ .

@@ Line 6: / Line 6: @@
 ==Solution==
-{{solution}}
+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.
+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>.
+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>.
+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>.
+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>.
 ==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

Page

Toolbox

Search

Difference between revisions of "1996 IMO Problems/Problem 3"

Revision as of 10:20, 3 June 2024

Problem

Solution

See Also