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.