Número mínimo de personas, de modo que se puede esperar que 2 se encuentren uno al lado del otro

Question

Nos da una gran mesa redonda con $n$ asientos. Es fácil ver que cada vez que $p\geq \text{int}(\frac{n}{2}) + 1$ la gente está sentada, al menos $2$ personas se sientan uno al lado del otro (en este caso $\text{int}(x)$ denota el mayor entero menor o igual a $x$).

Dado $n$ de los asientos en la mesa redonda, vamos a $s(n)$ ser el número más pequeño de modo que la probabilidad de que al menos $2$ personas se sientan uno al lado del otro es $\geq 0.5$ al $s(n)$ la gente elige a sus lugares al azar. (Es decir: en primer lugar, la persona número $1$ elige un asiento con el uniforme de probabilidad, a continuación, número $2$ ocupa uno de los asientos restantes con el uniforme de probabilidad, etc.)

Qué $\lim_{n\to \infty}\frac{s(n)}{n}$ existen, y cuál es su valor?

Answer 1

Usted puede mirar a través de el número esperado de personas que tienen un vecino, que simplemente es $n$ veces la probabilidad de que una determinada persona tiene un vecino. Pero también aquí es un enfoque combinatorio.

Wlog poner la primera persona en una posición fija. Ahora tenemos para el asiento de $s-1$ de personas en $n-1$ lugares colocados a lo largo de una línea en lugar de un círculo.

Si hacemos esto al azar, a continuación, todos los $\left( \begin{smallmatrix} n-1 \\ s-1 \end{smallmatrix} \right)$ subconjuntos son igualmente probables.

Pero se puede comprobar que el número de $W(m,k)$ de las formas para elegir a $k$ posiciones de una línea de longitud de la $m$ no hay dos lugares consecutivos elegido es $\left( \begin{smallmatrix} m-k+1 \\ k \end{smallmatrix} \right)$.

(Por ejemplo, comprobar mediante la inducción en $m+k$, ya que considerando los dos casos donde la primera posición en la línea es elegido o rechazado, consigue $W(m,k)=W(m-2,k-1)+W(m-1,k)$.)

Para obtener el número de acuerdos de buena que en nuestro caso, tome $m=n-3$ $k=s-1$ (porque también tenemos que evitar los dos asientos en cada lado de la primera, fijo, persona). Por lo que el número de "buena" subconjuntos de $\left( \begin{smallmatrix} n-s-1 \\ s-1 \end{smallmatrix} \right)$, y por lo que la probabilidad de evitar un enfrentamiento cuando los asientos de la gente al azar es $$ \frac{ \left( \begin{smallmatrix} n-s-1 \\ s-1 \end{smallmatrix} \right) } { \left( \begin{smallmatrix} n-1 \\ s-1 \end{smallmatrix} \right) } $$ Así que la pregunta se reduce a la probabilidad de que un determinado subconjunto de tamaño $s$ es evitado cuando la elección de $s-1$ objetos uniformemente al azar de un conjunto de tamaño $n-1$.

Espero que usted puede tomar desde aquí.