4
$\begingroup$

We are given a large, round table with $n$ seats. It is easy to see that whenever $p\geq \text{int}(\frac{n}{2}) + 1$ people are seated, at least $2$ people will sit next to each other (here $\text{int}(x)$ denotes the largest integer less or equal than $x$).

Given $n$ seats at a round table, let $s(n)$ be the smallest number so that the probability that at least $2$ people sit next to each other is $\geq 0.5$ when $s(n)$ people choose their places randomly. (That is: first, person number $1$ picks a seat with uniform probability, then number $2$ takes one of the remaining seats with uniform probability, etc.)

Does $\lim_{n\to \infty}\frac{s(n)}{n}$ exist, and what is its value?

$\endgroup$
  • 1
    $\begingroup$ I suppose you are not taking socio- psychological factors into account :) $\endgroup$ – Dirk Horsten Jul 24 '15 at 12:57
  • $\begingroup$ Have you tried simulating this? There is a numeric approach, not just an analytic one? $\endgroup$ – EngrStudent - Reinstate Monica Jul 27 '15 at 9:54
  • $\begingroup$ This looks like a tricky problem, since it depends on the gap size between previous people; this isn't a solution yet, it's more an exploration of the problem. Here I work with the complement (everyone sits alone). probability first person sits alone = 1 probability 2nd person sits alone = $(n-3)/(n-1)$ (since there's a seat either side of person one that's empty but would result in sitting adjacent to person 1; person 1 has a "forbidden zone" of 1 seat either side of them that person 2 can't occupy if they sit alone.) ...ctd $\endgroup$ – Glen_b -Reinstate Monica Jul 27 '15 at 10:19
  • $\begingroup$ ctd... Probability 3rd person sits alone if second person sits alone has two possibilities: a: person 2's zone doesn't overlap person 1's - then person 1 and person 2 "use up" 6 seats, and occupy 2, so prob=(n-6)/(n-2) b: person 2's zone overlaps person 1's - then person 1 and person 2 "use up" 5 seats, and occupy 2, so prob=(n-5)/(n-2) While the probability we're in situation b will be small (if n is large), as we add more people we get more and more cases of zone overlap; ... ctd $\endgroup$ – Glen_b -Reinstate Monica Jul 27 '15 at 10:20
  • $\begingroup$ ctd ... it looks like there's a rapidly increasing number of possibilities (different numbers of overlapping or non-overlapping zones) here as we add people. We need to keep track of the total number of "free" spaces using this approach and this seems to get quite complicated. It's possible there's a neater way to do it; perhaps we can recursively construct the probability distribution of the number of "forbidden" seats and empty seats as $n$ grows. $\endgroup$ – Glen_b -Reinstate Monica Jul 27 '15 at 10:20
2
$\begingroup$

You could look at this via the expected number of people who have a neighbour, which is simply $n$ times the probability that a given person has a neighbour. But alternatively here is a direct combinatorial approach.

Wlog put the first person in a fixed position. Now we have to seat $s-1$ people in $n-1$ places arranged along a line rather than a circle.

If we do this at random then all $\left( \begin{smallmatrix} n-1 \\ s-1 \end{smallmatrix} \right)$ subsets are equally likely.

But you can check that the number $W(m,k)$ of ways to choose $k$ positions from a line of length $m$ with no two consecutive places chosen is $\left( \begin{smallmatrix} m-k+1 \\ k \end{smallmatrix} \right)$.

(For example, verify this by induction on $m+k$, since by considering the two cases where the first position in the line is chosen or rejected, you get $W(m,k)=W(m-2,k-1)+W(m-1,k)$.)

To get the number of good arrangements in our case, take $m=n-3$ and $k=s-1$ (because we also have to avoid the two seats either side of the first, fixed, person). So the number of "good" subsets is $\left( \begin{smallmatrix} n-s-1 \\ s-1 \end{smallmatrix} \right)$, and so the probability of avoiding a clash when seating people at random is $$ \frac{ \left( \begin{smallmatrix} n-s-1 \\ s-1 \end{smallmatrix} \right) } { \left( \begin{smallmatrix} n-1 \\ s-1 \end{smallmatrix} \right) } $$ So the question reduces to the probability that a given subset of size $s$ is avoided when choosing $s-1$ objects uniformly at random from a set of size $n-1$.

I expect you can take it on from here.

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