Knights Around A Table

Let's say the 3 knights picked in order are named A, B, C as distinct. For symmetry reasons, let A be at seat 1. Then there are (24)(23) ways to arrange B and C in the rest of the seats. Out of these, we count the distinct ways at least 2 of them are sitting next to each other. Either B or C can be seated next to A, in which case the other can be seated in 23 other places, making (4)(23) in all. If neither B or C is seated next to A, then they must sit next to each other, and they can be seated in 20 other places times 2 for different orders, making (2)(20) in all. The fraction we seek is (4)(23) + (2)(20) divided by (24)(23), which works out to 11/46, and so the answer is 57.

Great ideas of Michael Mendrin en Kunal Kantaria in my opinion. I hope my solution is viewed as an useful addendum and not as redundant.

---

Denote $P_r^n = \frac{n!}{(n-r)!}$ as the number of $r$ -permutations of $n$ distinct objects and $Q_r^n = \frac{P_r^n}{r}$ as the number of $r$ -circular permutations of $n$ distinct objects.

---

Special cases where $r = n$ give rise to $P_n^n = n!$ and $Q_n^n = (n-1)!$ .

---

The question: "In how many ways can three specific men (A, B and C) along with 22 other men be seated around a circular table in such a way that at least of two the three men (A, B, C) are seated next to one another?" is equivalent to the problem at hand.

The total number of ways to seat 25 men around the table is

$Q_{25}^{25} = (25-1)! = 24!$

Solution 1: The method of Michael Mendrin

Case 1: The three men are seated next to one another in $Q_{23}^{23} \cdot 3! = 22! \cdot 3!$ number of ways. Treat the three men as one entity and place the 23 'objects' around the table and consider the number of ways the three men can permute.

Case 2: Of the three men only two are seated next to one another can be done in

$Q_{23}^{23} \cdot 21 \cdot 2 \cdot 3 = 22! \cdot 21 \cdot 3!$

number of ways. Treat the two men as one entity and place the 22 + 1 'objects' around the table. The entity of two men can be seated at 21 places (not adjacent to the specific man), the two men can change seats with one another (factor 2) and there are 3 ways of choosing two men out of the three to form the entity.

Total number of seatings is $22! \cdot 3! + 22! \cdot 21 \cdot 3!$ out of $24!$ seating resulting in:

$\frac{22! \cdot 3! + 22! \cdot 21 \cdot 3!}{24!} = \frac{22! \cdot 3! (1 + 21)}{24!} = \frac{11}{46}$

Solution 2: By method of complementation of Kunal Kantaria

The complement of the number of desired seatings is the number of seatings in which none of the three men (A, B, C) are seated next to one another. The 22 other men along with man A can be seated in $Q_{23}^{23} = 22!$ number of ways. There are now 23 places where man B can be seated, but only 23 - 2 = 21 seats are allowed. Then 24 men are seated and of the 24 available seats only 24 - 4 = 20 seats are allowed for man C.

Thus the total number of desired seatings is $24! - 22! \cdot 21 \cdot 22$ giving rise to the same requested probability:

$1 - \frac{22! \cdot 21 \cdot 22}{24!} = 1 - \frac{35}{46} = \frac{11}{46}$

The answer in both solutions is 11 + 46 = 57.

There's 25 ways to pick up three people next to each other.

With 2 people next to each other, there's 25 ways to pick up the single one, and then $25-4=21$ ways to pick up two people next to each other. So that is $25·21=525$ ways.

Total: 550 ways. Total of ways is $\begin{pmatrix}25\\3\end{pmatrix}=2300$ .

Then $P=\frac{550}{2300}=\frac{11}{46}$ .

---

With formula of number of $m$ -gons in a $n$ -gon without common side (so, picking $m$ people out of $n$ people without two next to each other) is $\frac{n}{m}\begin{pmatrix}n-m-1\\m-1\end{pmatrix}$ . Here, that is $\frac{25}{3}\begin{pmatrix}21\\2\end{pmatrix}=\frac{25}{3}·210=1750$ , so $2300=1750=550$ ways with at least two adjacent people.

I explained the formula in the answers of this problem .

In $\frac{2}{24}$ cases, the 2nd knight is already next to 1st. In $\frac{2}{24}$ cases, the second knight is one chair apart from 1st, so there is a $\frac{3}{23}$ chance that the 3rd knight will be a neighbor of one of them. In remaining $\frac{20}{24}$ scenarios, the probability for 3rd knight to be a neighbor of one of them is $\frac{4}{23}$ , so the probability in question is simply $\frac{2}{24}$ + $\frac{2}{24}$ $\frac{3}{23}$ + $\frac{20}{24}$ $\frac{4}{23}$ = $\frac{11}{46}$ .

Let the three knights who are sent be $A,B,C$ .They can be seated around the table in 2 ways $ABC$ or $ACB$ clockwise.

Let us now find the probability $Q$ that none of them is sitting together.

Let there be $x,y,z$ persons sitting between $A B$ and $C$ respectively

where $x,y,z$ should be greater than $0$ (not equal to $0$ )

and $x+y+z=22$

Using multinomial therem we have the number of solution as $\dbinom{21}{2}$ and the knights can be arranged in $22!$ ways.

The total number of sitting arrangements are $(25-1)!=24!$ .

$\Rightarrow Q = \frac{2 \times \dbinom{21}{2} \times 22!}{24!}=\frac{35}{46}$

Therefore the required probability $P$ that at least two are sitting together is $P = 1-Q$

$\Rightarrow P=1-\frac{35}{46}$

$\Rightarrow P=\frac{11}{46}$

Therefore the answer is $\boxed{57}$

Number of way we could have three knights all in a row = 25

Number of way we could have two knights next to each other and one sitting alone = $25\times 21$ . There are 25 ways of having two seats in a row, 21 possibilities left for the choice of the third knight.

Number of ways we could have all three sitting singly = $(25\times 20\times 19 + 25\times 2\times 20)/3! = 25\times 70$ . There are 25 ways to pick the first knight, 20 ways to pick the second so that there is a gap of at least two between them in which case there are 19 ways to pick the third knight. There are also 2 way to pick the second knight so that there is a gap of just one between them, in which case there are 20 ways to pick the third knight. Divide all this by 3! because we can reorder.

So we have $25 + 25\times 21 + 25\times 70$ ways to pick the three knights and $25 + 25\times 21$ of these give at least two sitting next to each other. get rid of the factor of 25 and we have (1+21)/(1+21+70)= 22/92 = 11/46.

Not the quickest way (we didn't really need to work out the number of ways we could have all three sitting singly), but it shows all the different combinations.

Let's look at a round table of 6 knights. It might help us to imagine it as a 6 sided polygon:

Now, let's select any pair of adjacent seats from the table. This is equivalent to selecting a random edge from the hexagon, giving us 6 possible choices. With $N$ seats, we have $N$ possible adjacent seat pairs to choose from. Next we choose a random point from the remaining points. For the hexagon, this would seem to give us $6-2$ possible seat choices. So we would naively expect there to be $6*(6-2)$ ways to select the knights such that at least two of them are adjacent to each other. However, we have forgotten to notice that we're double counting.

Let's go through the seat-pairs for a round table of 6 knights where the seats are labeled 1-6 and 1 and 6 are adjacent:

I've bolded the seats that create duplicate selections. For example, the selection $(1, 2) + 3$ is the same the selection $(2,3) + 1$ . For each adjacent-pair there are going to be exactly 2 seats that they'll share with other adjacent-pairs no matter what $N$ we use since each adjacent-pair has exactly 2 points adjacent to the pair. So to fix our double counting issue we exclude the point directly counterclockwise from the adjacent-pair we chose:

We've eliminated one of the choices from our original $N-2$ and are left with $N-3$ ways to uniquely select a final seat for each adjacent-pair.

Thus there are $N*(N-3)$ ways to uniquely select the knights such that at least 2 of them are adjacent to each other.

Finally there are $\begin{pmatrix} N \\ 3 \end{pmatrix}$ ways to select knights to go on the mission. Therefore the probability that at least 2 of the knights are adjacent to each other is: $\frac { N*(N-3) }{ \begin{pmatrix} N \\ 3 \end{pmatrix} }$

And when you plug $N=25$ in you get: $\frac {550 }{ 2300 }$ which simplifies to $\frac {11}{46}$ . Finally giving us the answer $57$ .