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

2012 USAMO Problems/Problem 4

Revision as of 14:12, 26 April 2012 by Pi37 (talk | contribs) (→‎Solution)

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

Note that $f(1)=f(1!)=f(1)!$ and $f(2)=f(2!)=f(2)!$, so $f(1)=1$ or $2$ and similarly for $f(2)$. We always have \[n\cdot n!=(n+1)!-n!|f(n+1)!-f(n)!\] (1)

Now if $f(n)=1$ for any $n\ge 2$, then $f(k)=1$ for all $k\ge n$. This follows because then $f(n+1)!\equiv 1 \mod n\cdot n!$, which is only possible if $f(n+1)=1$, and the rest 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|f(3)-f(1)\] so $2|-1$, a contradiction.

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

We claim $f(n)=n$ always by induction. The bases cases are already shown. If $f(k)=k$, then by (1) we have \[f(k+1)\equiv k! \mod k\cdot k!\] Which gives $f(k+1)<2k$ (otherwise $f(k+1)!\equiv 0 \mod k\cdot k!$). Also we have \[k+1-1|f(k+1)-f(1)\] so $f(k+1)\equiv 1 \mod k$. This gives the solutions $f(k+1)=1$ (obviously impossible) and $f(k+1)=k+1$. Then by induction, this always holds. Note that 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!\] Which gives $f(k+1)<2k$ similarly. Also note that \[k+1-1|f(k+1)-2\] \[k+1-2|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 this always holds, and note that this satisfies the requirements.

The solutions are $\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=46628"