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, ,
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
.