Difference between revisions of "Talk:2012 USAMO Problems/Problem 4"
(Created page with "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. ...") |
(No difference)
|
Revision as of 22:25, 3 May 2012
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, , equal to or .
2. Second, suppose that for all , . Then for ,
( is an integer.) , therefore and so is the only possibility. Hence . Similar argument yields that , so is a constant function, which can only be or .
3. From now on, suppose that there exists such that .
4. By and that we know that , or .
5. By we know that , and by and we know that , therefore .
6. Then by we know that is odd, so .
7. For , implies that , otherwise and that , which is a contradiction. Since , now we have , so . Now we have a lower bound. What is more difficult is to find an upper bound of . (I know from the main Page it is not too hard to get the upper bound, but to be honest it takes me a while to figure it out.)
8. Therefore . Now , therefore if , then suppose , then we have $$ (Error compiling LaTeX. Unknown error_msg) (D(n+1))! = n! + Cn\cdot n!, which is not divisible by and so . By induction we have for all .