Hey, this is Presh Talwalkar
Five people are seated randomly around a circular table.
What is the probability two people will be seated next to each other?
We can make the question a little bit more precise by labeling the people as A, B, C, D and E
and asking about the probability that A and B will be seated next to each other?
This is part one of the question
The next part is to ask for the same probability if the five people are seated randomly in a row.
The next part is to generalize
What is the probability if there are n people seated randomly?
Solve for both cases of seating around a circular table and in a row.
This problem has been asked to programmers
and during other technical jobs as an interview question.
Can you figure it out?
Give this problem a try and when you're ready keep watching the video for the solution.
We'll first consider seating around a circular table with five people
There are a couple of ways we'll solve this the first method is will consider equally likely seats
We have a circular table with five different seats
Person A will be in some seat.
Without loss of generality we can make it the seat at the top of the diagram
Person B can be in any of the four remaining seats.
It's equally likely that b will be in any of these seats.
All these seats exactly two of them will be adjacent to A.
Therefore the probability that A and B will be seated adjacent
is 2/4 which equals 1/2 and that's 50%
There's another way you could solve the problem by counting pairs of seats
When there are five seats there are 5 choose 2 which equals 10 pairs of seats.
Out of these, there are 5 pairs that are adjacent
Each seat can be paired adjacently to the one that's right next to it going Clockwise
Therefore the probability that A and B will be adjacent
will be 5/10 which also equals 1/2 and that's also 50%
Let's now solve the problem of seating in a row
One way to solve this is to use conditional probability
There are two different ways that a could be seated
Person A could be in the first or the last seat.
These are two out of five possible seats.
So if person A is in the first seat for example
Then person B will be adjacent for exactly one of the four remaining seats
Similarly a person is at the end seat person B has to be right next to it.
That's one out of the four remaining seats.
Now there's another case that person a could be in a middle seat,
so in this five person case there are three middle seats.
In any of these seats
person B can be adjacent to be either on the left side or the right side
there are two places that person B could be and could be adjacent.
So if we put these cases together
the probability is (2/5)*(1/4) Plus (3/5)*(2/4)
And that simplifies to be 2/5 which is 40%
Another way is that we could count the pairs of seats. There are 5 choose 2 which is 10 pairs of seats.
Now how many of these are adjacent?
Well there are 4 pairs of adjacent seats.
Because the first the second the third and the fourth seats could be paired with the seat after it
Therefore there are 4 out of 10 possibilities which also equals 40%
Now let's generalize for n people
We could solve these in the same ways
Let's consider the method of equally likely seat
Person A will be at some seat.
And now person B can be any of the n-1 remaining seats,
and it's equally likely that B will be at any of these n-1 remaining seats
Out of them
exactly 2 will be adjacent the seat to the left and the seat to the right of person A
Therefore there will be exactly 2/(n-1)
possible ways that A and B could be next to each other. So the probability is 2/(n-1)
We can also do the same thing by counting the pairs of seats
There are n choose 2 which equals n(n-1) /2 pairs of seats
Out of these there are n pairs of adjacent seats we start from the top of this diagram and go clockwise
Each seat can be paired with the one right after it we end up counting n different pairs of adjacent seats
So we take n divided by n choose 2, this also simplifies to be 2/(n-1)
Let's now solve the case seating in a row where you have n people
We can again solve it by conditional probability
One case is that A is either in the first seat or the last seat?
So these will be 2 out of the n possible seats, so in the first seat
person B could be adjacent for only 1/(n-1) remaining seats
Would have to be just right after or if a was at the very end B would have to be just before.
Now there's also the other case that A could be in a middle seat
there are (n-2)/n middle seats
Any of these middle seats B could either be on the left side or the right side.
So there will be 2/(n-1) possible ways that B could be adjacent
if we combine these cases we end up with the following equation.
(2/n)*(1/(n-1)) + ((n-2)/n)*(2/(n-1))
If you work through the algebra this simplifies to be 2/n, and that's the probability
We also do the same thing by counting pairs of seats
There n choose 2 pairs of seats and now how many adjacent seats are there? Well there are n-1
Each seat can be paired with the seat to its right so starting from the first seat on the left
We can count all the way up to n-1 that very last seat has no seat to its right
Therefore, we take n-1 and divide it by n choose 2 and that also simplifies to be 2/n
Did you figure out these problems?
Thanks for watching this video please subscribe to my channel
I make videos on math
You can catch me on my blogs mind your decisions that you can follow on Facebook google+ and patreon you can catch you on social
media at Presh Talwalkar and if you like this video, please check out my books there are links in the video description