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 10A Problems/Problem 24"

(→‎Solution 2(bash))
(→‎Solution 2(bash))
Line 26: Line 26:
 
== Solution 2(bash) ==
 
== Solution 2(bash) ==
 
First, we list out all the numbers<br \>
 
First, we list out all the numbers<br \>
−
<math>90!=2^{65}3^{44}5^{21}7^{13}11^813^617^519^423^329^331^237^241^243^2\cdot47\cdot53\cdot\cdot\cdot89</math>
+
<math>90!=2^{65}3^{44}5^{21}7^{13}11^813^617^519^423^329^331^237^241^243^2\cdot47\cdot53\cdot\cdot\cdot89</math><br \>
−
Since we must get rid of ending <math>0</math>s, we get rid of <math>5^21</math> and the corresponding <math>2^21</math>
+
Since we must get rid of ending <math>0</math>s, we get rid of <math>5^{21}</math> and the corresponding <math>2^{21}</math><br \>
−
Next, we note that <math>2^22\equiv2^2</math>,<math>3^20\equiv3</math>, and <math>7^4\equiv7</math>, so it can be simplified to
+
Next, we note that <math>2^22\equiv2^2</math>,<math>3^20\equiv3</math>, and <math>7^4\equiv7</math>, so it can be simplified to<br \>
−
<math>2^43^47\cdot11^813^617^5\cdot\cdot\cdot89</math>
+
<math>2^43^47\cdot11^813^617^5\cdot\cdot\cdot89</math><br \>
 +
Then, we bash using these following <math>4</math> difference of squares tricks and multiplication<br \>
 +
1. <math>(10k-1)(10k+1)\equiv-1</math><br \>
 +
2. <math>(10k+3)(10k+7)\equiv21=3\cdot7</math><br \>
 +
3. <math>(10k+1)(10k+9)\equiv9=3^2</math><br \>
 +
4. <math>(10k-3)(10k+3)\equiv-9\equiv7\cdot13</math><br \>
 +
Handling of powers of <math>3</math> and <math>7</math> are especially critical<br \>
 +
In the end, we get
  
 
== See also ==
 
== See also ==

Revision as of 21:11, 1 February 2020

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 1(Bigbrain)

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}$.

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 = \frac{90!}{5^{21}},\] where every number in the form $5n$ 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}$.

Solution 2(bash)

First, we list out all the numbers
$90!=2^{65}3^{44}5^{21}7^{13}11^813^617^519^423^329^331^237^241^243^2\cdot47\cdot53\cdot\cdot\cdot89$
Since we must get rid of ending $0$s, we get rid of $5^{21}$ and the corresponding $2^{21}$
Next, we note that $2^22\equiv2^2$,$3^20\equiv3$, and $7^4\equiv7$, so it can be simplified to
$2^43^47\cdot11^813^617^5\cdot\cdot\cdot89$
Then, we bash using these following $4$ difference of squares tricks and multiplication
1. $(10k-1)(10k+1)\equiv-1$
2. $(10k+3)(10k+7)\equiv21=3\cdot7$
3. $(10k+1)(10k+9)\equiv9=3^2$
4. $(10k-3)(10k+3)\equiv-9\equiv7\cdot13$
Handling of powers of $3$ and $7$ are especially critical
In the end, we get

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

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=2010_AMC_10A_Problems/Problem_24&oldid=116489"