Difference between revisions of "2010 AMC 12A Problems/Problem 23"

(Solution)
m (Solution)
Line 25: Line 25:
  
 
Where the first line is composed of the numbers in <math>90!</math> that aren't multiples of five, the second line is the multiples of five '''and not 25''' after they have been divided by five, and the third line is multiples of 25 after they have been divided by 25.
 
Where the first line is composed of the numbers in <math>90!</math> that aren't multiples of five, the second line is the multiples of five '''and not 25''' after they have been divided by five, and the third line is multiples of 25 after they have been divided by 25.
 +
 
Using the identity at the beginning of the solution, we can reduce <math>M</math> to
 
Using the identity at the beginning of the solution, we can reduce <math>M</math> to
  

Revision as of 14:55, 31 December 2011

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*}

Where the first line is composed of the numbers in $90!$ that aren't multiples of five, the second line is the multiples of five and not 25 after they have been divided by five, and the third line is multiples of 25 after they have been divided by 25.

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 (ProblemsAnswer KeyResources)
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