3
$\begingroup$

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. What is P?

I calculated by complement method. But I got it wrong. The total number of ways to select $3$ out of $25$ knights is $C(25,3)$.

Now 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)/3!$ ways to place $A, B, C$ in between these people with restrictions.

If I calculate the probability the answer does not match, what am I getting wrong?

$\endgroup$
  • $\begingroup$ Can you please elaborate a bit in your third paragraph (line by line)? Then it becomes easier to see what went wrong where. $\endgroup$ – Imago Jan 19 '19 at 12:32
  • 2
    $\begingroup$ @Imago Imagine placing $22$ chairs around the table. To ensure that no two of the three selected people are adjacent, Rituraj chose them by placing the three selected people in three of the $22$ gaps to the immediate right of those chairs (those chairs represent the positions where the knights who are not selected for the mission sit), giving an answer of $$1 - \frac{\binom{22}{3}}{\binom{25}{3}}$$ $\endgroup$ – N. F. Taussig Jan 19 '19 at 12:35
  • $\begingroup$ I found the solution here artofproblemsolving.com/wiki/index.php/1983_AIME_Problems/… )but i found the total restricted counts by method of solution 1 and total unrestricted counts by method of soution 3. The final answer should be same but it does not come so $\endgroup$ – Rituraj Tripathy Jan 19 '19 at 12:39
  • $\begingroup$ Yes but i get the answer wrong. Please help me out. $\endgroup$ – Rituraj Tripathy Jan 19 '19 at 12:42
  • 1
    $\begingroup$ @N.F.Taussig That needs to be $1-\frac{\frac{25}{22}\binom{22}{3}}{\binom{25}{3}}$ See this recent question as well as its linked and related questions for obtaining the formula $\frac{n}{n-r}\binom{n-r}{r}$ for counting the number of ways in which none are adjacent. $\endgroup$ – Daniel Mathias Jan 19 '19 at 16:25
1
$\begingroup$

Your numerator is incorrect.

We count the number of cases in which no two adjacent knights are selected by determining the number of favorable cases for a row, then subtracting those in which two people would be adjacent if the ends of the row are joined.

We arrange $22$ blue balls and $3$ green balls in a row so that no two of the three green balls are consecutive. Place $22$ blue balls in a row. This creates $23$ spaces, $21$ between successive balls and two at the ends of the row. $$\square b \square b \square b \square b \square b \square b \square b \square b \square b \square b \square b \square b \square b \square b \square b \square b \square b \square b \square b \square b \square b \square b \square$$ To ensure that no two of the green balls are consecutive, we choose three of these $23$ spaces in which to place a green ball, which can be done in $\binom{23}{3}$ ways.

However, if both spaces at the ends of the row are occupied by a green ball, they will be adjacent when the ends of the row are connected to form a circle. Thus, we must subtract these cases. If both ends of the row are occupied by a green ball and no two green balls are consecutive, then one of the $21$ spaces between successive blue balls must be occupied by a green ball.

Hence, the number of cases in which no two adjacent knights at the round table are selected is $$\binom{23}{3} - \binom{21}{1}$$ Dividing by the $\binom{25}{3}$ possible selections of three knights gives the probability $$\frac{\dbinom{23}{3} - \dbinom{21}{1}}{\dbinom{25}{3}} = \frac{35}{46}$$ that no two consecutive knights are selected, so the probability that at least two adjacent knights are selected is $$1 - \frac{35}{46} = \frac{11}{46}$$

We could also count directly. There are $25$ ways to select three consecutive knights and $25 \cdot 21$ ways to select a pair of adjacent knights (pick the leftmost member of the pair, then select the third knight from among the $21$ knights not adjacent to the pair), for a total of $25 + 25 \cdot 21$ favorable cases, which gives the probability
$$\frac{25 + 25 \cdot 21}{\dbinom{25}{3}} = \frac{11}{46}$$ that at least two consecutive knights are selected.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.