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 "2002 AMC 10P Problems/Problem 22"

(→‎Solution 1)
(→‎Solution 1)
 
(11 intermediate revisions by the same user not shown)
Line 16: Line 16:
  
 
== Solution 1==
 
== Solution 1==
−
We can solve this problem with an application of Legendre's formula.  
+
We can solve this problem with an application of [[Legendre's Formula|Legendre's Formula]].  
  
−
We know that there will be an abundance of factors of <math>2</math> compared to factors of <math>5,</math> so finding the amount of factors of <math>5</math> is equivalent to finding how many factors of <math>10</math> there are. Additionally, squaring a number will multiply the exponent of each factor by <math>2.</math> Therefore, we plug in <math>p=5</math> and <math>n=2002,</math> then plug in <math>p=5</math> and <math>n=1001</math> and multiply by <math>2</math> in:
+
We know that there will be an abundance of factors of <math>2</math> compared to factors of <math>5,</math> so finding the amount of factors of <math>5</math> is equivalent to finding how many factors of <math>10</math> there are, which is equivalent to how many zeroes there are at the end of the number. Additionally, squaring a number will multiply the exponent of each factor by <math>2.</math> Therefore, we plug in <math>p=5</math> and <math>n=2002,</math> then plug in <math>p=5</math> and <math>n=1001</math> and multiply by <math>2</math> in:
  
 
<cmath>e_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i}\right\rfloor =\frac{n-S_{p}(n)}{p-1}</cmath>
 
<cmath>e_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i}\right\rfloor =\frac{n-S_{p}(n)}{p-1}</cmath>
 +
 +
As such,
  
 
\begin{align*}
 
\begin{align*}
Line 30: Line 32:
 
or alternatively,
 
or alternatively,
  
−
<math>e_5(2002!)=\frac{2002-S_5(2002)}{5-1}=\frac{2002-S_5(31002_5)]}{4}=\frac{2002-6}{4}=499.</math>
+
<math>e_5(1001!)=\frac{2002-S_5(2002)}{5-1}=\frac{2002-S_5(31002_5)]}{4}=\frac{2002-6}{4}=499.</math>
  
 
Similarly,  
 
Similarly,  
  
 
\begin{align*}
 
\begin{align*}
−
e_5(2002!)=&\left\lfloor\frac{1001}{5}\right\rfloor+\left\lfloor\frac{1001}{5^2}\right\rfloor+\left\lfloor\frac {1001}{5^3}\right\rfloor+\left\lfloor\frac{1001}{5^4}\right\rfloor\\
+
e_5(1001!)=&\left\lfloor\frac{1001}{5}\right\rfloor+\left\lfloor\frac{1001}{5^2}\right\rfloor+\left\lfloor\frac {1001}{5^3}\right\rfloor+\left\lfloor\frac{1001}{5^4}\right\rfloor\\
 
=&200+40+8+1 \\
 
=&200+40+8+1 \\
 
=&299
 
=&299
Line 45: Line 47:
  
 
In any case, our answer is <math>499-2(249)= \boxed{\textbf{(B) } 1}.</math>
 
In any case, our answer is <math>499-2(249)= \boxed{\textbf{(B) } 1}.</math>
 +
 +
== Solution 2 ==
 +
 +
In case we have forgotten Legendre's formula or haven't learned it, this solution is equally viable. With similar reasoning to solution 1, all we need to find is the amount of multiples of <math>5</math> in the problem.
 +
 +
Cancel <math>1001!</math> from the top and bottom of the fraction. We get <math>\frac{2002!}{(1001)!^2}=\frac{1002 \cdot 1003 \cdot \; \dots \; \cdot 2002}{1 \cdot 2 \; \dots \; \cdot 1001}.</math> We can set a bijection between the two sets of terms with a multiple of <math>5.</math> Let <math>n</math> be a number from <math>1001!</math> that is a multiple of <math>5.</math> Its corresponding multiple of <math>5</math> from <math>\frac{2002!}{1001!}</math> will be <math>n+1000.</math> For clarity, <math>5</math> will group with <math>1005,</math>  <math>10</math> will group with <math>1010</math> <math> \; \dots \; </math>  <math>1000</math> will group with <math>2000.</math> Our goal is to find number(s) where <math>\frac{n+1000}{n}</math> for all <math>n \leq 1000, n \in 5\mathbb{Z}^{+}</math> will result in a multiple of <math>5.</math> Simplifying this equation, <math>1+\frac{1000}{n}=</math> a multiple of <math>5.</math> We can conclude that <math>n=250</math> is the only solution to this equation since <math>1000</math> is not divisible by any other number ending in a <math>4</math> or <math>9</math> (we can write the factors of <math>1000</math> to confirm this; <math>2^1=2,</math> <math>2^2=4,</math> and <math>2^3=8</math> are the only numbers that do not end in <math>5</math> or <math>0</math> because all multiples of <math>5</math> end in <math>5</math> or <math>0</math>). A quick check reveals <math>\frac{1250}{5}=250,</math> which has <math>3</math> multiples of <math>5</math> and <math>\frac{250}{5}=50,</math> which has <math>2</math> multiples of <math>5.</math> Thus, <math>n=250</math> is the only instance where there is an extra multiple of <math>5</math> at the top, meaning our answer is <math>\boxed{\textbf{(B) } 1}.</math>
  
 
== See also ==
 
== See also ==
 
{{AMC10 box|year=2002|ab=P|num-b=21|num-a=23}}
 
{{AMC10 box|year=2002|ab=P|num-b=21|num-a=23}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 04:20, 17 July 2024

Problem

In how many zeroes does the number $\frac{2002!}{(1001!)^2}$ end?

$\text{(A) }0 \qquad \text{(B) }1 \qquad \text{(C) }2 \qquad \text{(D) }200 \qquad \text{(E) }400$

Solution 1

We can solve this problem with an application of Legendre's Formula.

We know that there will be an abundance of factors of $2$ compared to factors of $5,$ so finding the amount of factors of $5$ is equivalent to finding how many factors of $10$ there are, which is equivalent to how many zeroes there are at the end of the number. Additionally, squaring a number will multiply the exponent of each factor by $2.$ Therefore, we plug in $p=5$ and $n=2002,$ then plug in $p=5$ and $n=1001$ and multiply by $2$ in:

\[e_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i}\right\rfloor =\frac{n-S_{p}(n)}{p-1}\]

As such,

\begin{align*} e_5(2002!)=&\left\lfloor\frac{2002}{5}\right\rfloor+\left\lfloor\frac{2002}{5^2}\right\rfloor+\left\lfloor\frac {2002}{5^3}\right\rfloor+\left\lfloor\frac{2002}{5^4}\right\rfloor\\ =&400+80+16+3 \\ =&499 \end{align*}

or alternatively,

$e_5(1001!)=\frac{2002-S_5(2002)}{5-1}=\frac{2002-S_5(31002_5)]}{4}=\frac{2002-6}{4}=499.$

Similarly,

\begin{align*} e_5(1001!)=&\left\lfloor\frac{1001}{5}\right\rfloor+\left\lfloor\frac{1001}{5^2}\right\rfloor+\left\lfloor\frac {1001}{5^3}\right\rfloor+\left\lfloor\frac{1001}{5^4}\right\rfloor\\ =&200+40+8+1 \\ =&299 \end{align*}

or alternatively,

$e_5(1001!)=\frac{1001-S_5(1001)}{5-1}=\frac{1001-S_5(13001_5)]}{4}=\frac{1001-5}{4}=249.$

In any case, our answer is $499-2(249)= \boxed{\textbf{(B) } 1}.$

Solution 2

In case we have forgotten Legendre's formula or haven't learned it, this solution is equally viable. With similar reasoning to solution 1, all we need to find is the amount of multiples of $5$ in the problem.

Cancel $1001!$ from the top and bottom of the fraction. We get $\frac{2002!}{(1001)!^2}=\frac{1002 \cdot 1003 \cdot \; \dots \; \cdot 2002}{1 \cdot 2 \; \dots \; \cdot 1001}.$ We can set a bijection between the two sets of terms with a multiple of $5.$ Let $n$ be a number from $1001!$ that is a multiple of $5.$ Its corresponding multiple of $5$ from $\frac{2002!}{1001!}$ will be $n+1000.$ For clarity, $5$ will group with $1005,$ $10$ will group with $1010$ $\; \dots \;$ $1000$ will group with $2000.$ Our goal is to find number(s) where $\frac{n+1000}{n}$ for all $n \leq 1000, n \in 5\mathbb{Z}^{+}$ will result in a multiple of $5.$ Simplifying this equation, $1+\frac{1000}{n}=$ a multiple of $5.$ We can conclude that $n=250$ is the only solution to this equation since $1000$ is not divisible by any other number ending in a $4$ or $9$ (we can write the factors of $1000$ to confirm this; $2^1=2,$ $2^2=4,$ and $2^3=8$ are the only numbers that do not end in $5$ or $0$ because all multiples of $5$ end in $5$ or $0$). A quick check reveals $\frac{1250}{5}=250,$ which has $3$ multiples of $5$ and $\frac{250}{5}=50,$ which has $2$ multiples of $5.$ Thus, $n=250$ is the only instance where there is an extra multiple of $5$ at the top, meaning our answer is $\boxed{\textbf{(B) } 1}.$

See also

2002 AMC 10P (Problems • Answer Key • Resources)
Preceded by
Problem 21 		Followed by
Problem 23
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2002_AMC_10P_Problems/Problem_22&oldid=222884"