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

For simplicity, let us call the engraved side of a coin the heads side and the other side the tails side. Two adjacent coins in a vertical stack are face to face when their heads are touching, meaning that the bottom coin is heads up and the top coin is heads down. This means that, in order to ensure that no two adjacent coins are face to face, when one coin is heads up, the coin above it must be heads up as well. However, this means that the coin above THAT must ALSO be heads up (by the same reasoning). As a result, all the coins above the lowest head must be heads up, and so the only variable we have is the placement of the lowest head, which could be anywhere from the bottom coin to the top coin- 8 possible locations. We could also have no heads at all, which would obviously prevent coins from being face to face. Thus there are possible ways to arrange the eight coins strictly by their heads-tails orientation. However, we haven't yet fully solved the problem- with our above "answer" of 9, we assumed that all eight coins were identical, but they are not- four of the coins are gold, and four of the coins are silver. Thus, we must also take into consideration the number of different ways in which we can order the eight coins by color. This is simple- we can reduce the problem to finding the number of orderings of the "word" GGGGSSSS, which is simply . Thus, our final answer is .