Difference between revisions of "2012 USAMO Problems/Problem 4"

Latest revision as of 07:18, 19 July 2016

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}$ .

Summary

Three functions: $f(x)=x$ since $x!=x!$ , $1!=1$ and $2!=2$ , fixed points on the $x!$ function.

No elegant $\mod$ argument needed; $f(m)-f(n)\textcolor{red}{\textbf{ = }}m-n$ so of course $m-n\mid f(m)-f(n)$ !

@@ Line 1: / Line 1: @@
 == Problem ==
-Give 370 proofs of the Pythagorean theorem.
+Find all functions <math>f : \mathbb{Z}^+ \to \mathbb{Z}^+</math> (where <math>\mathbb{Z}^+</math> is the set of positive integers) such that <math>f(n!) = f(n)!</math> for all positive integers <math>n</math> and such that <math>m - n</math> divides <math>f(m) - f(n)</math> for all distinct positive integers <math>m</math>, <math>n</math>.
+==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>
+n\cdot n!=(n+1)!-n! \mid f(n+1)!-f(n)! \qquad \qquad (1)
+</cmath>
+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:
+'''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>
+-1 \mid f(3)-f(1)
+</cmath>
+and so <math>2\mid -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 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>
+f(k+1)! \equiv k! \mod k\cdot k! .
+</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>
+(k+1)-1  \mid  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> 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>
+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>
+and so <math>f(k+1)<2k</math>.  Also note that
+<cmath>
+k+1-1  \mid  f(k+1)-2
+</cmath>
+and
+<cmath>
+k+1-2  \mid  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, <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}}
+{{MAA Notice}}
+[[Category:Olympiad Algebra Problems]]
+[[Category:Functional Equation Problems]]

2012 USAMO (Problems • Resources)
Preceded by Problem 3	Followed by Problem 5
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search

Difference between revisions of "2012 USAMO Problems/Problem 4"

Latest revision as of 07:18, 19 July 2016

Contents

Problem

Solution

Summary

See Also