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 == | ||
− | {{ | + | 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 16:35, 19 June 2008
Problem
The numbers and 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 and are considered to be consecutive, are written on faces that share an edge is where and are relatively prime positive integers. Find
Solution
Choose one face of the octahedron randomly and label it with . 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 , since these faces are all adjacent to . There are thus 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 and . 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 possibilities for the 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 possibilities. There are permutations of each, so acceptable ways to fill in the rest of the octahedron given the . There are ways to randomly fill in the rest of the octahedron. So the probability is . The answer is .
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 |