2009 AIME I Problem 9

Below is the professionally curated solution for Problem 9 of the 2009 AIME I, 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 of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:multiset permutationspartitions and compositionsmultiplication principle

Difficulty rating: 2600

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.

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 8Full ExamProblem 10

Problem 9 in Other Years