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. ...") |
|||
| Line 1: | Line 1: | ||
| + | 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, <math>f(1)</math>, <math>f(2)</math> equal to <math>1</math> or <math>2</math>. | ||
| + | |||
| + | 2. Second, suppose that for all <math>n</math>, <math>f(n)\le 2</math>. Then for <math>n\ge 3</math>, | ||
| + | |||
| + | <math> 2\ge f(n!) = f(1) + C(n!-1) </math> (<math>C\ge 0</math> is an integer.) | ||
| + | <math>\ge -2+5C</math>, therefore <math>5C\le 4</math> and so <math>C=0</math> is the only possibility. Hence <math>f(n)!=f(n!)=f(1)</math>. Similar argument yields that <math>f(n)!=f(n!)=f(2)</math>, so <math>f</math> is a constant function, which can only be <math>f=1</math> or <math>f=2</math>. | ||
| + | |||
| + | 3. From now on, suppose that there exists <math>n_0\ge 3</math> such that <math>f(n_0)>2</math>. | ||
| + | |||
| + | 4. By <math>2| (n_0!-2) | f(n_0)!-f(2)</math> and that <math>2|f(n_0)!</math> we know that <math>2|f(2)</math>, or <math>f(2)=2</math>. | ||
| + | |||
| + | 5. By <math>f(3)!=f(6)=4C+f(2)=4C+2</math> we know that <math>f(3)\le 3</math>, and by <math>3|f(n_0)!-f(3)</math> and <math>3|f(n_0)!</math> we know that <math>3|f(3)</math>, therefore <math>f(3)=3</math>. | ||
| + | |||
| + | 6. Then by <math>2|f(3)-f(1)</math> we know that <math>f(1)</math> is odd, so <math>f(1)=1</math>. | ||
| + | |||
| + | 7. For <math>n\ge 3</math>, <math>f(n)=C_1(n-1)+1=C_2(n-2)+2</math> implies that <math>f(n)>2</math>, otherwise <math>C_1=C_2=0</math> and that <math>f(n)=1=2</math>, which is a contradiction. Since <math>f(n)>2</math>, now we have <math>C_2\ge 1</math>, so <math>f(n)\ge (n-2)+2=n</math>. Now we have a lower bound. What is more difficult is to find an upper bound of <math>f(n)</math>. (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 <math>n|f(n)!</math>. Now <math>f( (n+1)!) = f(n!) + C( n \cdot n!)</math>, therefore if <math>f(n)=n</math>, then suppose <math>f(n+1)=D(n+1)</math>, then we have | ||
| + | <math></math> (D(n+1))! = n! + Cn\cdot n!, which is not divisible by <math>n\cdot n!</math> and so <math>D=1</math>. By induction we have <math>f(n)=n</math> for all <math>n\ge 3</math>. | ||
| + | |||
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. | 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. | ||
Revision as of 21: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 .
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 .
