2009 AIME I Problem 9

Attempt Problem 9 of the 2009 AIME I below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2009 AIME I solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

9.

A game show offers a contestant three prizes A, B and C, each of which is worth a whole number of dollars from $1\$1 to $9999\$9999 inclusive. The contestant wins the prizes by correctly guessing the price of each prize in the order A, B, C. As a hint, the digits of the three prices are given. On a particular day, the digits given were 1,1,1,1,3,3,3.1, 1, 1, 1, 3, 3, 3. Find the total number of possible guesses for all three prizes consistent with the hint.

Answer: 420
Concepts:multiset permutationspartitions and compositionsmultiplication principle
Difficulty rating: 2600
Solution:

Concatenating the three guessed prices in order produces an arrangement of the seven given digits, and each guess is recovered uniquely from an arrangement together with a way to cut it into three consecutive nonempty blocks of at most four digits each (prices run from $1\$1 to $9999,\$9999, and no price can start with 00 here since every digit is 11 or 33). There are 7!4!3!=35\frac{7!}{4!\,3!} = 35 arrangements of four 11s and three 33s.

The ordered block lengths are the ways to write 77 as an ordered sum of three parts between 11 and 4:4: the permutations of (1,2,4),(1, 2, 4), (2,2,3),(2, 2, 3), and (1,3,3),(1, 3, 3), giving 6+3+3=126 + 3 + 3 = 12 cuts for each arrangement.

The total is 3512=420.35 \cdot 12 = 420.

← Problem 8#8
Full Exam

Problem 9 in Other Years