AMC 10 · 2007 · #24

Grade 6 number-theory
Archetype Small-Domain Constrained Search └ Sub-archetype Factor / Divisibility Constraint
divisibility-rulesdigit-sumdigit-constraints extremal-construction ↑ Prerequisites: divisibility-rules
📏 Medium solution 💡 3 insights
Problem
Build the smallest positive whole number whose digits are only 4's and 9's (using at least one 4 and at least one 9) that is a multiple of both 4 and 9, then report its last four digits.

Pick an answer.

(A)
4444
(B)
4494
(C)
4944
(D)
9444
(E)
9944

AMC 10 2007 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve
Strategy Extreme Principle

The two divisibility rules act as filters that lock down the number's shape, and the word 'smallest' is a minimize signal, so the plan is: use the divisibility-by-4 rule to eliminate every ending except one, name the counts of each digit with a variable to force the divisibility-by-9 rule, then push toward the fewest digits and the smallest arrangement.

1STEP 1

Divisibility by 4 fixes the ending

Only the last two digits matter for 4, and among 44, 49, 94, 99 just 44 is a multiple of 4, so the number ends there.

44 = 4 × 11, 49, 94, 99 not divisible by 4
2STEP 2

Divisibility by 9 forces nine 4's

With a fours and b nines the digit sum is 4a + 9b; 9b is already a multiple of 9, so a must be a multiple of 9.

digit sum = 4a + 9b, 9 ∣ 4a ⇔ 9 ∣ a
3STEP 3

Fewest digits: nine 4's and one 9

Fewest digits wins, and the minimum allowed is nine 4's plus one 9 — a ten-digit number; nothing shorter can work.

a = 9, b = 1 → 10 digits
4STEP 4

Arrange for the smallest value

Push the lone 9 as far right as the 44 ending allows: n = 4444444944, whose last four digits are 4944, choice (C).

n = 4444444944, last four digits = 4944
Answer
4944
Check the winner 4444444944 directly: the last two digits are 44 = 4 x 11, so it is divisible by 4; the digit sum is nine 4's plus one 9 = 36 + 9 = 45 = 9 x 5, so it is divisible by 9; it uses both digits and has ten digits, the fewest possible. Its last four digits 4944 match (C). Choice (B) 4494 ends in 94, which is not divisible by 4, so it could never be the ending — a quick sanity check that the divisibility filter is doing real work.
💡Key takeaway

Let the divisibility rules pin down the shape of the number, then make it small by using as few digits as you can and hiding any big digit on the right.

  • Divisibility by 4 fixes the ending
  • Divisibility by 9 forces nine 4's
  • Fewest digits: nine 4's and one 9
  • Arrange for the smallest value

More like this

Same archetype — closest grade level first.