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.

Divisibility by $4$ is decided by the last two digits. Of the endings $44, 49, 94, 99$, only $44$ is a multiple of $4$, so $n$ ends in $44$.

Divisibility by $9$ is decided by the digit sum. Each $9$ contributes $9$, which is already a multiple of $9$, so the digit sum is a multiple of $9$ exactly when $4 \times (\text{number of } 4\text{'s})$ is, that is, when the number of $4$'s is a multiple of $9$. There must be at least one $4$, hence at least nine $4$'s.

Now minimize. The number must have at least one $9$ and at least nine $4$'s, so at least $10$ digits, and a $10$-digit number beats any longer one. Among $10$-digit numbers with nine $4$'s and one $9$, the smallest puts the $9$ as far right as possible; since the last two digits must be $44$, the $9$ goes in the third position from the right:
$$n = 4444444944.$$
This is divisible by $4$ (ends in $44$) and by $9$ (digit sum $9 \cdot 4 + 9 = 45$).

Its last four digits are $4944$.

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