Art of Problem Solving
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

1969 Canadian MO Problems/Problem 8: Difference between revisions

4everwise (talk | contribs)
92 edits
No edit summary
 
Temperal (talk | contribs)
3,154 edits
box
 
Line 1: Line 1:
== Problem ==
== Problem ==
Let <math>\displaystyle f</math> be a function with the following properties:
Let <math>f</math> be a function with the following properties:


1) <math>\displaystyle f(n)</math> is defined for every positive integer <math>\displaystyle n</math>;
1) <math>f(n)</math> is defined for every positive integer <math>n</math>;


2) <math>\displaystyle f(n)</math> is an integer;
2) <math>f(n)</math> is an integer;


3) <math>\displaystyle f(2)=2</math>;
3) <math>f(2)=2</math>;


4) <math>\displaystyle f(mn)=f(m)f(n)</math> for all <math>\displaystyle m</math> and <math>\displaystyle n</math>;
4) <math>f(mn)=f(m)f(n)</math> for all <math>m</math> and <math>n</math>;


5) <math>\displaystyle f(m)>f(n)</math> whenever <math>m>n</math>.
5) <math>f(m)>f(n)</math> whenever <math>m>n</math>.


Prove that <math>\displaystyle f(n)=n</math>.
Prove that <math>f(n)=n</math>.


== Solution ==
== Solution ==
It's easily shown that <math>\displaystyle f(1)=1</math> and <math>\displaystyle f(4)=4</math>. Since <math>\displaystyle f(2)<f(3)<f(4),</math> <math>\displaystyle f(3) = 3.</math>
It's easily shown that <math>f(1)=1</math> and <math>f(4)=4</math>. Since <math>f(2)<f(3)<f(4),</math> <math>f(3) = 3.</math>


Now, assume that <math>\displaystyle f(2n+2)=f(2(n+1))=f(2)f(n+1)=2n+2</math> is true for all <math>\displaystyle f(k)</math> where <math>\displaystyle k\leq 2n.</math>   
Now, assume that <math>f(2n+2)=f(2(n+1))=f(2)f(n+1)=2n+2</math> is true for all <math>f(k)</math> where <math>k\leq 2n.</math>   


It follows that <math>\displaystyle 2n<f(2n+1)<2n+2.</math> Hence, <math>\displaystyle f(2n+1)=2n+1</math>, and by induction <math>\displaystyle f(n) = n.</math>
It follows that <math>2n<f(2n+1)<2n+2.</math> Hence, <math>f(2n+1)=2n+1</math>, and by induction <math>f(n) = n</math>.


----
{{Old CanadaMO box|num-b=7|num-a=9|year=1969}}
* [[1969 Canadian MO Problems/Problem 7|Previous Problem]]
* [[1969 Canadian MO Problems/Problem 9|Next Problem]]
* [[1969 Canadian MO Problems|Back to Exam]]

Latest revision as of 21:42, 17 November 2007

Problem

Let $f$ be a function with the following properties:

1) $f(n)$ is defined for every positive integer $n$;

2) $f(n)$ is an integer;

3) $f(2)=2$;

4) $f(mn)=f(m)f(n)$ for all $m$ and $n$;

5) $f(m)>f(n)$ whenever $m>n$.

Prove that $f(n)=n$.

Solution

It's easily shown that $f(1)=1$ and $f(4)=4$. Since $f(2)<f(3)<f(4),$ $f(3) = 3.$

Now, assume that $f(2n+2)=f(2(n+1))=f(2)f(n+1)=2n+2$ is true for all $f(k)$ where $k\leq 2n.$

It follows that $2n<f(2n+1)<2n+2.$ Hence, $f(2n+1)=2n+1$, and by induction $f(n) = n$.

1969 Canadian MO (Problems)
Preceded by
Problem 7 		1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • Followed by
Problem 9


Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1969_Canadian_MO_Problems/Problem_8&oldid=19645"