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"

(→‎Solution)
(→‎Solution 8)
 
(36 intermediate revisions by 18 users not shown)
Line 1: Line 1:
 +
__TOC__
 +
 
== 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 brobability 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 off 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 denominator?
 +
 
 +
== Solution 1 ==
 +
We can use [[complementary counting]], by finding the probability that none of the three knights are sitting next to each other and subtracting it from <math>1</math>.
 +
 
 +
Imagine that 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 put <math>A</math>, followed by <math>21</math> places to put <math>B</math>, and <math>20</math> places to put <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 put <math>A</math>, followed by <math>23</math> places to put <math>B</math>, and <math>24</math> places to put <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 probability 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 ==
 +
There are <math>(25-1)! = 24!</math> configurations for the knights about the table (since configurations that are derived from each other simply by a rotation are really the same, and should not be counted multiple times).
 +
 
 +
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 in which order they are seated. Since these two knights must be together, 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 required probability is <math>\frac{2 \times 3 \times 23! - 6 \times 22!}{24!} = \frac{11}{46}</math>, and the answer is <math>\boxed{057}</math>.
 +
 
 +
== Solution 3 ==
 +
 
 +
Number the knights around the table from <math>1</math> to <math>25</math>. The total number of ways to pick the knights is <cmath>{25\choose 3} = \frac{25\cdot24\cdot23}{3\cdot2\cdot1} = 25\cdot23\cdot4</cmath>
 +
There are two possibilities: either 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 <math>(1,2,3)</math>, <math>(2,3,4)</math>, <math>(3,4,5)</math>, <math>(4,5,6)</math>, ...,<math>(23,24,25)</math>, <math>(24,25,1)</math>, <math>(25,1,2)</math>.  This makes <math>25</math> combinations.
 +
 
 +
Case 2:  Like above, there are <math>25</math> 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. (For example, if you pick <math>(5,6)</math>, you may not pick 4 or 7.) Thus, there are <math>25-4=21</math> ways to pick the third knight, for a total of <math>25\cdot21</math> combinations.
 +
 
 +
Thus, you have a total of <math>25 + (25\cdot21) = 25\cdot22</math> allowable ways to pick the knights.   
 +
 
 +
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 <math>2</math> possible places for this out of <math>24</math>, 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 apart from the first knight. There are <math>2</math> possible places for this out of <math>24</math>, so the probability is <math>\frac{1}{12}</math>. Then there are <math>3</math> places out of a remaining <math>23</math> 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 three or more spaces apart from the first knight. There are <math>20</math> possible places for this out of <math>24</math>, so the probability is <math>\frac{5}{6}</math>. Then there are <math>4</math> places to put the last knight out of <math>23</math>, so the total probability for this case is <math>\frac{5}{6}\times\frac{4}{23}</math>.
 +
 
 +
Now we 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}</cmath> so the answer is <math>\boxed{057}</math>.
 +
 
 +
== Solution 5 ==
 +
 
 +
We simplify this problem by using complementary counting and fixing one knight in place. Then, either a knight can sit two spaces apart from the fixed knight, or a knight can sit more than two spaces apart from the fixed knight. The probability is then <math>\frac{24\left(23\right)-\left[2\left(20\right)+20\left(19\right)\right]}{24\left(23\right)}=\frac{11}{46}</math>, so the answer is <math>11+46=\boxed{057}</math>.
 +
 
 +
== Solution 6 (stars and bars) ==
 +
Let <math>K_1, K_2, K_3</math> be the knights in clockwise order. Let <math>A</math> be the distance between <math>K_1</math> and <math>K_2</math>, <math>B</math> the distance between <math>K_2</math> and <math>K_3</math> and <math>C</math> the distance between <math>K_3</math> and <math>K_1</math>. <math>A + B + C = 25</math> and <math>A, B, C \geq 1</math>. In order to use stars and bars the numbers must be greater than or equal to 0 instead of 1, so we define <math>A_1 = A - 1, B_1 = B - 1, C_1 = C - 1</math>. <math>A_1 + B_1 + C_1 = 22</math>, so by stars and bars there are <math>\binom{22 + 3 - 1}{3 - 1} = 276</math> possibilities.
 +
 
 +
The condition is not satisfied if <math>A, B, C \geq 2</math>, so we can use complementary counting. Let <math>A_2 = A - 2, B_2 = B - 2, C_2 = C - 2</math>. <math>A_2 + B_2 + C_2 = 19</math>, and by stars and bars there are <math>\binom{19 + 3 - 1}{3 - 1} = 210</math> possibilities. This means there are <math>276 - 210 = 66</math> possibilities where the condition is satisfied, so the probability is <math>\frac{11}{46}</math>, resulting in <math>\boxed{057}</math>.
 +
 
 +
==Solution 7==
 +
 
 +
There are <math>\binom{25}{3}=\frac{25 \cdot 24 \cdot 23}{3 \cdot 2}=2300</math> ways to chose <math>3</math> knights out of <math>25</math> knights.
 +
 
 +
To ensure at least <math>2</math> adjacent knights are chosen, first choose <math>1</math> of the <math>25</math> pairs of adjacent knights. After choosing the adjacent pair of knights, there are <math>23</math> ways to choose the third knight. There are <math>25</math> choices of <math>3</math> knights sitting consecutively, which are counted twice. For example, choosing <math>(1,2)</math> first, then choosing <math>3</math> is the same as choosing <math>(2,3)</math> first, then choosing <math>1</math>. Therefore, there are <math>25 \cdot 23 -25=550</math> ways to choose <math>3</math> knights where at least <math>2</math> of the <math>3</math> had been sitting next to each other.
 +
<cmath>P=\frac{550}{2300}=\frac{11}{46}</cmath>
 +
The answer is <math>11+46=\boxed{\textbf{057}}</math>
 +
 
 +
~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen]
 +
 
 +
==Solution 8==
 +
(I need to get this out)
 +
 
 +
There are two possible scenarios satisfying this condition, one where two knights sit next to each other, while the third knight is lonely, and the other is where all three knights sit next to each other. On the numerator will be the total number of ways to position the knights, and on the denominator will be the number of ways to choose three knights.
 +
 
 +
Denominator: <math>\binom{25}{3}</math> ways to choose three knights
 +
 
 +
Numerator:
  
−
== Solution ==
+
<math>\implies</math> <math>Case_1:</math> Two knights are next to each other, third is lonely :(
−
We can also find the [[probability]] that none of them are sitting together, and subtract from 1. There are 2 cases:
 
  
−
# They are all separated by at least 2 seats.
+
<math>25</math> ways to situate two knights, <math>21</math> ways for third knight
−
# One of them is separated from one of the others by 1 seat.
 
  
−
In case (1), the probability is <math>\frac{25}{25} \cdot \frac{20}{24} \cdot \frac{19}{23} =\frac{380}{552}</math>.
 
  
−
But what if they're only separated by 1 seat? In that case, the probability is <math>\frac{25}{25} \cdot \frac{2}{24} \cdot \frac{20}{23}=\frac{40}{552}</math>.
+
<math>\implies</math> <math>Case_2:</math> All three knights are next to each other
  
−
The total probability is <math>\frac{420}{552}=\frac{35}{46}</math>, so our answer is <math>1-\frac{35}{46}=\frac{11}{46}</math>.
+
<math>25</math> ways
  
−
----
+
So, we have <math>P = \frac{21 \cdot 25+25}{\binom{25}{3}}</math>
 +
<math>= \frac{22 \cdot 25 \cdot 6}{25 \cdot 24 \cdot 3}</math>
 +
<math>= \frac{11}{46}</math>, and our answer is <math>11+46=\boxed{057}</math>
  
−
* [[1983 AIME Problems/Problem 6|Previous Problem]]
+
~[https://artofproblemsolving.com/wiki/index.php/User:mineric mineric] (formatted shalomkeshet)
−
* [[1983 AIME Problems/Problem 8|Next Problem]]
 
−
* [[1983 AIME Problems|Back to Exam]]
 
  
−
== See also ==
+
== See Also ==
−
* [[AIME Problems and Solutions]]
+
{{AIME box|year=1983|num-b=6|num-a=8}}
−
* [[American Invitational Mathematics Examination]]
 
−
* [[Mathematics competition resources]]
 
  
 
[[Category:Intermediate Combinatorics Problems]]
 
[[Category:Intermediate Combinatorics Problems]]

Latest revision as of 10:50, 30 October 2024

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 off 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 denominator?

Solution 1

We can use complementary counting, by finding the probability that none of the three knights are sitting next to each other and subtracting it from $1$.

Imagine that 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 put $A$, followed by $21$ places to put $B$, and $20$ places to put $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 put $A$, followed by $23$ places to put $B$, and $24$ places to put $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 probability 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 (since configurations that are derived from each other simply by a rotation are really the same, and should not be counted multiple times).

There are ${3\choose 2} = 3$ ways to pick a pair of knights from the trio, and there are $2! = 2$ ways to determine in which order they are seated. Since these two knights must be together, 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 required probability 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 from $1$ to $25$. The total number of ways to pick the knights is \[{25\choose 3} = \frac{25\cdot24\cdot23}{3\cdot2\cdot1} = 25\cdot23\cdot4\] There are two possibilities: either 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)$, $(3,4,5)$, $(4,5,6)$, ...,$(23,24,25)$, $(24,25,1)$, $(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. (For example, 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 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 apart 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 three or more spaces apart from the first knight. There are $20$ possible places for this out of $24$, so the probability is $\frac{5}{6}$. Then there are $4$ places to put the last knight out of $23$, so the total probability for this case is $\frac{5}{6}\times\frac{4}{23}$.

Now we 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}\] so the answer is $\boxed{057}$.

Solution 5

We simplify this problem by using complementary counting and fixing one knight in place. Then, either a knight can sit two spaces apart from the fixed knight, or a knight can sit more than two spaces apart from the fixed knight. The probability is then $\frac{24\left(23\right)-\left[2\left(20\right)+20\left(19\right)\right]}{24\left(23\right)}=\frac{11}{46}$, so the answer is $11+46=\boxed{057}$.

Solution 6 (stars and bars)

Let $K_1, K_2, K_3$ be the knights in clockwise order. Let $A$ be the distance between $K_1$ and $K_2$, $B$ the distance between $K_2$ and $K_3$ and $C$ the distance between $K_3$ and $K_1$. $A + B + C = 25$ and $A, B, C \geq 1$. In order to use stars and bars the numbers must be greater than or equal to 0 instead of 1, so we define $A_1 = A - 1, B_1 = B - 1, C_1 = C - 1$. $A_1 + B_1 + C_1 = 22$, so by stars and bars there are $\binom{22 + 3 - 1}{3 - 1} = 276$ possibilities.

The condition is not satisfied if $A, B, C \geq 2$, so we can use complementary counting. Let $A_2 = A - 2, B_2 = B - 2, C_2 = C - 2$. $A_2 + B_2 + C_2 = 19$, and by stars and bars there are $\binom{19 + 3 - 1}{3 - 1} = 210$ possibilities. This means there are $276 - 210 = 66$ possibilities where the condition is satisfied, so the probability is $\frac{11}{46}$, resulting in $\boxed{057}$.

Solution 7

There are $\binom{25}{3}=\frac{25 \cdot 24 \cdot 23}{3 \cdot 2}=2300$ ways to chose $3$ knights out of $25$ knights.

To ensure at least $2$ adjacent knights are chosen, first choose $1$ of the $25$ pairs of adjacent knights. After choosing the adjacent pair of knights, there are $23$ ways to choose the third knight. There are $25$ choices of $3$ knights sitting consecutively, which are counted twice. For example, choosing $(1,2)$ first, then choosing $3$ is the same as choosing $(2,3)$ first, then choosing $1$. Therefore, there are $25 \cdot 23 -25=550$ ways to choose $3$ knights where at least $2$ of the $3$ had been sitting next to each other. \[P=\frac{550}{2300}=\frac{11}{46}\] The answer is $11+46=\boxed{\textbf{057}}$

~isabelchen

Solution 8

(I need to get this out)

There are two possible scenarios satisfying this condition, one where two knights sit next to each other, while the third knight is lonely, and the other is where all three knights sit next to each other. On the numerator will be the total number of ways to position the knights, and on the denominator will be the number of ways to choose three knights.

Denominator: $\binom{25}{3}$ ways to choose three knights

Numerator:

$\implies$ $Case_1:$ Two knights are next to each other, third is lonely :(

$25$ ways to situate two knights, $21$ ways for third knight


$\implies$ $Case_2:$ All three knights are next to each other

$25$ ways

So, we have $P = \frac{21 \cdot 25+25}{\binom{25}{3}}$ $= \frac{22 \cdot 25 \cdot 6}{25 \cdot 24 \cdot 3}$ $= \frac{11}{46}$, and our answer is $11+46=\boxed{057}$

~mineric (formatted shalomkeshet)

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=230979"