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 "2006 AIME I Problems/Problem 3"

(→‎Problem)
(→‎Solution)
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
−
The number can be represented as <math>10^na+b</math>, where <math> a </math> is the leftmost digit, and <math> b </math> is the rest of the number. We know that <math>b=\frac{10^na+b}{29} \implies 28b=2^2\times7b=10^na</math>. Thus <math> a </math> has to be 7 since <math> 10^n </math> can not have 7 as a factor, and the smallest <math> 10^n </math> can be and have a factor of <math> 2^2 </math> is <math> 10^2=100. </math> We find that <math> b </math> is 25, so the number is 725.
+
 
 +
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 ==
 
== See also ==

Revision as of 13:00, 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 (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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_AIME_I_Problems/Problem_3&oldid=16802"