Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎Solution)
(Undo revision 40320 by Hli (talk))
Line 3: Line 3:
  
 
== Solution ==
 
== 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 <math>8+1=9</math> possible ways to arrange the eight coins strictly by their heads-tails orientation.
+
There are two separate parts to this problem: one is the color (gold vs silver), and the other is the 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 <math>7*90=\boxed{630}</math>.
 
  
 +
There are <math>{8\choose4} = 70</math> 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 <math>9</math> total configurations. Thus, the answer is <math>70 \cdot 9 = 630</math>.
 +
 
== See also ==
 
== See also ==
 
{{AIME box|year=2005|n=I|num-b=4|num-a=6}}
 
{{AIME box|year=2005|n=I|num-b=4|num-a=6}}
  
 
[[Category:Intermediate Combinatorics Problems]]
 
[[Category:Intermediate Combinatorics Problems]]

Revision as of 12:01, 9 July 2011

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

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 = 630$.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_AIME_I_Problems/Problem_5&oldid=40321"