2005 AIME I Problem 5

Attempt Problem 5 of the 2005 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 2005 AIME I solutions, or check the answer key.

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

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.

Answer: 630
Concepts:arrangements with restrictionscombinationsmultiplication principle
Difficulty rating: 2300
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 4#4
Full Exam

Problem 5 in Other Years