Difference between revisions of "1983 AIME Problems/Problem 7"
(→Solution) |
(agreed; delete solution, + direct counting) |
||
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
| − | Twenty five of King Arthur's knights are seated at their customary round table. Three of them are chosen - all choices being equally likely - and are sent of to slay a troublesome dragon. Let <math>P</math> be the probability that at least two of the three had been sitting next to each other. If <math>P</math> is written as a fraction in lowest terms, what is the sum of the numerator and the denominator? | + | Twenty five of King Arthur's knights are seated at their customary round table. Three of them are chosen - all choices being equally likely - and are sent of to slay a troublesome dragon. Let <math>P</math> be the [[probability]] that at least two of the three had been sitting next to each other. If <math>P</math> is written as a fraction in lowest terms, what is the sum of the numerator and the denominator? |
| + | __TOC__ | ||
== Solution == | == Solution == | ||
| − | We can | + | === Solution 1 === |
| + | We can apply the [[complement principle]], by finding the probability that none are sitting next to each other, and subtractring from <math>1</math>. | ||
| − | + | Imagine the <math>22</math> other (indistinguishable) people are already seated, and fixed into place. | |
| − | |||
| − | + | We will place <math>A</math>, <math>B</math>, and <math>C</math> with and without the restriction. | |
| − | + | There are <math>22</math> places to place <math>A</math>, followed by <math>21</math> places to place <math>B</math>, and <math>20</math> places to place <math>C</math> after <math>A</math> and <math>B</math>. Hence, there are <math>22\cdot21\cdot20</math> ways to place <math>A, B, C</math> in between these people with restrictions. | |
| − | + | Without restrictions, there are <math>22</math> places to palce <math>A</math>, followed by <math>23</math> places to place <math>B</math>, and <math>24</math> places to place <math>C</math> after <math>A</math> and <math>B</math>. Hence, there are <math>22\cdot23\cdot24</math> ways to place <math>A,B,C</math> in between these people without restrictions. | |
| − | |||
| − | + | Thus, the desired amount is <math>1-\frac{22\cdot21\cdot20}{22\cdot23\cdot24}=1-\frac{420}{552}=1-\frac{35}{46}=\frac{11}{46}</math>, and the answer is <math>11+46=\boxed{057}</math>. | |
| − | ==Solution 2 ( | + | === Solution 2 === |
| + | There are <math>(25-1)! = 24!</math> configurations for the knights about the table. | ||
| − | + | There are <math>{3\choose 2} = 3</math> ways to pick a pair of knights from the trio, and there are <math>2! = 2</math> ways to determine which order they are seated. Since these two knights must be attached, we let them be a single entity, so there are <math>(24-1)! = 23!</math> configurations for the entities. | |
| − | + | However, this [[Principle of Inclusion-Exclusion|overcounts]] the instances in which the trio sits together; when all three knights sit together, then two of the pairs from the previous case are counted. However, we only want to count this as one case, so we need to subtract the number of instances in which the trio sits together (as a single entity). There are <math>3! = 6</math> ways to determine their order, and there are <math>(23-1)! = 22!</math> configurations. | |
| − | + | Thus, the answer is <math>\frac{2 \times 3 \times 23! - 6 \times 22!}{24!} = \frac{11}{46}</math>, and the answer is <math>\boxed{057}</math>. | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== See also == | == See also == | ||
{{AIME box|year=1983|num-b=6|num-a=8}} | {{AIME box|year=1983|num-b=6|num-a=8}} | ||
| − | |||
| − | |||
| − | |||
[[Category:Intermediate Combinatorics Problems]] | [[Category:Intermediate Combinatorics Problems]] | ||
Revision as of 15:31, 22 November 2008
Problem
Twenty five of King Arthur's knights are seated at their customary round table. Three of them are chosen - all choices being equally likely - and are sent of to slay a troublesome dragon. Let 
be the probability that at least two of the three had been sitting next to each other. If is written as a fraction in lowest terms, what is the sum of the numerator and the denominator?
Solution
Solution 1
We can apply the complement principle, by finding the probability that none are sitting next to each other, and subtractring from 
.
Imagine the 
other (indistinguishable) people are already seated, and fixed into place.
We will place 
, 
, and 
with and without the restriction.
There are places to place , followed by 
places to place , and 
places to place after and . Hence, there are 
ways to place 
in between these people with restrictions.
Without restrictions, there are places to palce , followed by 
places to place , and 
places to place after and . Hence, there are 
ways to place 
in between these people without restrictions.
Thus, the desired amount is 
, and the answer is 
.
Solution 2
There are 
configurations for the knights about the table.
There are 
ways to pick a pair of knights from the trio, and there are 
ways to determine which order they are seated. Since these two knights must be attached, we let them be a single entity, so there are 
configurations for the entities.
However, this overcounts the instances in which the trio sits together; when all three knights sit together, then two of the pairs from the previous case are counted. However, we only want to count this as one case, so we need to subtract the number of instances in which the trio sits together (as a single entity). There are 
ways to determine their order, and there are 
configurations.
Thus, the answer is 
, and the answer is 
.
See also
| 1983 AIME (Problems • Answer Key • Resources) | ||
| Preceded by Problem 6 |
Followed by Problem 8 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
| All AIME Problems and Solutions | ||
