Difference between revisions of "Talk:2012 USAMO Problems/Problem 4"
(2 intermediate revisions by the same user not shown) | |||
Line 5: | Line 5: | ||
2. Second, suppose that for all <math>n</math>, <math>f(n)\le 2</math>. Then for <math>n\ge 3</math>, | 2. Second, suppose that for all <math>n</math>, <math>f(n)\le 2</math>. Then for <math>n\ge 3</math>, | ||
− | < | + | <cmath> 2\ge f(n!) = f(1) + C(n!-1)\ge -2+5C</cmath> |
− | + | ||
+ | , where <math>C\ge 0</math> is an integer. We have <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>. | 3. From now on, suppose that there exists <math>n_0\ge 3</math> such that <math>f(n_0)>2</math>. |
Latest revision as of 22:29, 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
,
, where is an integer. We have
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 quite a while to figure it out.)
8. Therefore . Now
, therefore if
, then let
and we have
, where the right hand side should not be divisible by and so
. By induction we have
for all
.
--Lightest 22:26, 3 May 2012 (EDT)