Art of Problem Solving
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

2010 AMC 10A Problems/Problem 24: Difference between revisions

← Older editNewer edit →
Nathan wailes (talk | contribs)
2,960 edits
No edit summary
Armalite46 (talk | contribs)
206 edits
Line 7: Line 7:
== Solution ==
== Solution ==


We will use the fact that for any integer <math>n</math>,
We will use the fact that for any integer <math>n</math>, <cmath>\begin{align*}(5n+1)(5n+2)(5n+3)(5n+4)&=[(5n+4)(5n+1)][(5n+2)(5n+3)]\\ &=(25n^2+25n+4)(25n^2+25n+6)\equiv 4\cdot 6\\ &=24\pmod{25}\equiv -1\pmod{25}.\end{align*}</cmath>  
<cmath>\begin{align*}(5n+1)(5n+2)(5n+3)(5n+4)&=[(5n+4)(5n+1)][(5n+2)(5n+3)]\\
&=(25n^2+25n+4)(25n^2+25n+6)\equiv 4\cdot 6\\
&=24\pmod{25}\equiv -1\pmod{25}.\end{align*}</cmath>


First, we find that the number of factors of <math>10</math> in <math>90!</math> is equal to <math>\left\lfloor \frac{90}5\right\rfloor+\left\lfloor\frac{90}{25}\right\rfloor=18+3=21</math>. Let <math>N=\frac{90!}{10^{21}}</math>. The <math>n</math> we want is therefore the last two digits of <math>N</math>, or <math>N\pmod{100}</math>. Since there is clearly an excess of factors of 2, we know that <math>N\equiv 0\pmod 4</math>, so it remains to find <math>N\pmod{25}</math>.
First, we find that the number of factors of <math>10</math> in <math>90!</math> is equal to <math>\left\lfloor \frac{90}5\right\rfloor+\left\lfloor\frac{90}{25}\right\rfloor=18+3=21</math>. Let <math>N=\frac{90!}{10^{21}}</math>. The <math>n</math> we want is therefore the last two digits of <math>N</math>, or <math>N\pmod{100}</math>. Since there is clearly an excess of factors of 2, we know that <math>N\equiv 0\pmod 4</math>, so it remains to find <math>N\pmod{25}</math>.  


If we divide <math>N</math> by <math>5^{21}</math> by taking out all the factors of <math>5</math> in <math>N</math>, we can write <math>N</math> as <math>\frac M{2^{21}}</math> where
If we divide <math>N</math> by <math>5^{21}</math> , we can write <math>N</math> as <math>\frac M{2^{21}}</math> where <cmath>M=1\cdot 2\cdot 3\cdot 4\cdot 1\cdot 6\cdot 7\cdot 8\cdot 9\cdot 2\cdots 89\cdot 18,</cmath> where every number in the form <math>(5^a)*n</math> is replaced by <math>n</math>.  
<cmath>M=1\cdot 2\cdot 3\cdot 4\cdot 1\cdot 6\cdot 7\cdot 8\cdot 9\cdot 2\cdots 89\cdot 18,</cmath>
where every multiple of 5 is replaced by the number with all its factors of 5 removed. Specifically, every number in the form <math>5n</math> is replaced by <math>n</math>, and every number in the form <math>25n</math> is replaced by <math>n</math>.


The number <math>M</math> can be grouped as follows:
The number <math>M</math> can be grouped as follows:  


<cmath>\begin{align*}M= &(1\cdot 2\cdot 3\cdot 4)(6\cdot 7\cdot 8\cdot 9)\cdots(86\cdot 87\cdot 88\cdot 89)\\
<cmath>\begin{align*}M= &(1\cdot 2\cdot 3\cdot 4)(6\cdot 7\cdot 8\cdot 9)\cdots(86\cdot 87\cdot 88\cdot 89)\\ &\cdot (1\cdot 2\cdot 3\cdot 4)(6\cdot 7\cdot 8\cdot 9)\cdots (16\cdot 17\cdot 18) \\ &\cdot (1\cdot 2\cdot 3).\end{align*}</cmath>  
&\cdot (1\cdot 2\cdot 3\cdot 4)(6\cdot 7\cdot 8\cdot 9)\cdots (16\cdot 17\cdot 18) \\
&\cdot (1\cdot 2\cdot 3).\end{align*}</cmath>


Using the identity at the beginning of the solution, we can reduce <math>M</math> to
Hence, we can reduce <math>M</math> to  


<cmath>\begin{align*}M&\equiv(-1)^{18} \cdot (-1)^3(16\cdot 17\cdot 18) \cdot (1\cdot 2\cdot 3) \\
<cmath>\begin{align*}M&\equiv(-1)^{18} \cdot (-1)^3(16\cdot 17\cdot 18) \cdot (1\cdot 2\cdot 3) \\ &= 1\cdot -21\cdot 6\\ &= -1\pmod{25} =24\pmod{25}.\end{align*}</cmath>  
&= 1\cdot -21\cdot 6\\
&= -1\pmod{25} =24\pmod{25}.\end{align*}</cmath>


Using the fact that <math>2^{10}=1024\equiv -1\pmod{25}</math> (or simply the fact that <math>2^{21}=2097152</math> if you have your powers of 2 memorized), we can deduce that <math>2^{21}\equiv 2\pmod{25}</math>. Therefore <math>N=\frac M{2^{21}}\equiv \frac {24}2\pmod{25}=12\pmod{25}</math>.
Using the fact that <math>2^{10}=1024\equiv -1\pmod{25}</math>,we can deduce that <math>2^{21}\equiv 2\pmod{25}</math>. Therefore <math>N=\frac M{2^{21}}\equiv \frac {24}2\pmod{25}=12\pmod{25}</math>.  


Finally, combining with the fact that <math>N\equiv 0\pmod 4</math> yields <math>n=\boxed{\textbf{(A)}\ 12}</math>.
Finally, combining with the fact that <math>N\equiv 0\pmod 4</math> yields <math>n=\boxed{\textbf{(A)}\ 12}</math>.

Revision as of 20:07, 3 September 2013

Problem

The number obtained from the last two nonzero digits of $90!$ is equal to $n$. What is $n$?

$\textbf{(A)}\ 12 \qquad \textbf{(B)}\ 32 \qquad \textbf{(C)}\ 48 \qquad \textbf{(D)}\ 52 \qquad \textbf{(E)}\ 68$

Solution

We will use the fact that for any integer $n$, \begin{align*}(5n+1)(5n+2)(5n+3)(5n+4)&=[(5n+4)(5n+1)][(5n+2)(5n+3)]\\ &=(25n^2+25n+4)(25n^2+25n+6)\equiv 4\cdot 6\\ &=24\pmod{25}\equiv -1\pmod{25}.\end{align*}

First, we find that the number of factors of $10$ in $90!$ is equal to $\left\lfloor \frac{90}5\right\rfloor+\left\lfloor\frac{90}{25}\right\rfloor=18+3=21$. Let $N=\frac{90!}{10^{21}}$. The $n$ we want is therefore the last two digits of $N$, or $N\pmod{100}$. Since there is clearly an excess of factors of 2, we know that $N\equiv 0\pmod 4$, so it remains to find $N\pmod{25}$.

If we divide $N$ by $5^{21}$ , we can write $N$ as $\frac M{2^{21}}$ where \[M=1\cdot 2\cdot 3\cdot 4\cdot 1\cdot 6\cdot 7\cdot 8\cdot 9\cdot 2\cdots 89\cdot 18,\] where every number in the form $(5^a)*n$ is replaced by $n$.

The number $M$ can be grouped as follows:

\begin{align*}M= &(1\cdot 2\cdot 3\cdot 4)(6\cdot 7\cdot 8\cdot 9)\cdots(86\cdot 87\cdot 88\cdot 89)\\ &\cdot (1\cdot 2\cdot 3\cdot 4)(6\cdot 7\cdot 8\cdot 9)\cdots (16\cdot 17\cdot 18) \\ &\cdot (1\cdot 2\cdot 3).\end{align*}

Hence, we can reduce $M$ to

\begin{align*}M&\equiv(-1)^{18} \cdot (-1)^3(16\cdot 17\cdot 18) \cdot (1\cdot 2\cdot 3) \\ &= 1\cdot -21\cdot 6\\ &= -1\pmod{25} =24\pmod{25}.\end{align*}

Using the fact that $2^{10}=1024\equiv -1\pmod{25}$,we can deduce that $2^{21}\equiv 2\pmod{25}$. Therefore $N=\frac M{2^{21}}\equiv \frac {24}2\pmod{25}=12\pmod{25}$.

Finally, combining with the fact that $N\equiv 0\pmod 4$ yields $n=\boxed{\textbf{(A)}\ 12}$.

See also

2010 AMC 10A (Problems • Answer Key • Resources)
Preceded by
Problem 23 		Followed by
Problem 25
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

These problems are copyrighted © by the Mathematical Association of America.

Retrieved from "https://wiki.aopstest.com/wiki/index.php?title=2010_AMC_10A_Problems/Problem_24&oldid=57035"