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 "2010 AMC 12A Problems/Problem 23"

m (Semi-automated contest formatting - script by azjps)
m (debug error)
Line 28: Line 28:
 
<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\cdot -21\cdot 6\\
−
= -1\pmod{25}&=24\pmod{25}.\end{align*}</cmath>
+
&= -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> (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>.

Revision as of 22:36, 25 February 2010

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}$ by taking out all the factors of $5$ in $N$, 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 multiple of 5 is replaced by the number with all its factors of 5 removed. Specifically, every number in the form $5n$ is replaced by $n$, and every number in the form $25n$ 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*}

Using the identity at the beginning of the solution, 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}$ (or simply the fact that $2^{21}=2097152$ if you have your powers of 2 memorized), 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 12A (Problems • Answer Key • Resources)
Preceded by
Problem 22 		Followed by
Problem 24
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 12 Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2010_AMC_12A_Problems/Problem_23&oldid=33685"