Difference between revisions of "2006 AIME II Problems/Problem 3"
m |
|||
| Line 1: | Line 1: | ||
| − | # | + | == Problem == |
| + | Let <math>P </math> be the product of the first <math>100</math> [[positive integer | positive]] [[odd integer]]s. Find the largest integer <math>k </math> such that <math>P </math> is divisible by <math>3^k .</math> | ||
| + | |||
| + | == Solution == | ||
| + | |||
| + | Note that the product of the first <math>100</math> positive odd integers can be written as <math>1\cdot 3\cdot 5\cdot 7\cdots 195\cdot 197\cdot 199=\frac{1\cdot 2\cdots200}{2\cdot4\cdots200} = \frac{200!}{2^{100}\cdot 100!}</math> | ||
| + | |||
| + | Hence, we seek the number of threes in <math>200!</math> decreased by the number of threes in <math>100!.</math> | ||
| + | |||
| + | There are | ||
| + | |||
| + | <math>\left\lfloor \frac{200}{3}\right\rfloor+\left\lfloor\frac{200}{9}\right\rfloor+\left\lfloor \frac{200}{27}\right\rfloor+\left\lfloor\frac{200}{81}\right\rfloor =66+22+7+2=97</math> | ||
| + | |||
| + | threes in <math>200!</math> and | ||
| + | |||
| + | <math>\left\lfloor \frac{100}{3}\right\rfloor+\left\lfloor\frac{100}{9}\right\rfloor+\left\lfloor \frac{100}{27}\right\rfloor+\left\lfloor\frac{100}{81}\right\rfloor=33+11+3+1=48 </math> | ||
| + | |||
| + | threes in <math>100!</math> | ||
| + | |||
| + | Therefore, we have a total of <math>97-48=049</math> threes. | ||
| + | |||
| + | For more information, see also [[Factorial#Prime factorization| prime factorizations of a factorial]]. | ||
| + | |||
| + | == See also == | ||
| + | * [[Number Theory]] | ||
| + | {{AIME box|year=2006|n=I|num-b=2|num-a=4}} | ||
| + | |||
| + | [[Category:Intermediate Number Theory Problems]] | ||
Revision as of 18:58, 25 September 2007
Problem
Let 
be the product of the first 
positive odd integers. Find the largest integer 
such that is divisible by 
Solution
Note that the product of the first positive odd integers can be written as 
Hence, we seek the number of threes in 
decreased by the number of threes in 
There are
threes in and
threes in 
Therefore, we have a total of 
threes.
For more information, see also prime factorizations of a factorial.
See also
| 2006 AIME I (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 | ||
