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
Small Hint:

Handle orientations and colors separately. Record each coin’s orientation, bottom to top, as UU (face up) or DD (face down).

Big Hint:

Face to face happens exactly when a UU sits directly below a D,D, so all the DD’s must come before all the UU’s

Solution:

Choose the coin orientations and the gold/silver positions independently. Record the orientations from bottom to top as a string of UU (engraved face up) and DD (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 UU is immediately followed by a D.D.

A string of UU’s and DD’s avoids the pattern UDUD exactly when every DD precedes every U,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