2007 AMC 10B Problem 24

Question

Let

n

denote the smallest positive integer that is divisible by both

4

and

9,

and whose base-

10

representation consists of only

4

’s and

9

’s, with at least one of each. What are the last four digits of

n?

4444

4494

4944

9444

9944

Answer: C

Concepts:divisibility digits optimization

Difficulty rating: 1980

Small hint:

Divisibility by

9

constrains the digit sum; divisibility by

4

constrains the last two digits

Big hint:

The digit sum forces at least nine

4

’s, and the last two digits must both be

4

Solution:

Since

n

is divisible by

9,

its digit sum is a multiple of

9.

With

k

fours and

m

nines, the digit sum is

4k+9m,

so

4k

is divisible by

9,

forcing

k

to be divisible by

9.

Thus

k\ge 9,

and with at least one

9,

the number has at least ten digits.

For divisibility by

4,

the last two digits must form a multiple of

4,

and among

44,

49,

94,

and

99

only

44

works, so

n

ends in

44.

The smallest such ten-digit number places the single

9

in the lowest available position, giving

4{,}444{,}444{,}944.

Its last four digits are

4944.

Thus, the correct answer is C.