Difference between revisions of "2006 AIME I Problems/Problem 4"

Latest revision as of 21:56, 27 September 2024

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 $\boxed{124}$ .

Solution 2 (Legendre's Formula )

This problem can be easily solved using Legendre's Formula:

First is to account for all of the factorials that are greater than $5n$ or $5, 10, 15, 20...100$ , then the factorials that are greater than $5^2n$ or $25, 50, 75, 100$ . Since $5^3=125>100$ we do not need to account for it.

This gives $96+91+86+...+1$ and $76+51+26+1$ respectively. Adding all of these terms up gives 1124 or $\boxed{124}$ .

~PeterDoesPhysics

Video Solution by OmegaLearn

https://youtu.be/p5f1u44-pvQ?t=413

~ pi_is_3.14

@@ Line 1: / Line 1: @@
 == Problem ==
+Let <math> N </math> be the number of consecutive <math>0</math>'s at the right end of the decimal representation of the product <math> 1!2!3!4!\cdots99!100!. </math> Find the remainder when <math> N </math> is divided by <math>1000</math>.
+== 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.
-Let <math> (a_1,a_2,a_3,\ldots,a_{12}) </math> be a permutation of <math> (1,2,3,\ldots,12) </math> for which
+One way to do this is as follows: <math>96</math> of the numbers <math>1!,\ 2!,\ 3!,\ 100!</math> have a factor of <math>5</math>. <math>91</math> have a factor of <math>10</math>. <math>86</math> have a factor of <math>15</math>. And so on. This gives us an initial count of <math>96 + 91 + 86 + \ldots + 1</math>.  Summing this [[arithmetic series]] of <math>20</math> terms, we get <math>970</math>.  However, we have neglected some powers of <math>5</math> - every <math>n!</math> term for <math>n\geq25</math> has an additional power of <math>5</math> dividing it, for <math>76</math> extra; every n! for <math>n\geq 50</math> has one more in addition to that, for a total of <math>51</math> extra; and similarly there are <math>26</math> extra from those larger than <math>75</math> and <math>1</math> extra from <math>100</math>.  Thus, our final total is <math>970 + 76 + 51 + 26 + 1 = 1124</math>, and the answer is <math>\boxed{124}</math>.
-<center><math> a_1>a_2>a_3>a_4>a_5>a_6 \mathrm{\  and \ } a_6<a_7<a_8<a_9<a_{10}<a_{11}<a_{12}. </math></center>
+== Solution 2 (Legendre's Formula )==
-An example of such a permutation is <math> (6,5,4,3,2,1,7,8,9,10,11,12). </math> Find the number of such permutations.
+This problem can be easily solved using [[Legendre's Formula]]:
-== Solution ==
+First is to account for all of the factorials that are greater than <math>5n</math> or <math>5, 10, 15, 20...100</math>, then the factorials that are greater than <math>5^2n</math> or <math>25, 50, 75, 100</math>. Since <math>5^3=125>100</math> we do not need to account for it.
+This gives <math>96+91+86+...+1</math> and <math>76+51+26+1</math> respectively. Adding all of these terms up gives 1124 or <math>\boxed{124}</math>.
+~PeterDoesPhysics
+== Video Solution by OmegaLearn ==
+https://youtu.be/p5f1u44-pvQ?t=413
-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.
+~ pi_is_3.14
 == See also ==
@@ Line 17: / Line 27: @@
 [[Category:Intermediate Combinatorics Problems]]
 [[Category:Intermediate Number Theory Problems]]
+{{MAA Notice}}

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

Page

Toolbox

Search