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 "1983 AIME Problems/Problem 7"

m
(solution 4 added)
Line 37: Line 37:
  
 
The probability is <math>\frac{25\cdot22}{25\cdot23\cdot4} = \frac{11}{46}</math>, and the answer is <math>\boxed{057}</math>.
 
The probability is <math>\frac{25\cdot22}{25\cdot23\cdot4} = \frac{11}{46}</math>, and the answer is <math>\boxed{057}</math>.
 +
 +
=== Solution 4 ===
 +
 +
Pick an arbitrary spot for the first knight. Then pick spots for the next two knights in order.
 +
 +
Case 1: The second knight sits next to the first knight. There are 2 possible places for this out of 24, so the probability of this is <math>\frac{1}{12}</math>. We do not need to consider the third knight.
 +
 +
Case 2: The second knight sits two spaces from the first knight. There are 2 possible places for this out of 24, so the probability is <math>\frac{1}{12}</math>. Then there are 3 places out of a remaining 23 for the third knight to sit, so the total probability for this case is <math>\frac{1}{12} \times \frac{3}{23}</math>
 +
 +
Case 3: The second knight sits 3 or more spaces from the first knight. There are 20 possible places for this out of 24, so the probability is <math>\frac{5}{6}</math>. Then there are four places to put the last knight out of 23, so the total probability for this case is <math>\frac{5}{6}\times\frac{4}{23}</math>
 +
 +
So add the probabilities to get the total:
 +
 +
 +
<cmath>\frac{1}{12}+\frac{1}{12}\times\frac{3}{23}+\frac{5}{6}\times\frac{4}{23}=\frac{1}{12}\times\frac{1}{23}\left(23+3+40\right)=\frac{66}{12\times 23}</cmath>
 +
<cmath>=\frac{6\times 11}{6\times 2 \times 23}=\frac{11}{46}\to\boxed{057}</cmath>
 +
  
 
== See Also ==
 
== See Also ==

Revision as of 23:10, 23 February 2014

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 $P$ be the probability that at least two of the three had been sitting next to each other. If $P$ is written as a fraction in lowest terms, what is the sum of the numerator and the denominator?

Solution

Solution 1

We can use Complementary counting by finding the probability that none are sitting next to each other and subtracting it from $1$.

Imagine the $22$ other (indistinguishable) people are already seated, and fixed into place.

We will place $A$, $B$, and $C$ with and without the restriction.

There are $22$ places to place $A$, followed by $21$ places to place $B$, and $20$ places to place $C$ after $A$ and $B$. Hence, there are $22\cdot21\cdot20$ ways to place $A, B, C$ in between these people with restrictions.

Without restrictions, there are $22$ places to place $A$, followed by $23$ places to place $B$, and $24$ places to place $C$ after $A$ and $B$. Hence, there are $22\cdot23\cdot24$ ways to place $A,B,C$ in between these people without restrictions.

Thus, the desired amount is $1-\frac{22\cdot21\cdot20}{22\cdot23\cdot24}=1-\frac{420}{552}=1-\frac{35}{46}=\frac{11}{46}$, and the answer is $11+46=\boxed{057}$.

Solution 2

There are $(25-1)! = 24!$ configurations for the knights about the table.

There are ${3\choose 2} = 3$ ways to pick a pair of knights from the trio, and there are $2! = 2$ 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 $(24-1)! = 23!$ 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 $3! = 6$ ways to determine their order, and there are $(23-1)! = 22!$ configurations.

Thus, the answer is $\frac{2 \times 3 \times 23! - 6 \times 22!}{24!} = \frac{11}{46}$, and the answer is $\boxed{057}$.

Solution 3

Number the knights around the table 1-25. There are two possibilities: All three sit next to each other, or two sit next to each other and one is not sitting next to the other two.

Case 1: All three sit next to each other. In this case, you are picking $(1,2,3)$, $(2,3,4)$, $(4,5,6)$...$(25,1,2)$. This makes $25$ combinations.

Case 2: Like above, there are $25$ ways to pick the pair of knights sitting next to each other. Once a pair is picked, you cannot pick either of the two adjacent knights. (i.e. if you pick $(5,6)$, you may not pick 4 or 7). Thus, there are $25-4=21$ ways to pick the third knight, for a total of $25\cdot21$ combinations.

Thus, you have a total of $25 + (25\cdot21) = 25\cdot22$ allowable ways to pick the knights. The total number of ways to pick the knights is ${25\choose 3} = \frac{25\cdot24\cdot23}{3\cdot2\cdot1} = 25\cdot23\cdot4$.

The probability is $\frac{25\cdot22}{25\cdot23\cdot4} = \frac{11}{46}$, and the answer is $\boxed{057}$.

Solution 4

Pick an arbitrary spot for the first knight. Then pick spots for the next two knights in order.

Case 1: The second knight sits next to the first knight. There are 2 possible places for this out of 24, so the probability of this is $\frac{1}{12}$. We do not need to consider the third knight.

Case 2: The second knight sits two spaces from the first knight. There are 2 possible places for this out of 24, so the probability is $\frac{1}{12}$. Then there are 3 places out of a remaining 23 for the third knight to sit, so the total probability for this case is $\frac{1}{12} \times \frac{3}{23}$

Case 3: The second knight sits 3 or more spaces from the first knight. There are 20 possible places for this out of 24, so the probability is $\frac{5}{6}$. Then there are four places to put the last knight out of 23, so the total probability for this case is $\frac{5}{6}\times\frac{4}{23}$

So add the probabilities to get the total:


\[\frac{1}{12}+\frac{1}{12}\times\frac{3}{23}+\frac{5}{6}\times\frac{4}{23}=\frac{1}{12}\times\frac{1}{23}\left(23+3+40\right)=\frac{66}{12\times 23}\] \[=\frac{6\times 11}{6\times 2 \times 23}=\frac{11}{46}\to\boxed{057}\]


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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1983_AIME_Problems/Problem_7&oldid=60428"