Difference between revisions of "2012 USAMO Problems/Problem 4"
(→Solution) |
m (→See also) |
||
(7 intermediate revisions by 4 users not shown) | |||
Line 4: | Line 4: | ||
==Solution== | ==Solution== | ||
− | + | By the first condition we have <math>f(1)=f(1!)=f(1)!</math> and <math>f(2)=f(2!)=f(2)!</math>, so <math>f(1)=1</math> or <math>2</math> and similarly for <math>f(2)</math>. By the second condition, we have | |
<cmath> | <cmath> | ||
− | n\cdot n!=(n+1)!-n! | + | n\cdot n!=(n+1)!-n! \mid f(n+1)!-f(n)! \qquad \qquad (1) |
</cmath> | </cmath> | ||
− | (1) | + | for all positive integers <math>n</math>. |
+ | |||
+ | Suppose that for some <math>n \geq 2</math> we have <math>f(n) = 1</math>. We claim that <math>f(k)=1</math> for all <math>k\ge n</math>. Indeed, from Equation (1) we have <math>f(n+1)!\equiv 1 \mod n\cdot n!</math>, and this is only possible if <math>f(n+1)=1</math>; the claim follows by induction. | ||
− | |||
We now divide into cases: | We now divide into cases: | ||
Line 21: | Line 22: | ||
This implies <math>f(n)=1</math> for all <math>n\ge 2</math>, but this does not satisfy the initial conditions. Indeed, we would have | This implies <math>f(n)=1</math> for all <math>n\ge 2</math>, but this does not satisfy the initial conditions. Indeed, we would have | ||
<cmath> | <cmath> | ||
− | 3-1 | + | 3-1 \mid f(3)-f(1) |
</cmath> | </cmath> | ||
− | so <math>2 | + | and so <math>2\mid -1</math>, a contradiction. |
'''Case 3:''' <math>f(1)=1</math>, <math>f(2)=2</math> | '''Case 3:''' <math>f(1)=1</math>, <math>f(2)=2</math> | ||
− | We claim <math>f(n)=n</math> always by induction. The | + | We claim <math>f(n)=n</math> always by induction. The base cases are <math>n = 1</math> and <math>n = 2</math>. Fix <math>k > 1</math> and suppose that <math>f(k)=k</math>. By Equation (1) we have that |
<cmath> | <cmath> | ||
− | f(k+1)\equiv k! \mod k\cdot k! | + | f(k+1)! \equiv k! \mod k\cdot k! . |
</cmath> | </cmath> | ||
− | + | This implies <math>f(k+1)<2k</math> (otherwise <math>f(k+1)!\equiv 0 \mod k\cdot k!</math>). Also we have | |
<cmath> | <cmath> | ||
− | k+1-1 | + | (k+1)-1 \mid f(k+1)-f(1) |
</cmath> | </cmath> | ||
− | so <math>f(k+1)\equiv 1 \mod k</math>. This gives the solutions <math>f(k+1)=1</math> (obviously impossible | + | so <math>f(k+1)\equiv 1 \mod k</math>. This gives the solutions <math>f(k+1)=1</math> and <math>f(k+1)=k+1</math>. The first case is obviously impossible, so <math>f(k + 1) = k + 1</math>, as desired. By induction, <math>f(n) = n</math> for all <math>n</math>. This also satisfies the requirements. |
'''Case 4:''' <math>f(1)=f(2)=2</math> | '''Case 4:''' <math>f(1)=f(2)=2</math> | ||
Line 43: | Line 44: | ||
f(k+1)\equiv 2 \mod k\cdot k! | f(k+1)\equiv 2 \mod k\cdot k! | ||
</cmath> | </cmath> | ||
− | + | and so <math>f(k+1)<2k</math>. Also note that | |
<cmath> | <cmath> | ||
− | k+1-1 | + | k+1-1 \mid f(k+1)-2 |
</cmath> | </cmath> | ||
+ | and | ||
<cmath> | <cmath> | ||
− | k+1-2 | + | k+1-2 \mid f(k+1)-2 |
</cmath> | </cmath> | ||
− | so <math>f(k+1)\equiv 2 \mod k(k-1)</math>. Then the only possible solution is <math>f(k+1)=2</math>. By induction | + | so <math>f(k+1)\equiv 2 \mod k(k-1)</math>. Then the only possible solution is <math>f(k+1)=2</math>. By induction, <math>f(n) = 2</math> for all <math>n</math>, and this satisfies all requirements. |
+ | |||
+ | |||
+ | 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.