2000 AIME II Problems/Problem 7: Difference between revisions
\ |
|||
| (15 intermediate revisions by 10 users not shown) | |||
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
Given that <center><math>\frac 1{2!17!}+\frac 1{3!16!}+\frac 1{4!15!}+\frac 1{5!14!}+\frac 1{6!13!}+\frac 1{7!12!}+\frac 1{8!11!}+\frac 1{9!10!}=\frac N{1!18!}</math></center> find the [[floor function|greatest integer]] that is less than <math>\frac N{100}</math>. | |||
== Solution == | == Solution == | ||
Multiplying both sides by <math>19!</math> yields: | |||
<cmath>\frac {19!}{2!17!}+\frac {19!}{3!16!}+\frac {19!}{4!15!}+\frac {19!}{5!14!}+\frac {19!}{6!13!}+\frac {19!}{7!12!}+\frac {19!}{8!11!}+\frac {19!}{9!10!}=\frac {19!N}{1!18!}.</cmath> | |||
<cmath>\binom{19}{2}+\binom{19}{3}+\binom{19}{4}+\binom{19}{5}+\binom{19}{6}+\binom{19}{7}+\binom{19}{8}+\binom{19}{9} = 19N.</cmath> | |||
Recall the [[combinatorial identity|Combinatorial Identity]] <math>2^{19} = \sum_{n=0}^{19} {19 \choose n}</math>. Since <math>{19 \choose n} = {19 \choose 19-n}</math>, it follows that <math>\sum_{n=0}^{9} {19 \choose n} = \frac{2^{19}}{2} = 2^{18}</math>. | |||
Thus, <math>19N = 2^{18}-\binom{19}{1}-\binom{19}{0}=2^{18}-19-1 = (2^9)^2-20 = (512)^2-20 = 262124</math>. | |||
So, <math>N=\frac{262124}{19}=13796</math> and <math>\left\lfloor \frac{N}{100} \right\rfloor =\boxed{137}</math>. | |||
== Solution 2 == | |||
Let <math>f(x) = (1+x)^{19}.</math> Applying the binomial theorem gives us <math>f(x) = \binom{19}{19} x^{19} + \binom{19}{18} x^{18} + \binom{19}{17} x^{17}+ \cdots + \binom{19}{0}.</math> Since <math>\frac 1{2!17!}+\frac 1{3!16!}+\dots+\frac 1{8!11!}+\frac 1{9!10!} = \frac{\frac{f(1)}{2} - \binom{19}{19} - \binom{19}{18}}{19!},</math> <math>N = \frac{2^{18}-20}{19}.</math> After some fairly easy bashing, we get <math>\boxed{137}</math> as the answer. | |||
~peelybonehead | |||
==Solution 3 (Brute Force)== | |||
Convert each denominator to <math>19!</math> and get the numerators to be <math>9,51,204,612,1428,2652,3978,4862</math> (refer to note). Adding these up we have <math>13796</math> therefore <math>\boxed{137}</math> is the desired answer. | |||
Note: | |||
Notice that each numerator is increased each time by a factor of <math>\frac{17}{3}, \frac{16}{4}, \frac{15}{5}, \frac{14}{6},</math> etc. until <math>\frac{11}{9}</math>. If you were taking the test under normal time conditions, it shouldn't be too hard to bash out all of the numbers but it is priority to be careful. | |||
~SirAppel | |||
== See also == | == See also == | ||
{{AIME box|year=2000|n=II|num-b=6|num-a=8}} | |||
[[Category:Intermediate Combinatorics Problems]] | |||
{{MAA Notice}} | |||
Latest revision as of 11:09, 5 April 2024
Problem
Given that
find the greatest integer that is less than 
.
Solution
Multiplying both sides by 
yields:
![\[\frac {19!}{2!17!}+\frac {19!}{3!16!}+\frac {19!}{4!15!}+\frac {19!}{5!14!}+\frac {19!}{6!13!}+\frac {19!}{7!12!}+\frac {19!}{8!11!}+\frac {19!}{9!10!}=\frac {19!N}{1!18!}.\]](http://latex.artofproblemsolving.com/5/1/2/512c6a00ae7e316e65fee4284136007504350d26.png)
![\[\binom{19}{2}+\binom{19}{3}+\binom{19}{4}+\binom{19}{5}+\binom{19}{6}+\binom{19}{7}+\binom{19}{8}+\binom{19}{9} = 19N.\]](http://latex.artofproblemsolving.com/e/3/e/e3e8008bba65f49823f5d64af9b96e7d8ec7dedc.png)
Recall the Combinatorial Identity 
. Since 
, it follows that 
.
Thus, 
.
So, 
and 
.
Solution 2
Let 
Applying the binomial theorem gives us 
Since 
After some fairly easy bashing, we get 
as the answer.
~peelybonehead
Solution 3 (Brute Force)
Convert each denominator to and get the numerators to be 
(refer to note). Adding these up we have 
therefore is the desired answer.
Note:
Notice that each numerator is increased each time by a factor of 
etc. until 
. If you were taking the test under normal time conditions, it shouldn't be too hard to bash out all of the numbers but it is priority to be careful.
~SirAppel
See also
| 2000 AIME II (Problems • Answer Key • Resources) | ||
| Preceded by Problem 6 |
Followed by Problem 8 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
| All AIME Problems and Solutions | ||
These problems are copyrighted © by the Mathematical Association of America. 
