Difference between revisions of "2006 AIME I Problems/Problem 4"
m (rv) |
m (tex) |
||
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
| − | Let <math> N </math> be the number of consecutive 0'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 1000. | + | 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 == | == 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. | 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: | + | |
| + | 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>. | ||
== See also == | == See also == | ||
Revision as of 14:02, 25 November 2007
Problem
Let 
be the number of consecutive 
's at the right end of the decimal representation of the product 
Find the remainder when is divided by 
.
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: 
of the numbers 
have a factor of 
. 
have a factor of 
. 
have a factor of 
. And so on. This gives us an initial count of 
. Summing this arithmetic series of 
terms, we get 
. However, we have neglected some powers of - every 
term for 
has an additional power of dividing it, for 
extra; every n! for 
has one more in addition to that, for a total of 
extra; and similarly there are 
extra from those larger than 
and 
extra from 
. Thus, our final total is 
, and the answer is 
.
See also
| 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 | ||
