Minimum number of people such that 2 can be expected to sit next to each other 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?
 A: 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. 
