2005 AIME I Problems/Problem 5

Problem

Robert has 4 indistinguishable gold coins and 4 indistinguishable silver coins. Each coin has an engraving of one 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 8 coins.

Solution 1

There are two separate parts to this problem: one is the color (gold vs silver), and the other is the orientation.

There are ${8\choose4} = 70$ ways to position the gold coins in the stack of 8 coins, which determines the positions of the silver coins.

Create a string of letters H and T to denote the orientation of the top of the coin. To avoid making two faces touch, we cannot have the arrangement HT. Thus, all possible configurations must be a string of tails followed by a string of heads, since after the first H no more tails can appear. The first H can occur in a maximum of eight times different positions, and then there is also the possibility that it doesn’t occur at all, for $9$ total configurations. Thus, the answer is $70 \cdot 9 = \boxed{630}$ .

Solution 2

We can imagine the $8$ coins as a string of $0\text{'s}$ and $1\text{'s}$ . Because no $2$ adjacent coins can have $2$ faces touching, subsequent to changing from $0$ to $1$ , the numbers following $1$ must be $1\text{'s}$ ; therefore, the number of possible permutations if all the coins are indistinguishable is $9$ (there are $8$ possible places to change from $0$ to $1$ and there is the possibility that there no change occurs). There are $\binom 8 4$ possibilities of what coins are gold and what coins are silver, so the solution is $\boxed{9\cdot \binom 8 4=630}$ .

Solution 3

First, we can break this problem up into two parts: the amount of ways to order the coins based on color, and which side is facing up for each coin (assuming they are indistinguishable). I’m the end, we multiply these values together.

First, there are obviously $\binom{8}{5}$ ways to order the coins based on color.

Next, we set up a recurrence. Let $a_n$ be the number of ways $n$ indistinguishable coins to be stacked such that no heads are facing each other.

Consider the top coin. If it is facing up, then there are $a_{n-1}$ ways for the rest of the coins below it to be arranged. If it is facing down however, there will only be one way to arrange the coins. We can the recurrence: $a_n=a_{n-1}+1.$ Note $a_1=2$ , so $a_8 = 9$ .

Finally, to get the result, we do $70\times 9$ to get $\boxed{630}$ .

~superagh

2005 AIME I (Problems • Answer Key • Resources)
Preceded by Problem 4	Followed by Problem 6
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search

2005 AIME I Problems/Problem 5

Contents

Problem

Solution 1

Solution 2

Solution 3

See also