Difference between revisions of "2012 USAMO Problems/Problem 4"
(→See also) |
(→Solution) |
||
Line 4: | Line 4: | ||
==Solution== | ==Solution== | ||
+ | Note that <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>. We always have | ||
+ | <cmath> | ||
+ | n\cdot n!=(n+1)!-n!|f(n+1)!-f(n)! | ||
+ | </cmath> | ||
+ | (1) | ||
+ | |||
+ | Now if <math>f(n)=1</math> for any <math>n\ge 2</math>, then <math>f(k)=1</math> for all <math>k\ge n</math>. This follows because then <math>f(n+1)!\equiv 1 \mod n\cdot n!</math>, which is only possible if <math>f(n+1)=1</math>, and the rest follows by induction. | ||
+ | We now divide into cases: | ||
+ | |||
+ | '''Case 1:''' <math>f(1)=f(2)=1</math> | ||
+ | |||
+ | This gives <math>f(n)=1</math> always from the previous claim, which is a solution. | ||
+ | |||
+ | '''Case 2:''' <math>f(1)=2, f(2)=1</math> | ||
+ | |||
+ | 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> | ||
+ | 3-1|f(3)-f(1) | ||
+ | </cmath> | ||
+ | so <math>2|-1</math>, a contradiction. | ||
+ | |||
+ | '''Case 3:''' <math>f(1)=1</math>, <math>f(2)=2</math> | ||
+ | |||
+ | We claim <math>f(n)=n</math> always by induction. The bases cases are already shown. If <math>f(k)=k</math>, then by (1) we have | ||
+ | <cmath> | ||
+ | f(k+1)\equiv k! \mod k\cdot k! | ||
+ | </cmath> | ||
+ | Which gives <math>f(k+1)<2k</math> (otherwise <math>f(k+1)!\equiv 0 \mod k\cdot k!</math>). Also we have | ||
+ | <cmath> | ||
+ | k+1-1|f(k+1)-f(1) | ||
+ | </cmath> | ||
+ | so <math>f(k+1)\equiv 1 \mod k</math>. This gives the solutions <math>f(k+1)=1</math> (obviously impossible) and <math>f(k+1)=k+1</math>. Then by induction, this always holds. Note that this also satisfies the requirements. | ||
+ | |||
+ | '''Case 4:''' <math>f(1)=f(2)=2</math> | ||
+ | |||
+ | We claim <math>f(n)=2</math> by a similar induction. Again if <math>f(k)=2</math>, then by (1) we have | ||
+ | <cmath> | ||
+ | f(k+1)\equiv 2 \mod k\cdot k! | ||
+ | </cmath> | ||
+ | Which gives <math>f(k+1)<2k</math> similarly. Also note that | ||
+ | <cmath> | ||
+ | k+1-1|f(k+1)-2 | ||
+ | </cmath> | ||
+ | <cmath> | ||
+ | k+1-2|f(k+1)-2 | ||
+ | </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 this always holds, and note that this satisfies the requirements. | ||
+ | |||
+ | The solutions are <math>\boxed{f(n)=1, f(n)=2, f(n)=n}</math>. | ||
==See also== | ==See also== |
Revision as of 14:12, 26 April 2012
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
Note that and , so or and similarly for . We always have (1)
Now if for any , then for all . This follows because then , which is only possible if , and the rest 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 so , a contradiction.
Case 3: ,
We claim always by induction. The bases cases are already shown. If , then by (1) we have Which gives (otherwise ). Also we have so . This gives the solutions (obviously impossible) and . Then by induction, this always holds. Note that this also satisfies the requirements.
Case 4:
We claim by a similar induction. Again if , then by (1) we have Which gives similarly. Also note that so . Then the only possible solution is . By induction this always holds, and note that this satisfies the requirements.
The solutions are .
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 |