1
$\begingroup$

Can someone explain to me why my solution to this problem is wrong? Where have a made a logical error?

The problem is

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$?

My solution to this was that first, the chance of every person being chosen was $1/25$. The probability of any next single person being chosen was $1/24$. Therefore, the probability of $2$ people sitting next to each other is $1/25 \cdot 1/24$.

I then did this for $3$ people, and got $1/25 \cdot 1/24 \cdot 1/23$, then added this to $1/25 \cdot 1/24$.

Can someone explain to me where I have gone wrong logically? Why is this wrong?

And as an addition, what situation would the above answer describe? If it does not describe the probability of at least $2$ of $3$ people sitting together being chosen, then what probability does the answer above give?

$\endgroup$
  • $\begingroup$ Hint: count how many ways no three sit next to each other; i.e. count the complement. $\endgroup$ – Sean Roberson Aug 18 '18 at 5:45
  • $\begingroup$ @SeanRoberson Thanks. But can you also explain why the above method is wrong? $\endgroup$ – Ethan Chan Aug 18 '18 at 5:46
  • 3
    $\begingroup$ It is usually hard to explain why a wrong argument is wrong. Yours is just absurd, you haven't really justified (combinatorically, probabilistically) why you applied certain operations on certain numbers. I often see this when teaching combinatorics: the student takes the numbers in the problem, substitutes it into their favorite formula, and then wonders where they went wrong. Think about it. Try to reformulate the problem so that you can justify the use of formulas in the subproblems. Why did you multiply those numbers? (independent events?) Why did you add the products? (disjoint events) $\endgroup$ – A. Pongrácz Aug 18 '18 at 6:20
  • 1
    $\begingroup$ There are two seats next to the first person who is selected, so the probability of selecting a person next to the first person is $2/24$. However, it is not necessarily the case that somebody will sit next to the first person who is selected. It could be that the first and second people selected will sit next to each other, the first and third people selected will sit next to each other, or the second and third people selected will sit next to each other. Things get still more complicated when you consider ways in which all three people sit consecutively. $\endgroup$ – N. F. Taussig Aug 18 '18 at 7:31
  • $\begingroup$ @N.F.Taussig Thanks, I now see where I've gone wrong. $\endgroup$ – Ethan Chan Aug 18 '18 at 8:33
1
$\begingroup$

What is wrong with your attempt?

Trying to select the people sequentially is asking for trouble.

You are guaranteed to pick someone first, so the probability that you select someone first is $1$. It is true that the probability of picking a particular person first is $1/25$, but you have to multiply this by the $25$ a person could be selected first.

Since there are two seats next to the seat occupied by the first person, the probability that the second person selected sits next to the first person is $2/24$, not $1/24$.

If the first two people selected are adjacent, it is possible for the third person who is selected to be adjacent to them (in two ways) or not adjacent to them.

Also, even if the first two people who are selected are not adjacent, it is possible for the third person who is selected to sit next to one of them, both of them (if the first two knights who were selected had exactly one seat between them, which can occur in two ways), or none of them.

Also, we cannot add the probability that three people are adjacent to the probability that two people are adjacent unless we calculate the probability that exactly two people are adjacent since having two adjacent people does not preclude the possibility that three people are adjacent (in fact, it counts those cases twice, once for each pair to which the person in the middle belongs).

A better approach

Assume the positions of the knights are fixed.

In how many ways can three of the $25$ knights at the round table be selected?

$$\binom{25}{3}$$

For the favorable cases, we wish to count selections in which at least one pair of adjacent knights is selected.

In a given pair of adjacent knights, one person must be on the right. Choosing the position of that person also determines the position of the other knight in the adjacent pair of knights. In how many ways can the person who sits on the right in the adjacent pair be seated?

There are $25$ possible positions for the member of the adjacent pair who sits on the right.

Once we have selected a pair of adjacent knights, in how many ways can we select the third knight, who may or may not be adjacent to the pair of adjacent knights?

Once the adjacent pair has been selected, there are $25 - 2 = 23$ ways to choose the remaining knight.

In how many ways can we select a pair of adjacent knights and a third person from the round table?

By the Multiplication Principle, there are $25 \cdot 23$ such selections.

However, we have counted each selection in which three knights who are seated consecutively are chosen twice, once when we designated the pair in which the middle knight and the knight to his right are selected as the pair of adjacent knights and once when we designated the pair in which the middle knight and the knight to his left are selected as the pair of adjacent knights. We only want to count such selections once, so we must subtract them from the total.

In a given trio of consecutive knights, one person must be in the middle. Choosing the position of that person also determines the positions of the other knights in the trio of consecutive knights. In how many ways can the person who sits in the middle of the trio of consecutive knights be seated?

There are $25$ possible positions for the position of that knight.

How many favorable cases are there?

By the Inclusion-Exclusion Principle, the number of favorable cases is $25 \cdot 23 - 25$.

Dividing the number of favorable cases by the number of ways of selecting three knights gives the probability that at least two consecutive knights are selected.

$\endgroup$
1
$\begingroup$

Call the three chosen knights Alf, Bill, and Chuck. Let $x$ be the number of chairs between Alf and Bill, $y$ the number between Bill and Chuck, $z$ the number between Chuck and Alf. Then $x,y,z$ are nonnegative integers that add up to $22;$ by the so-called "stars and bars" formula, the number of solutions is $\binom{24}2.$ This is the total number of configurations for the three chosen knights.

Now let's count the number of configurations in which none of the three chosen knights are sitting next to each other. This means that $x,y,z$ are positive integers that add up to $22.$ That is, $x=u+1,y=v+1,z=w+1,$ where $u,v,w$ are nonnegative integers adding up to $19;$ the number of solutions is $\binom{21}2.$

The probability that no two of the three chosen knights are sitting next to each other is therefore $$\frac{\binom{21}2}{\binom{24}2}=\frac{21\cdot20}{24\cdot23}=\frac{7\cdot5}{2\cdot23}=\frac{35}{46},$$ and the probability that at least two of them are sitting next to each other is $$1-\frac{35}{46}=\boxed{\frac{11}{46}}.$$

$\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.