AoPSWiki

Do you have what it takes to be the next brilliant trader, researcher, or developer at Jane Street Capital? Find out in the Careers in Mathematics Forum.

Personal tools

Search

Toolbox

2006 AIME II Problems/Problem 3

From AoPSWiki

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

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

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

Number Theory

2006 AIME II (Problems • Resources)
Preceded by Problem 2	Followed by Problem 4
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15

Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/2006_AIME_II_Problems/Problem_3"

Category: Intermediate Number Theory Problems

Visit the AoPS Book Store.

© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us