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 "1977 IMO Problems/Problem 6"

(Created page with "= Problem = Let <math>f(n)</math> be a function <math>f: \mathbb{N}^{+}\to\mathbb{N}^{+}</math>. Prove that if <cmath> f(n+1) > f(f(n)) </cmath> for each positive integer <mat...")
 
Line 16: Line 16:
  
 
So the inductive step is complete. Therefore, by induction <math>f(n)=n</math> for all positive integers <math>n</math>.
 
So the inductive step is complete. Therefore, by induction <math>f(n)=n</math> for all positive integers <math>n</math>.
 +
 +
== See Also == {{IMO box|year=1977|num-b=5|after=Last Question}}

Revision as of 15:49, 29 January 2021

Problem

Let $f(n)$ be a function $f: \mathbb{N}^{+}\to\mathbb{N}^{+}$. Prove that if \[f(n+1) > f(f(n))\] for each positive integer $n$, then $f(n)=n$.

Solution

We will prove this via induction. First we will prove there is a $t$ such that $f(t)=1$ and then that $t=1$ is the only such solution.

Define the sequence $a_n$ with $a_0>1$ for $a_0\in \mathbb{N}$ and $a_k=f(a_{k-1}-1)$. By the given inequality we have that $f(a_n)>f(a_{n+1})$, this can be used to form a inequality chain of decreasing positive integers: \[f(a_0)>f(a_1)>f(a_2)>...\] By Infinite Descent, this sequence must terminate, and the only way it can terminate is if we input something into $f$ that is outside of its range. This can only happen if $a_n=1$ since the range and domain of $f$ are the positive integers. Since $a_0\neq 1$, there is a integer $t$ ($a_{n-1}-1$) such that $f(t)=1$.

Now if $t\neq 1$, then $f(t)=1>f(f(t-1))$, which is impossible since $f(f(t-1))\ge 1$ by the range of $f$, so we have $t=1$ is the only time when $f(t)=1$.

Now for the inductive step.

Assume that $f(n)=n$ for all $n<k$ and these are the only times these values occur. We will prove that $f(k)=k$ and that this is the only time this value occurs. Define the sequence $a_n$ similarly, except that $a_0>k$, by the reasoning above, there is a $a_m$ such that $f(a_m)=1$, by the inductive assumption, this means that $a_m=f(a_{m-1}-1)=1$, we can repeat the inductive assumption to get that $a_{m-k+1}=k$. This implies that $f(a_{m-k}-1)=k$. Thus, there is a $t$ such that $f(t)=k$.

Now for that $t$, we have $k>f(f(t-1))$, which means that $k+1>t$ by the inductive assumption which implies $t=k$ since we must have $t>k-1$, otherwise $f(t)<k$. So $t=k$ is the only time when $f(t)=k$

So the inductive step is complete. Therefore, by induction $f(n)=n$ for all positive integers $n$.

See Also

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