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 "2012 USAMO Problems/Problem 4"

(→‎Solution)
(→‎Solution: cleaned up)
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
+
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!|f(n+1)!-f(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.
  
−
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:
 
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|f(3)-f(1)
+
3-1 \mid f(3)-f(1)
 
</cmath>
 
</cmath>
−
so <math>2|-1</math>, a contradiction.
+
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 bases cases are already shown. If <math>f(k)=k</math>, then by (1) we have
+
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>
−
Which gives <math>f(k+1)<2k</math> (otherwise <math>f(k+1)!\equiv 0 \mod k\cdot k!</math>). Also we have
+
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|f(k+1)-f(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) and <math>f(k+1)=k+1</math>. Then by induction, this always holds. Note that this also satisfies the requirements.
+
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>
−
Which gives <math>f(k+1)<2k</math> similarly. Also note that
+
and so <math>f(k+1)<2k</math>. Also note that
 
<cmath>
 
<cmath>
−
k+1-1|f(k+1)-2
+
k+1-1 \mid  f(k+1)-2
 
</cmath>
 
</cmath>
 +
and
 
<cmath>
 
<cmath>
−
k+1-2|f(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 this always holds, and note that this satisfies the requirements.
+
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.
 +
 
  
−
The solutions are <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>.
  
 
==See also==
 
==See also==

Revision as of 11:10, 21 June 2012

Problem

Find all functions $f : \mathbb{Z}^+ \to \mathbb{Z}^+$ (where $\mathbb{Z}^+$ is the set of positive integers) such that $f(n!) = f(n)!$ for all positive integers $n$ and such that $m - n$ divides $f(m) - f(n)$ for all distinct positive integers $m$, $n$.

Solution

By the first condition we have $f(1)=f(1!)=f(1)!$ and $f(2)=f(2!)=f(2)!$, so $f(1)=1$ or $2$ and similarly for $f(2)$. By the second condition, we have \[n\cdot n!=(n+1)!-n! \mid f(n+1)!-f(n)! \qquad \qquad (1)\] for all positive integers $n$.

Suppose that for some $n \geq 2$ we have $f(n) = 1$. We claim that $f(k)=1$ for all $k\ge n$. Indeed, from Equation (1) we have $f(n+1)!\equiv 1 \mod n\cdot n!$, and this is only possible if $f(n+1)=1$; the claim follows by induction.

We now divide into cases:

Case 1: $f(1)=f(2)=1$

This gives $f(n)=1$ always from the previous claim, which is a solution.

Case 2: $f(1)=2, f(2)=1$

This implies $f(n)=1$ for all $n\ge 2$, but this does not satisfy the initial conditions. Indeed, we would have \[3-1 \mid f(3)-f(1)\] and so $2\mid -1$, a contradiction.

Case 3: $f(1)=1$, $f(2)=2$

We claim $f(n)=n$ always by induction. The base cases are $n = 1$ and $n = 2$. Fix $k > 1$ and suppose that $f(k)=k$. By Equation (1) we have that \[f(k+1)! \equiv k! \mod k\cdot k! .\] This implies $f(k+1)<2k$ (otherwise $f(k+1)!\equiv 0 \mod k\cdot k!$). Also we have \[(k+1)-1 \mid f(k+1)-f(1)\] so $f(k+1)\equiv 1 \mod k$. This gives the solutions $f(k+1)=1$ and $f(k+1)=k+1$. The first case is obviously impossible, so $f(k + 1) = k + 1$, as desired. By induction, $f(n) = n$ for all $n$. This also satisfies the requirements.

Case 4: $f(1)=f(2)=2$

We claim $f(n)=2$ by a similar induction. Again if $f(k)=2$, then by (1) we have \[f(k+1)\equiv 2 \mod k\cdot k!\] and so $f(k+1)<2k$. Also note that \[k+1-1 \mid f(k+1)-2\] and \[k+1-2 \mid f(k+1)-2\] so $f(k+1)\equiv 2 \mod k(k-1)$. Then the only possible solution is $f(k+1)=2$. By induction, $f(n) = 2$ for all $n$, and this satisfies all requirements.


In summary, there are three solutions: $\boxed{f(n)=1, f(n)=2, f(n)=n}$.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2012_USAMO_Problems/Problem_4&oldid=47440"