# Difference between revisions of "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}$.