Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Talk:2012 USAMO Problems/Problem 4"
 
(7 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>,  
  
−
<math> 2\ge f(n!)  = f(1) + C(n!-1) </math>  (<math>C\ge 0</math> is an integer.)
+
<cmath> 2\ge f(n!)  = f(1) + C(n!-1)\ge -2+5C</cmath>
−
<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>.
+
 
 +
, 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>.
Line 16: Line 20:
 
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>.
 
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.)
+
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>.  
−
 
 
−
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.
+
'''(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.)'''
  
−
1. First, <math>f(1)</math>, <math>f(2)</math> equal to <math>1</math> or <math>2</math>.
+
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 let <math>f(n+1)=D(n+1)</math> and we have
−
 
+
<cmath> (D(n+1))! = n! + Cn \cdot n!</cmath>
−
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.)
+
, where the right hand side should not be 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>.
  
−
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
+
--[[User:Lightest|Lightest]] 22:26, 3 May 2012 (EDT)
−
<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>.
 

Latest revision as of 21: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, $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)

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Talk:2012_USAMO_Problems/Problem_4&oldid=46818"