Difference between revisions of "2012 USAMO Problems/Problem 4"
(→Solution: cleaned up) |
m (→See also) |
||
(6 intermediate revisions by 3 users not shown) | |||
Line 57: | Line 57: | ||
In summary, there are three solutions: <math>\boxed{f(n)=1, f(n)=2, f(n)=n}</math>. | In summary, there are three solutions: <math>\boxed{f(n)=1, f(n)=2, f(n)=n}</math>. | ||
− | == | + | ==Summary== |
− | + | Three functions: <math>f(x)=x</math> since <math>x!=x!</math>, <math>1!=1</math> and <math>2!=2</math>, fixed points on the <math>x!</math> function. | |
+ | No elegant<math>\mod</math> argument needed; <math>f(m)-f(n)\textcolor{red}{\textbf{ = }}m-n</math> so of course <math>m-n\mid f(m)-f(n)</math>! | ||
+ | |||
+ | ==See Also== | ||
{{USAMO newbox|year=2012|num-b=3|num-a=5}} | {{USAMO newbox|year=2012|num-b=3|num-a=5}} | ||
+ | {{MAA Notice}} | ||
+ | [[Category:Olympiad Algebra Problems]] | ||
+ | [[Category:Functional Equation Problems]] |
Latest revision as of 08:18, 19 July 2016
Contents
Problem
Find all functions (where is the set of positive integers) such that for all positive integers and such that divides for all distinct positive integers , .
Solution
By the first condition we have and , so or and similarly for . By the second condition, we have for all positive integers .
Suppose that for some we have . We claim that for all . Indeed, from Equation (1) we have , and this is only possible if ; the claim follows by induction.
We now divide into cases:
Case 1:
This gives always from the previous claim, which is a solution.
Case 2:
This implies for all , but this does not satisfy the initial conditions. Indeed, we would have and so , a contradiction.
Case 3: ,
We claim always by induction. The base cases are and . Fix and suppose that . By Equation (1) we have that This implies (otherwise ). Also we have so . This gives the solutions and . The first case is obviously impossible, so , as desired. By induction, for all . This also satisfies the requirements.
Case 4:
We claim by a similar induction. Again if , then by (1) we have and so . Also note that and so . Then the only possible solution is . By induction, for all , and this satisfies all requirements.
In summary, there are three solutions: .
Summary
Three functions: since , and , fixed points on the function.
No elegant argument needed; so of course !
See Also
2012 USAMO (Problems • Resources) | ||
Preceded by Problem 3 |
Followed by Problem 5 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.