2010 AMC 10A Problem 24

The idea: throw away the tens that make the zeros, then keep track of only a remainder, never the huge number itself.

Step 1: count the zeros. Each zero at the end comes from one $5$ paired with one $2$. There are far more $2$s than $5$s, so count the $5$s.
- Multiples of $5$ up to $90$: $90 \div 5 = 18$ of them.
- $25$, $50$, $75$ each give one extra $5$: $3$ more.

That is $21$ fives, so $90!$ ends in $21$ zeros. Let $M$ be $90!$ with $21$ fives and $21$ twos taken out. The answer $n$ is the last two digits of $M$.

Step 2: why we only need the remainder after dividing by 25. $90!$ has $86$ twos in total ($45 + 22 + 11 + 5 + 2 + 1$, counting multiples of $2, 4, 8, 16, 32, 64$), so $M$ still has $65$ twos. That makes $n$ a multiple of $4$. All five choices are multiples of $4$, so that does not decide it. But the choices leave different remainders when divided by $25$:

So we find the remainder of $M$ after dividing by $25$. Two rules help:
- To find the remainder of a product, you can multiply the remainders instead.
- A remainder of $24$ is "one short of $25$," so it behaves like $-1$: two of them multiply to a remainder of $1$.

(Short notation: $a \equiv b \pmod{25}$ means $a$ and $b$ leave the same remainder when divided by $25$.)

Step 3: a useful fact. Four numbers in a row with no multiple of $5$ multiply to a remainder of $24$, that is $-1$:
- $1 \cdot 2 \cdot 3 \cdot 4 = 24$.
- $6 \cdot 7 \cdot 8 \cdot 9 = 3024 = 25 \cdot 121 - 1$.

In general, when you multiply out $(5k+1)(5k+2)(5k+3)(5k+4)$, you get $24$ plus terms that are all multiples of $25$. (The terms with one factor $5k$ add up to $5k \cdot (24 + 12 + 8 + 6) = 250k$; the others contain $5k$ twice or more.)

Step 4: take the fives out of $90!$.
- The $72$ numbers from $1$ to $90$ that are not multiples of $5$ form $18$ groups of four: $1$–$4$, $6$–$9$, …, $86$–$89$. Their product acts like $(-1)^{18} = 1$.
- The $18$ multiples of $5$ are $5 \cdot 1, 5 \cdot 2, \ldots, 5 \cdot 18$. Taking out the $18$ fives leaves $1 \cdot 2 \cdots 18 = 18!$.

Step 5: do the same inside $18!$.
- Non-multiples of $5$: the groups $1$–$4$, $6$–$9$, $11$–$14$ give $(-1)^3 = -1$. The leftovers $16 \cdot 17 \cdot 18 = 4896 = 25 \cdot 196 - 4$ act like $-4$. Together: $(-1)(-4) = 4$.
- Multiples of $5$: $5, 10, 15$. Taking out the $3$ fives leaves $1 \cdot 2 \cdot 3 = 6$.

So $90!$ with all $21$ fives removed leaves remainder $1 \cdot 4 \cdot 6 = 24$, which is $-1$.

Step 6: take out the 21 twos. $2^{10} = 1024 = 25 \cdot 41 - 1$ acts like $-1$, so $2^{20}$ acts like $1$ and $2^{21}$ acts like $2$. We know $M \times 2^{21}$ leaves remainder $24$, so $2 \times M$ leaves remainder $24$. If $M$ leaves remainder $r$ (from $0$ to $24$), then $2r$ is $24$ or $49$. It must be even, so $2r = 24$ and $r = 12$.

Step 7: match. Only choice $12$ leaves remainder $12$.

The answer is $\boxed{\textbf{(A)}\ 12}$.

The last two digits of a number are its remainder after dividing by $100$, and $100 = 4 \times 25$. The factor $4$ is easy because so many $2$s are left over, so all the work is with $25$. Removing fives in layers ($90!$, then $18!$, then $3!$) and treating each run of four as $-1$ keeps every number small.

The exponent of $5$ in $90!$ is $\lfloor 90/5 \rfloor + \lfloor 90/25 \rfloor = 18 + 3 = 21$, and the exponent of $2$ is $45 + 22 + 11 + 5 + 2 + 1 = 86$. So $90!$ ends in $21$ zeros and $n \equiv \dfrac{90!}{10^{21}} \pmod{100}$. This quotient still contains $2^{65}$, so $n \equiv 0 \pmod 4$; every choice is a multiple of $4$, so the work is mod $25$.

A useful fact. For any $k$, $(5k+1)(5k+2)(5k+3)(5k+4) \equiv 1 \cdot 2 \cdot 3 \cdot 4 = 24 \equiv -1 \pmod{25}$ (the other terms of the expansion are multiples of $25$).

Remove the 5s. Write $90! = 5^{18} \cdot 18! \cdot P$, where $P$ is the product of the $72$ non-multiples of $5$ up to $90$. Those form $18$ blocks of four, so $P \equiv (-1)^{18} = 1$. Similarly $18! = 5^3 \cdot 3! \cdot Q$ with $Q = (1\cdot2\cdot3\cdot4)(6\cdots9)(11\cdots14)(16\cdot17\cdot18) \equiv (-1)^3 \cdot 16 \cdot 17 \cdot 18$. Since $16 \cdot 17 = 272 \equiv -3$ and $-3 \cdot 18 = -54 \equiv -4$, we get $Q \equiv 4$. Hence
$$\frac{90!}{5^{21}} = 6 \cdot Q \cdot P \equiv 24 \equiv -1 \pmod{25}.$$

Remove the 2s. $2^{10} = 1024 \equiv -1$, so $2^{21} = (2^{10})^2 \cdot 2 \equiv 2 \pmod{25}$. Then $n = \dfrac{90!/5^{21}}{2^{21}}$ satisfies $2n \equiv -1 \equiv 24$, so $n \equiv 12 \pmod{25}$.

Among the choices, $32 \equiv 7$, $48 \equiv 23$, $52 \equiv 2$, $68 \equiv 18 \pmod{25}$; only $12$ works.

The answer is $\boxed{\textbf{(A)}\ 12}$.