2005 AIME I Problem 5

Below is the professionally curated solution for Problem 5 of the 2005 AIME I, from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2005 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:arrangements with restrictionscombinationsmultiplication principle

Difficulty rating: 2300

5.

Robert has 44 indistinguishable gold coins and 44 indistinguishable silver coins. Each coin has an engraving of a face on one side, but not on the other. He wants to stack the eight coins on a table into a single stack so that no two adjacent coins are face to face. Find the number of possible distinguishable arrangements of the 88 coins.

Solution:

Choose the coin orientations and the gold/silver positions independently. Record the orientations from bottom to top as a string of U (engraved face up) and D (engraved face down). Two adjacent coins are face to face exactly when the lower coin's engraved side faces up and the upper coin's engraved side faces down — that is, exactly when a U is immediately followed by a D.

A string of U's and D's avoids the pattern UD exactly when every D precedes every U, so the string is DiU8i\text{D}^i\text{U}^{8-i} for some i=0,1,,8:i = 0, 1, \ldots, 8: there are 99 allowable orientation strings. Independently, the gold coins occupy 44 of the 88 positions in (84)=70\binom{8}{4} = 70 ways.

The total is 970=630.9 \cdot 70 = 630.

← Problem 4Full ExamProblem 6

Problem 5 in Other Years