Skip to main content

2007 AMC 10B Problem 24

Problem 24 of 25HarderAlgebraNumber Theory

Let nn denote the smallest positive integer that is divisible by both 44 and 9,9, and whose base-1010 representation consists of only 44’s and 99’s, with at least one of each. What are the last four digits of n?n?

Answer choices

Show solution

Solution

Since nn is divisible by 9,9, its digit sum is a multiple of 9.9. With kk fours and mm nines, the digit sum is 4k+9m,4k+9m, so 4k4k is divisible by 9,9, forcing kk to be divisible by 9.9. Thus k9,k\ge 9, and with at least one 9,9, the number has at least ten digits. For divisibility by 4,4, the last two digits must form a multiple of 4,4, and among 44,44, 49,49, 94,94, and 9999 only 4444 works, so nn ends in 44.44. The smallest such ten-digit number places the single 99 in the lowest available position, giving 4,444,444,944.4{,}444{,}444{,}944. Its last four digits are 4944.4944. Thus, the correct answer is C.

More practice

Concepts: divisibility · digits · optimization

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.