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 "University of South Carolina High School Math Contest/1993 Exam/Problem 19"
(→‎Solution)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
 
In the figure below, there are 4 distinct dots <math>A, B, C,</math> and <math>D</math>, joined by edges.  Each dot is to be colored either red, blue, green, or yellow.  No two dots joined by an edge are to be colored with the same color.  How many completed colorings are possible?
 
In the figure below, there are 4 distinct dots <math>A, B, C,</math> and <math>D</math>, joined by edges.  Each dot is to be colored either red, blue, green, or yellow.  No two dots joined by an edge are to be colored with the same color.  How many completed colorings are possible?
−
{{image}}
+
 
 +
<center>[[Image:Usc93.19.PNG]]</center>
  
 
<center><math> \mathrm{(A) \ }24 \qquad \mathrm{(B) \ }72 \qquad \mathrm{(C) \ }84 \qquad \mathrm{(D) \ }96 \qquad \mathrm{(E) \ }108  </math></center>
 
<center><math> \mathrm{(A) \ }24 \qquad \mathrm{(B) \ }72 \qquad \mathrm{(C) \ }84 \qquad \mathrm{(D) \ }96 \qquad \mathrm{(E) \ }108  </math></center>
  
 
== Solution ==
 
== Solution ==
−
We look at the number of possibilities by considering each dot. If we start with <math>A</math>, there are <math>4</math> distinct colors for it. Then, there are <math>3!</math> ways to color the other three dots since they are all distinct. Thus, the number of ways to color the graph is <math>3! \cdot 4 \cdot 4=96</math>. However, <math>A,B,C,D</math> are distinct, or in other words, the graphs must be distinct which can occur one way for each pair of starting dots we choose. Thus, the total number is <math>96-{4\choose 2}=84</math>.
+
There are 4 color choices for dot <math>A</math>. After coloring dot <math>A</math>, there are 3 color choices for dot <math>B</math>.   If dot <math>D</math> is the same color as dot <math>B</math> (1 way), there are 3 choices for dot <math>C</math>. If dot <math>D</math> is a different color from dot <math>B</math> (2 ways), there are only 2 choices for dot <math>C</math>. Thus we have in total <math>4\cdot3\cdot(1\cdot3 + 2\cdot2) = 84</math> possible colorings, so choice <math>\mathrm{(C)}</math> is the answer.  
  
 
----
 
----
Line 15: Line 16:
  
  
−
[[Category:Intermediate Combinatorics Problems]]
+
[[Category:Introductory Combinatorics Problems]]

Latest revision as of 16:37, 17 August 2006

Problem

In the figure below, there are 4 distinct dots $A, B, C,$ and $D$, joined by edges. Each dot is to be colored either red, blue, green, or yellow. No two dots joined by an edge are to be colored with the same color. How many completed colorings are possible?

Usc93.19.PNG
$\mathrm{(A) \ }24 \qquad \mathrm{(B) \ }72 \qquad \mathrm{(C) \ }84 \qquad \mathrm{(D) \ }96 \qquad \mathrm{(E) \ }108$

Solution

There are 4 color choices for dot $A$. After coloring dot $A$, there are 3 color choices for dot $B$. If dot $D$ is the same color as dot $B$ (1 way), there are 3 choices for dot $C$. If dot $D$ is a different color from dot $B$ (2 ways), there are only 2 choices for dot $C$. Thus we have in total $4\cdot3\cdot(1\cdot3 + 2\cdot2) = 84$ possible colorings, so choice $\mathrm{(C)}$ is the answer.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=University_of_South_Carolina_High_School_Math_Contest/1993_Exam/Problem_19&oldid=9629"