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 07:45, 1 July 2019
Contents
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 
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 
total configurations. Thus, the answer is 
.
Solution 2
We can imagine the 
coins as a string of 
and 
. Because no 
adjacent coins can have faces touching, subsequent to changing from 
to 
, the numbers following must be ; therefore, the number of possible permutations if all the coins are indistinguishable is (there are possible places to change from to and there is the possibility that there no change occurs). There are 
possibilities of what coins are gold and what coins are silver, so the solution is 
.
See also
| 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 | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
