Cómo tomar asiento en un avión

Question

Este es un pequeño problema que he discutido hoy con mi grupo de laboratorio durante el almuerzo. No es particularmente difícil, pero tiene implicaciones interesantes.

Imagina que hay 100 personas en la cola para subir a un avión con 100 plazas. La primera persona de la cola se da cuenta de que ha perdido su tarjeta de embarque, así que cuando sube al avión decide coger un asiento al azar. Todas las personas que suban al avión después de él ocuparán su asiento "adecuado" o, si éste está ocupado, un asiento al azar.

Pregunta: ¿Cuál es la probabilidad de que la última persona que suba a bordo acabe en su asiento correspondiente?

Además, y esta es la parte sobre la que todavía estoy reflexionando. ¿Puedes pensar en un sistema físico que siga esta estadística combinatoria? Quizá una función de onda de espín en un cristal, etc.

Answer 1

Este es un rompecabezas clásico.

La respuesta es que la probabilidad de que la última persona acabe en su sitio es exactamente $\frac{1}{2}$

El razonamiento es el siguiente:

En primer lugar, observe que el destino de la última persona se determina en el momento en que se selecciona el primer o el último asiento. Esto se debe a que la última persona obtendrá el primer asiento o el último. Cualquier otro asiento estará necesariamente ocupado en el momento en que el último tenga que "elegir".

Dado que en cada paso de elección, el primero o el último tienen la misma probabilidad de ser tomados, la última persona obtendrá el primero o el último con igual probabilidad: $\frac{1}{2}$ .

Lo siento, no tengo ni idea de un sistema físico.

Answer 2

Busquemos la posibilidad de que cualquier el cliente termina en el asiento equivocado.

Para $2\leq k\leq n$ , cliente $k$ será golpeado cuando encuentre su asiento ocupado por alguien con un número menor, que también fue desplazado por alguien con un número menor, y así sucesivamente hasta llegar al cliente $1$ .

Este proceso puede resumirse en el diagrama $$1\longrightarrow j_1\longrightarrow j_2\longrightarrow\cdots\longrightarrow j_m\longrightarrow k.$$
Aquí $j_1<j_2<\cdots <j_m$ es cualquier secuencia creciente (posiblemente vacía) de números enteros estrictamente entre $1$ y $k$ . La probabilidad de esta secuencia de eventos es $${1\over n}\times{1\over(n+1)-j_1}\times {1\over(n+1)-j_2}\times\cdots\times{1\over(n+1)-j_m}.$$

Así, la probabilidad de que el cliente $k$ se golpea es $$p(k)={1\over n}\sum\prod_{\ell=1}^m {1\over(n+1)-j_\ell}$$ donde la suma es sobre todos los conjuntos de $j$ valores $1<j_1<j_2<\cdots <j_m<k$ . Es decir, \begin{eqnarray*} p(k)&=&{1\over n}\sum_{J\subseteq\{2,\dots,k-1\}}\ \, \prod_{j\in J}{1\over (n+1)-j}\cr &=&{1\over n}\ \,\prod_{j=2}^{k-1} \left(1+{1\over (n+1)-j}\right)\cr &=&{1\over n}\ \,\prod_{j=2}^{k-1} {(n+2)-j\over (n+1)-j}\cr &=&{1\over n+2-k}. \end{eqnarray*}

En el caso $k=n$ obtenemos $p(n)=1/2$ como en las otras soluciones. Quizá haya una explicación intuitiva de la fórmula general; a mí no se me ha ocurrido ninguna.

---

Referencia añadida: Encontrar su asiento frente a lanzar una moneda por Yared Nigussie, American Mathematical Monthly 121, junio-julio 2014, 545-546.

Answer 3

Este análisis es correcto, pero no lo suficientemente completo como para convencerme. Por ejemplo, ¿por qué el destino de la última persona se resuelve tan pronto como se elige el asiento de la primera? ¿Por qué cualquier otro asiento que no sea el de la primera persona o el de la última persona estará ocupado en el momento en que la última persona suba a bordo?

Tuve que rellenar los huecos por mí mismo de esta manera...

El destino de la última persona se decide tan pronto como alguien elige el asiento de la primera persona (nadie está ahora en un asiento equivocado, por lo que todos los demás obtienen su asiento asignado, incluida la última persona) o el asiento de la última persona (la última persona ahora no obtendrá su asiento correcto). Cualquier otra elección en cualquier fase no cambia las probabilidades en absoluto.

Reformulando... en cada etapa, o bien el asunto se resuelve y hay un 50/50 de probabilidades de que se resuelva en cada sentido para el asiento de la última persona, o simplemente se pospone la agonía. Por lo tanto, el asunto puede resolverse en cualquier etapa, y las probabilidades en esa etapa son las únicas que importan, y son 50/50 sin importar la etapa. Por tanto, la probabilidad global es de 50/50.

Answer 4

Dejemos que $P(n)$ denotan la probabilidad de que el último pasajero obtenga su asiento si comenzamos con $n$ pasajeros.

Considere el caso simple de sólo $2$ asientos:

$P(2) = \frac12$ (el primer interno elige su propio asiento con 1/2 probabilidad)

Para $n$ asientos: (i) Con $\frac1n$ probabilidad, el pasajero elige el asiento del primer pasajero, el n'º asiento desde el final (en cuyo caso el último pasajero obtendría definitivamente su asiento). (ii) Con una probabilidad de 1/n, el pasajero actual elige el asiento del último pasajero, el primer asiento desde el final (y ahora, el último pasajero puede definitivamente no conseguir su propio asiento). (iii) En caso contrario, el pasajero elige algún otro asiento (digamos #i del final) entre los n-2 asientos restantes (con probabilidad 1/n), continuando el dilema. El problema se reduce ahora al problema inicial con i asientos.

Por lo tanto, $$ P(n) = \frac1n \times 1 + \frac1n \times 0 + \frac1n\sum_{i=2}^{n-1} P(i) $$ o $$ nP(n) = 1 + \sum_{i=2}^{n-1} P(i).$$ Así que $$nP(n)-(n-1)P(n-1)=P(n-1)\Longleftrightarrow P(n)=P(n-1),$$ y $P(n)=P(2) = \frac12, \,\forall n \ge 2$ .

Answer 5

No tengo la intuición para esto, pero conozco la prueba formal. Esto equivale a demostrar que la probabilidad de que en una permutación de $[n]$ elegidos uniformemente al azar, dos elementos elegidos uniformemente al azar están en el mismo ciclo es $1/2$ . Por simetría, basta con demostrar que la probabilidad de que $1$ y $2$ están en el mismo ciclo es $1/2$ .

Hay muchas maneras de demostrar este hecho. Por ejemplo: la probabilidad de que $1$ está en un ciclo de longitud $k$ es $1/n$ , para $1 \le k \le n$ . Esto es cierto porque el número de posibles $k$ -ciclos que contienen $1$ es ${n-1 \choose k-1} (k-1)! = (n-1)!/(n-k)!$ y el número de formas de completar una permutación una vez que un $k$ -El ciclo elegido es $(n-k)!$ . Así que hay $(n-1)!$ permutaciones de $[n]$ en el que $1$ está en un $k$ -ciclo. Ahora la probabilidad de que $2$ está en el mismo ciclo que $1$ dado que $1$ está en un $k$ -ciclo, es $(k-1)/(n-1)$ . Así que la probabilidad de que $2$ está en el mismo ciclo que $1$ es $$ \sum_{k=1}^n {k-1 \over n-1} {1 \over n} = {1 \over n(n-1)} \sum_{k=1}^n (k-1) = {1 \over n(n-1)} {n(n-1)\over 2} = 1/2. $$

Como alternativa, el Proceso del restaurante chino con $\alpha = 0, \theta = 1$ genera una permutación aleatoria uniforme de $[n]$ en el $n$ paso; $2$ está emparejado con $1$ en el segundo paso con probabilidad $1/2$ . Esto es un poco más elegante, pero requiere una cierta comprensión del CRP.