Difference between revisions of "2005 AIME I Problems/Problem 5"

(Solution)
Line 2: Line 2:
 
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.
 
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 ==
+
== 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 two separate parts to this problem: one is the color (gold vs silver), and the other is the orientation.
  
Line 8: Line 8:
  
 
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 <math>9</math> total configurations. Thus, the answer is <math>70 \cdot 9 = \boxed{630}</math>.
 
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 <math>9</math> total configurations. Thus, the answer is <math>70 \cdot 9 = \boxed{630}</math>.
 +
 +
== Solution 2 ==
 +
We can imagine the <math>8</math> coins as a string of <math>0\text{'s}</math> and <math>1\text{'s}</math>. Because no <math>2</math> adjacent coins can have <math>2</math> faces touching, subsequent to changing from <math>0</math> to <math>1</math>, the numbers following <math>1</math> must be <math>1\text{'s}</math>; therefore, the number of possible permutations if all the coins are indistinguishable is <math>9</math> (there are <math>8</math> possible places to change from <math>0</math> to <math>1</math> and there is the possibility that there no change occurs). There are <math>\binom 8 4</math> possibilities of what coins are gold and what coins are silver, so the solution is <math>\boxed{9\cdot \binom 8 4=630}</math>.
  
 
== See also ==
 
== See also ==

Revision as of 06:45, 1 July 2019

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}$.

See also

2005 AIME I (ProblemsAnswer KeyResources)
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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png