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 "2001 AIME I Problems/Problem 15"

m
(solution by E^(pi*i)=-1)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
The numbers 1, 2, 3, 4, 5, 6, 7, and 8 are randomly written on the faces of a regular octahedron so that each face contains a different number.  The probability that no two consecutive numbers, where 8 and 1 are considered to be consecutive, are written on faces that share an edge is <math>m/n,</math> where <math>m</math> and <math>n</math> are relatively prime positive integers.  Find <math>m + n.</math>
+
The numbers <math>1, 2, 3, 4, 5, 6, 7,</math> and <math>8</math> are randomly written on the faces of a regular [[octahedron]] so that each face contains a different number.  The [[probability]] that no two consecutive numbers, where <math>8</math> and <math>1</math> are considered to be consecutive, are written on faces that share an edge is <math>m/n,</math> where <math>m</math> and <math>n</math> are relatively prime positive integers.  Find <math>m + n.</math>
  
 
== Solution ==
 
== Solution ==
−
{{solution}}
+
Choose one face of the octahedron randomly and label it with <math>1</math>.  There are three faces adjacent to this one, which we will call A-faces.  There are three faces adjacent to two of the A-faces, which we will call B-faces, and one face adjacent to the three B-faces, which we will call the C-face.
 +
 
 +
Clearly, the labels for the A-faces must come from the set <math>\{3,4,5,6,7\}</math>, since these faces are all adjacent to <math>1</math>.  There are thus <math>5 \cdot 4 \cdot 3 = 60</math> ways to assign the labels for the A-faces. 
 +
 
 +
The labels for the B-faces and C-face are the two remaining numbers from the above set, plus <math>2</math> and <math>8</math>.  The number on the C-face must not be adjacent to any of the numbers on the B-faces. 
 +
 
 +
From here it is easiest to brute force the <math>10</math> possibilities for the <math>4</math> numbers left.
 +
 
 +
*2348 (2678): 8(2) is the only one not adjacent to any of the others, so it goes on the C-face.  4(6) has only one B-face it can go to, while 2 and 3 (7 and 8) can be assigned randomly to the last two.  2 possibilities here.
 +
 
 +
*2358 (2578): 5 cannot go on any of the B-faces, so it must be on the C-face.  3 and 8 (2 and 7) have only one allowable B-face, so just 1 possibility here.
 +
 
 +
*2368 (2478): 6(4) cannot go on any of the B-faces, so it must be on the C-face.  3 and 8 (2 and 7) have only one allowable B-face, so 1 possibility here.
 +
 
 +
*2458 (2568): All of the numbers have only one B-face they could go to.  2 and 4 (6 and 8) can go on the same, so one must go to the C-face.  Only 2(8) is not consecutive with any of the others, so it goes on the C-face.  1 possibility.
 +
 
 +
*2378: None of the numbers can go on the C-face because they will be consecutive with one of the B-face numbers.  So this possibility is impossible.
 +
 
 +
*2468: Both 4 and 6 cannot go on any B-face.  They cannot both go on the C-face, so this possibility is impossible.
 +
 
 +
There is a total of <math>10</math> possibilities.  There are <math>3!=6</math> permutations of each, so <math>60</math> acceptable ways to fill in the rest of the octahedron given the <math>1</math>.  There are <math>7!=5040</math> ways to randomly fill in the rest of the octahedron.  So the probability is <math>\frac {60}{5040} = \frac {1}{84}</math>. The answer is <math>\boxed{085}</math>.
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2001|n=I|num-b=14|after=Last Question}}
 
{{AIME box|year=2001|n=I|num-b=14|after=Last Question}}
 +
 +
[[Category:Intermediate Combinatorics Problems]]

Revision as of 17:35, 19 June 2008

Problem

The numbers $1, 2, 3, 4, 5, 6, 7,$ and $8$ are randomly written on the faces of a regular octahedron so that each face contains a different number. The probability that no two consecutive numbers, where $8$ and $1$ are considered to be consecutive, are written on faces that share an edge is $m/n,$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

Solution

Choose one face of the octahedron randomly and label it with $1$. There are three faces adjacent to this one, which we will call A-faces. There are three faces adjacent to two of the A-faces, which we will call B-faces, and one face adjacent to the three B-faces, which we will call the C-face.

Clearly, the labels for the A-faces must come from the set $\{3,4,5,6,7\}$, since these faces are all adjacent to $1$. There are thus $5 \cdot 4 \cdot 3 = 60$ ways to assign the labels for the A-faces.

The labels for the B-faces and C-face are the two remaining numbers from the above set, plus $2$ and $8$. The number on the C-face must not be adjacent to any of the numbers on the B-faces.

From here it is easiest to brute force the $10$ possibilities for the $4$ numbers left.

  • 2348 (2678): 8(2) is the only one not adjacent to any of the others, so it goes on the C-face. 4(6) has only one B-face it can go to, while 2 and 3 (7 and 8) can be assigned randomly to the last two. 2 possibilities here.
  • 2358 (2578): 5 cannot go on any of the B-faces, so it must be on the C-face. 3 and 8 (2 and 7) have only one allowable B-face, so just 1 possibility here.
  • 2368 (2478): 6(4) cannot go on any of the B-faces, so it must be on the C-face. 3 and 8 (2 and 7) have only one allowable B-face, so 1 possibility here.
  • 2458 (2568): All of the numbers have only one B-face they could go to. 2 and 4 (6 and 8) can go on the same, so one must go to the C-face. Only 2(8) is not consecutive with any of the others, so it goes on the C-face. 1 possibility.
  • 2378: None of the numbers can go on the C-face because they will be consecutive with one of the B-face numbers. So this possibility is impossible.
  • 2468: Both 4 and 6 cannot go on any B-face. They cannot both go on the C-face, so this possibility is impossible.

There is a total of $10$ possibilities. There are $3!=6$ permutations of each, so $60$ acceptable ways to fill in the rest of the octahedron given the $1$. There are $7!=5040$ ways to randomly fill in the rest of the octahedron. So the probability is $\frac {60}{5040} = \frac {1}{84}$. The answer is $\boxed{085}$.

See also

2001 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 14 		Followed by
Last Question
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=2001_AIME_I_Problems/Problem_15&oldid=26678"