Talk:2012 USAMO Problems/Problem 4

Though not as elegant as the inductive proof, my proof for this problem is quite different from the one posted in the Page, so I would like to paste it here just for reference.

1. First, $f(1)$ , $f(2)$ equal to $1$ or $2$ .

2. Second, suppose that for all $n$ , $f(n)\le 2$ . Then for $n\ge 3$ ,

$2\ge f(n!) = f(1) + C(n!-1)\ge -2+5C$

, where $C\ge 0$ is an integer. We have $5C\le 4$ and so $C=0$ is the only possibility.

Hence $f(n)!=f(n!)=f(1)$ . Similar argument yields that $f(n)!=f(n!)=f(2)$ , so $f$ is a constant function, which can only be $f=1$ or $f=2$ .

3. From now on, suppose that there exists $n_0\ge 3$ such that $f(n_0)>2$ .

4. By $2| (n_0!-2) | f(n_0)!-f(2)$ and that $2|f(n_0)!$ we know that $2|f(2)$ , or $f(2)=2$ .

5. By $f(3)!=f(6)=4C+f(2)=4C+2$ we know that $f(3)\le 3$ , and by $3|f(n_0)!-f(3)$ and $3|f(n_0)!$ we know that $3|f(3)$ , therefore $f(3)=3$ .

6. Then by $2|f(3)-f(1)$ we know that $f(1)$ is odd, so $f(1)=1$ .

7. For $n\ge 3$ , $f(n)=C_1(n-1)+1=C_2(n-2)+2$ implies that $f(n)>2$ , otherwise $C_1=C_2=0$ and that $f(n)=1=2$ , which is a contradiction. Since $f(n)>2$ , now we have $C_2\ge 1$ , so $f(n)\ge (n-2)+2=n$ . Now we have a lower bound. What is more difficult is to find an upper bound of $f(n)$ .

(I know from the main Page it is not too hard to get the upper bound, but to be honest it takes me quite a while to figure it out.)

8. Therefore $n|f(n)!$ . Now $f( (n+1)!) = f(n!) + C n \cdot n!$ , therefore if $f(n)=n$ , then let $f(n+1)=D(n+1)$ and we have $(D(n+1))! = n! + Cn \cdot n!$

, where the right hand side should not be divisible by $n\cdot n!$ and so $D=1$ . By induction we have $f(n)=n$ for all $n\ge 3$ .

--Lightest 22:26, 3 May 2012 (EDT)

Page

Toolbox

Search

Talk:2012 USAMO Problems/Problem 4