2007 AMC 10B Problem 24

Use the two divisibility tests one at a time, then make the number as small as possible.

Step 1: divisible by 4. A number is a multiple of $4$ exactly when its last two digits are. The possible endings are $44, 49, 94, 99$. Only $44 = 4 \times 11$ is a multiple of $4$. So $n$ ends in $44$.

Step 2: divisible by 9. A number is a multiple of $9$ exactly when its digit sum is.

1. Each $9$ adds $9$ to the digit sum, which never changes whether the sum is a multiple of $9$.
2. Each $4$ adds $4$. With one $4$ the sum from the $4$'s is $4$, with two it is $8$, and so on. That sum is a multiple of $9$ only when the number of $4$'s is a multiple of $9$.
3. There is at least one $4$, so there are at least nine $4$'s.

Step 3: make it small.

1. We need at least nine $4$'s and at least one $9$, so at least $10$ digits. Any $10$-digit number is smaller than any longer one, so use exactly nine $4$'s and one $9$.
2. Among these, the smaller number has its $9$ farther to the right. The last two digits must be $44$, so the $9$ goes third from the right:
$$n = 4444444944.$$
3. Check: it ends in $44$, and its digit sum is $9 \times 4 + 9 = 45 = 9 \times 5$.

The last four digits are $4944$.

The answer is $\boxed{\textbf{(C)}\ 4944}$.

Tests for $4$ and $9$ look at digits, so they turn into rules about the ending and about how many of each digit you use. To make a number as small as possible, first use as few digits as possible, then push the larger digits as far to the right as the rules allow.