Difference between revisions of "1991 AIME Problems/Problem 3"
Gabiloncho (talk | contribs) (→Solution) |
m |
||
(27 intermediate revisions by 9 users not shown) | |||
Line 7: | Line 7: | ||
== Solution == | == Solution == | ||
− | Let <math>0<x_{}^{}<1</math>. Then we may write <math>A_{k}^{}=\frac{N!}{k!(N-k)!}x^{k}=\frac{(N-k+1)!}{k!}x^{k}</math>. Taking logarithms in both sides of this last equation | + | === Solution 1 === |
+ | Let <math>0<x_{}^{}<1</math>. Then we may write <math>A_{k}^{}={N\choose k}x^{k}=\frac{N!}{k!(N-k)!}x^{k}=\frac{(N-k+1)!}{k!}x^{k}</math>. Taking logarithms in both sides of this last equation and using the well-known fact <math>\log(a_{}^{}b)=\log a + \log b</math> (valid if <math>a_{}^{},b_{}^{}>0</math>), we have | ||
<math> | <math> | ||
− | \log(A_{k})=\log\left[\frac{(N-k+1)!}{k!}x^{k}\right]=\sum_{j=1}^{k}\log\left[\frac{(N-j+1)x}{j}\right]\, . | + | \log(A_{k})=\log\left[\frac{(N-k+1)!}{k!}x^{k}\right]=\log\left[\prod_{j=1}^{k}\frac{(N-j+1)x}{j}\right]=\sum_{j=1}^{k}\log\left[\frac{(N-j+1)x}{j}\right]\, . |
</math> | </math> | ||
− | Now, <math>\log(A_{k}^{})</math> keeps increasing with <math>k_{}^{}</math> as long as the arguments <math>\frac{(N-j+1)x}{j}>1</math> in each of the terms (recall that <math>\log y_{}^{} <0</math> if <math>0<y_{}^{}<1</math>). Therefore, the <math>k_{}^{}</math> that we are looking for must satisfy <math>\frac{(N-k+1) | + | Now, <math>\log(A_{k}^{})</math> keeps increasing with <math>k_{}^{}</math> as long as the arguments <math>\frac{(N-j+1)x}{j}>1</math> in each of the <math>\log\big[\;\big]</math> terms (recall that <math>\log y_{}^{} <0</math> if <math>0<y_{}^{}<1</math>). Therefore, the integer <math>k_{}^{}</math> that we are looking for must satisfy <math>k=\Big\lfloor\frac{(N+1)x}{1+x}\Big\rfloor</math>, where <math>\lfloor z_{}^{}\rfloor</math> denotes the greatest integer less than or equal to <math>z_{}^{}</math>. |
+ | |||
+ | In summary, substituting <math>N_{}^{}=1000</math> and <math>x_{}^{}=0.2</math> we finally find that <math>k=\boxed{166}</math>. | ||
+ | |||
+ | ===Solution 2=== | ||
+ | |||
+ | We know that once we have found the largest value of <math>k</math>, all values after <math>A_k</math> are less than <math>A_k</math>. Therefore, we are looking for the smallest possible value such that: | ||
+ | |||
+ | <math>{\frac{1}{5}}^k\cdot {{1000} \choose {k}}>{\frac{1}{5}}^{k+1}\cdot {{1000} \choose {k+1}}</math> | ||
+ | |||
+ | Dividing by <math>{\frac{1}{5}}^k</math> gives: | ||
+ | |||
+ | <math>{1000\choose k}>{\frac{1}{5}}\cdot{1000\choose {k+1}}</math>. | ||
+ | |||
+ | We can express these binomial coefficients as factorials. | ||
+ | |||
+ | <math>\frac{1000!}{(1000-k)!\cdot(k)!}>{\frac{1}{5}}\cdot\frac{1000!}{(1000-k-1)!\cdot{(k+1)!}}</math> | ||
+ | |||
+ | We note that the <math>1000!</math> can cancel. Also, <math>(1000-k)!=(1000-k)(1000-k-1)!</math>. Similarly, <math>(k+1)!=(k+1)k!</math>. | ||
+ | |||
+ | Canceling these terms yields, | ||
+ | |||
+ | <math>\frac{1}{(1000-k)}>{\frac{1}{5}}\cdot\frac{1}{(k+1)}</math> | ||
+ | |||
+ | Cross multiplying gives: | ||
+ | |||
+ | <math>5k+5>1000-k \Rightarrow k>165.8</math> | ||
+ | |||
+ | Therefore, since this identity holds for all values of <math>k>165.8</math>, the largest possible value of <math>k</math> is <math>\boxed{166}</math>. | ||
+ | |||
+ | ===Solution 3=== | ||
+ | |||
+ | We know that <math>A_k</math> will increase as <math>k</math> increases until certain <math>k=m</math>, where <math> A_0 < A_1 < A_2 < \dots < A_{m-2} < A_{m-1} < A_m </math> and | ||
+ | |||
+ | <math>A_m > A_{m+1} > A_{m+2} > \dots > A_{1000}.</math> | ||
+ | |||
+ | Next, to change <math> A_{k-1} </math> to <math> A_k </math>, we multiply <math> A_{k-1} </math> by <math>\frac{1000-k+1}{5k}</math>. It follows that the numerator must be greater than the | ||
+ | |||
+ | denominator or | ||
+ | |||
+ | <cmath>1000-k+1>5k</cmath> | ||
+ | <cmath>k<166.8</cmath>. | ||
+ | |||
+ | We conclude that the answer is <math>\boxed{166}</math>. | ||
+ | |||
+ | ==Solution 4== | ||
+ | |||
+ | Notice that the expansion is the largest the moment BEFORE the <math>nC_p < 5</math> (this reasoning can probably be found in the other solutions; basically, if we have a number k and then k+1, the value is the largest when k+1 is larger than k, or in other words <math>nC_p*\frac{1}{5} > 1</math>) | ||
+ | |||
+ | Say we have <math>{1000 \choose 5}</math>... this equals <math>\frac{1000*999*998*997*996}{5*4*3*2*1}</math>, and if we have k+1, then it's just going to be equivalent to multiplying this fraction by <math>\frac{995}{6}</math>. Notice that this fraction's numerator plus denominator is equal to <math>1001</math>. Calling the numerator x and the denominator y, we get that | ||
+ | <cmath>x+y = 1001</cmath> <cmath>\frac{x}{y} > 5</cmath> <cmath>x>5y</cmath> <cmath>6y<1001</cmath> <cmath>y<166.83333</cmath> and since the denominator is what we are specifically choosing, or in other words what k is, we conclude k = <math>\boxed{166}</math> | ||
+ | |||
+ | Note: It may be more intuitive to equate <math>x=5y</math> and then use test points to figure out which side of the inequality to lie on. | ||
+ | |||
+ | ==Solution 5== | ||
+ | |||
+ | Notice the relation between <math>A_m</math> and <math>A_{m+1}</math>. We have that: <math>A_{m+1} = A_m \cdot \frac{1}{5} \cdot \frac{1000-m}{m+1}</math>. This is true because from <math>A_m</math> to <math>A_{m+1}</math> we have to multiply by <math>\frac{1}{5}=0.2</math> once,and then we must resolve the factorial issue. To do this, we must realize that | ||
+ | |||
+ | <cmath> {1000 \choose m+1} = \frac{1000!}{(m+1)!(1000-m-1)!} = \frac{1000 \cdots (1001-m)(1000-m)}{(m+1)!}</cmath> | ||
+ | and that | ||
+ | <cmath> {1000 \choose m} = \frac{1000!}{m!(1000-m)!} = \frac{1000 \cdots (1001-m)}{m!}</cmath> | ||
+ | |||
+ | <cmath>\Longrightarrow {1000 \choose m} \cdot \frac{1000-m}{m+1}</cmath> | ||
+ | |||
+ | So now, we must find out for which <math>m</math> is <math>1000-m< 5 \cdot (m+1)</math> (when this happens the numerator is less than the denominator for the fraction <math>\frac{1000-m}{m+1}</math> so then we will have <math>A_m > A_{m+1}</math>) Then we find that for all <math>m > 165.833333</math>, the above inequality (<math>1000-m< 5 \cdot (m+1)</math>) holds, so then <math>m=165</math> so <math>k=m+1= \boxed{166}</math>. | ||
+ | |||
+ | ~qwertysri987 | ||
== See also == | == See also == | ||
{{AIME box|year=1991|num-b=2|num-a=4}} | {{AIME box|year=1991|num-b=2|num-a=4}} | ||
+ | {{MAA Notice}} |
Latest revision as of 11:13, 21 May 2020
Contents
[hide]Problem
Expanding by the binomial theorem and doing no further manipulation gives
where for . For which is the largest?
Solution
Solution 1
Let . Then we may write . Taking logarithms in both sides of this last equation and using the well-known fact (valid if ), we have
Now, keeps increasing with as long as the arguments in each of the terms (recall that if ). Therefore, the integer that we are looking for must satisfy , where denotes the greatest integer less than or equal to .
In summary, substituting and we finally find that .
Solution 2
We know that once we have found the largest value of , all values after are less than . Therefore, we are looking for the smallest possible value such that:
Dividing by gives:
.
We can express these binomial coefficients as factorials.
We note that the can cancel. Also, . Similarly, .
Canceling these terms yields,
Cross multiplying gives:
Therefore, since this identity holds for all values of , the largest possible value of is .
Solution 3
We know that will increase as increases until certain , where and
Next, to change to , we multiply by . It follows that the numerator must be greater than the
denominator or
.
We conclude that the answer is .
Solution 4
Notice that the expansion is the largest the moment BEFORE the (this reasoning can probably be found in the other solutions; basically, if we have a number k and then k+1, the value is the largest when k+1 is larger than k, or in other words )
Say we have ... this equals , and if we have k+1, then it's just going to be equivalent to multiplying this fraction by . Notice that this fraction's numerator plus denominator is equal to . Calling the numerator x and the denominator y, we get that and since the denominator is what we are specifically choosing, or in other words what k is, we conclude k =
Note: It may be more intuitive to equate and then use test points to figure out which side of the inequality to lie on.
Solution 5
Notice the relation between and . We have that: . This is true because from to we have to multiply by once,and then we must resolve the factorial issue. To do this, we must realize that
and that
So now, we must find out for which is (when this happens the numerator is less than the denominator for the fraction so then we will have ) Then we find that for all , the above inequality () holds, so then so .
~qwertysri987
See also
1991 AIME (Problems • Answer Key • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.