Difference between revisions of "2006 AIME II Problems/Problem 3"

 
m
Line 1: Line 1:
#REDIRECT [[2006 AIME A Problems/Problem 3]]
+
== 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 17:58, 25 September 2007

Problem

Let $P$ be the product of the first $100$ positive odd integers. Find the largest integer $k$ such that $P$ is divisible by $3^k .$

Solution

Note that the product of the first $100$ positive odd integers can be written as $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!}$

Hence, we seek the number of threes in $200!$ decreased by the number of threes in $100!.$

There are

$\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$

threes in $200!$ and

$\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$

threes in $100!$

Therefore, we have a total of $97-48=049$ threes.

For more information, see also prime factorizations of a factorial.

See also

2006 AIME I (ProblemsAnswer KeyResources)
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