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 A Problems/Problem 4"

(→‎Problem)
(→‎Solution)
Line 4: Line 4:
 
== Solution ==
 
== Solution ==
  
−
Clearly, <math>a_6=1</math>.  Now, consider selecting <math>5</math> of the remaining <math>11</math> values.  Sort these values in descending order, and sort the other <math>6</math> values in ascending order.  Now, let the <math>5</math> selected values be <math>a_1</math> through <math>a_5</math>, and let the remaining <math>6</math> be <math>a_7</math> through <math>{a_{12}}</math>.  It is now clear that there is a [[bijection]] between the number of ways to select <math>5</math> values from <math>11</math> and ordered 12-tuples <math>(a_1,\ldots,a_{12})</math>.  Thus, there will be <math>{11 \choose 5}=462</math> such ordered 12-tuples.
+
A number in [[decimal notation]] ends in a zero for each power of ten which divides it.  Thus, we need to count both the number of 5s and the number of 2s dividing into our given expression.  Since there are clearly more 2s than 5s, it is sufficient to count the number of 5s.
 +
One way to do this is as follows: 96 of the numbers 1!, 2!, 3!, ..., 100! have a factor of 5.  91 have a factor of 10.  86 have a factor of 15.  And so on.  This gives us an initial count of <math>96 + 91 + 86 + \ldots + 1</math>.  Summing this [[arithmetic series]] of 20 terms, we get 970.  However, we have neglected some powers of 5 -- every n! term for <math>n\geq25</math> has an additional power of 5 dividing it, for 76 extra; every n! for <math>n\geq 50</math> has one more in addition to that, for a total of 51 extra; and similarly there are 26 extra from those larger than 75 and 1 extra from 100.  Thus, our final total is 970 + 76 + 51 + 26 + 1 = 1124, and the answer is 124.
  
 
== See also ==
 
== See also ==

Revision as of 13:04, 25 September 2007

Problem

Let $N$ be the number of consecutive 0's at the right end of the decimal representation of the product $1!2!3!4!\cdots99!100!.$ Find the remainder when $N$ is divided by 1000.

Solution

A number in decimal notation ends in a zero for each power of ten which divides it. Thus, we need to count both the number of 5s and the number of 2s dividing into our given expression. Since there are clearly more 2s than 5s, it is sufficient to count the number of 5s. One way to do this is as follows: 96 of the numbers 1!, 2!, 3!, ..., 100! have a factor of 5. 91 have a factor of 10. 86 have a factor of 15. And so on. This gives us an initial count of $96 + 91 + 86 + \ldots + 1$. Summing this arithmetic series of 20 terms, we get 970. However, we have neglected some powers of 5 -- every n! term for $n\geq25$ has an additional power of 5 dividing it, for 76 extra; every n! for $n\geq 50$ has one more in addition to that, for a total of 51 extra; and similarly there are 26 extra from those larger than 75 and 1 extra from 100. Thus, our final total is 970 + 76 + 51 + 26 + 1 = 1124, and the answer is 124.

See also

2006 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 3 		Followed by
Problem 5
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_A_Problems/Problem_4&oldid=16809"