Asientos de $n$ de las personas con entradas en $n+k$ sillas con la 1ª persona que toma un asiento al azar

Question

"$n$ los amantes de la música han reservado asientos en un teatro que contiene un total de $n+k$ escaños ($k$ asientos están sin asignar). La primera persona que entra en el teatro, sin embargo, perdió la asignación de asiento y elige un asiento al azar. Posteriormente, las personas entran en el teatro, de una en una y sentarse en su asiento asignado a menos que ya esté ocupado. Si es así, elija un asiento al azar de entre el resto de los asientos vacíos. ¿Cuál es la probabilidad de que la persona $n$, la última persona en entrar en el teatro, encuentra su asiento ya está ocupado?"

Yo podría hacer este problema para los pequeños valores específicos de $n$$k$, pero a medida que crecen las expresiones parecen a poner muy complicado realmente rápido con ningún patrón discernible. ¿Cómo se podía resolver este problema?

Answer 1

Deje $N=n+k$. Yo reclamo la probabilidad de que la persona $i$'s del asiento es tomado ya cuando ella entra en la habitación es $\frac{1}{N-i+2}$ si $i>1$. Podemos demostrarlo por inducción. De hecho, si $1<j<i$, entonces, por inducción, la probabilidad de que $j$ elige un asiento al azar es $\frac{1}{N-j+2}$, por lo que el probable que alguien se $i$'s seat es

$$\frac{1}{N} + \sum_{1<j<i} \frac{1}{N-j+2}\frac{1}{N-(j-1)} = \frac{1}{N} + \sum_{1<j<i} \left(\frac{1}{N-(j-1)}-\frac{1}{N-(j-2)}\right) = \frac{1}{N-i+2}.$$

(La probabilidad de que $j$ toma asiento $i$ si $j$ elige un asiento al azar y todavía nadie ha tomado asiento $i$$1/(N-(j-1)$.)

Tomando $i=n$, consigue $1/(k+2)$.

Hay un segundo, evidentemente, mucho más agradable manera de obtener esta respuesta. Observe que, tan pronto como nadie elige cualquiera de los escaños $1,n,n+1,\ldots,n+k$, el destino de la persona $n$ está sellado, porque cada persona lleva su propio asiento. Claramente cada uno de los escaños $1,n,\ldots,n+k$ tiene la misma probabilidad de ser tomada en primer lugar, por lo que la probabilidad de que el asiento de $n$ es tomada en primer lugar es $1/(k+2)$.

Answer 2

Creo que la forma más sencilla de ver la solución es considerar otro problema: el de la primera persona toma un asiento al azar. Las personas que lleguen después de ir a sus propios asientos no importa qué - si su asiento está ocupado, le piden a la persona que lo ocupa para alejarse y tomar una muestra aleatoria de asiento entre los asientos todavía vacantes. Esto es claramente equivalente al problema original. Por otra parte, es fácil de resolver. La primera persona a cambiar sus asientos hasta terminar en uno de los asientos de $1,n,n,n+1,\dots n+k$, cada uno de estos, es igual de probable. Por lo tanto la probabilidad de que la última persona que se encuentra su asiento ocupado ya es exactamente $1/(k+2)$

Answer 3

Esto es similar a un típico problema con respecto a los pasajeros que ocupan los asientos en un avión.

Por el momento $r$ la gente está sentada, la escaños $2,3,\ldots,r$ están todos ocupados (si $i^\mathrm{th}$ asiento estaba desocupado, $i^\mathrm{th}$ persona habría sentado allí, para $i \neq 1$). Por lo $r-1$ asientos son fijos. Que un asiento adicional, si era alguna de las $k$ extra de asientos, o si era el asiento de la $1$, luego el resto de las personas se sientan en sus lugares, en particular, $n^\mathrm{th}$ persona que se sentará en el asiento $n$. Pero si este asiento se $n$, $n^\mathrm{th}$ persona no puede tener asiento $n$ ahora. Cualquiera de estos dos eventos que ocurra primero, decide si $n$ sentado en el asiento $n$ o no. Supongamos que uno de estos eventos se produce por primera vez después de $r$ asientos están ocupados. Así que la persona $r$ se sentó en el asiento de $1$ o de cualquiera de las $k$ de los asientos o en el asiento de $n$'. Así que la probabilidad de que la persona $n$ puede sentarse en el asiento $n$$\frac{k+1}{k+2}$.

Answer 4

So n los amantes de la música(ML) pueden, en conjunto con los asientos vacíos para ser dispuestos $(n + k)!$ maneras.
Esa es la última de la ML puede sentarse correctamente, por lo que su ubicación debe estar vacío. Puede ser (k + 1) maneras. Aunque cada uno de estos asientos libres arreglo puede producirse $(k+n-1)!$ veces.
La probabilidad, de que el espectador tendrá el asiento libre es $p ={{(k + 1)(k+n-1)!}\over {(n + k)!}}$. Debido a $(n+k)! = (n+k)(n+k-1)!$, la probabilidad es:$$p = {{k+1}\over{k+n}}$$.