Resposta: Puzzle dos passageiros no avião

Pergunta:

Há 500 passageiros em uma fila (em ordem aleatória) para embarcar em um avião. O voo está totalmente reservado, com exatamente 500 assentos disponíveis. Devido a uma falha técnica, o primeiro passageiro escolhe um assento aleatoriamente, com todos os assentos igualmente prováveis.

Cada um dos outros passageiros segue esta regra: se o assento designado está livre, ele se senta nele; caso contrário, escolhe um assento aleatório dentre os disponíveis. Qual é a probabilidade de que o último passageiro sente-se em seu assento designado?

Original:
https://medium.com/puzzle-sphere/can-you-solve-this-famous-interview-question-91d0db846935

Resposta:

Vale a pena fazer a conta para alguns casos menores, a fim de entender e generalizar o problema.

1) Subcaso com apenas dois passageiros, A e B.

O primeiro pode sentar aleatoriamente, com igual probabilidade, no assento a ou b.

Se o primeiro sentar no a, o segundo senta no b, e está todo mundo no lugar certo.

Se o primeiro sentar no b, o segundo senta no a, assento errado.

Portanto, há 50% de chance do último passageiro sentar no assento correto.

2) Subcaso três passageiros, A, B e C.

Se o primeiro sentar em a, o segundo vai sentar em b e o terceiro em c — todo mundo no lugar certo.

Se o primeiro sentar em c, o último passageiro © vai necessariamente sentar em a.

Se o primeiro sentar em b, o segundo pode sentar em a ou c, com igual chance para a ou c. Se sentar em a, o último passageiro senta no lugar certo, c. Caso ele sente em c, o último vai sentar no lugar errado, a.

Portanto, 50% de chance de o último passageiro sentar no lugar certo.

Note a simetria. Há 1/3 de chance do primeiro sentar no lugar certo e resolver o problema, e 1/3 de chance dele sentar no lugar do último e bagunçar o lugar deste.

Para o 1/3 restante, depende do segundo passageiro, que vai ter 1/2 de chance de sentar no lugar certo ou no lugar do último passageiro.

3) Subcaso quatro passageiros, A, B, C e D.

Há 1/4 de chance de A sentar em a, daí todo mundo senta no lugar correto.

Há 1/4 de chance de A sentar em d, daí necessariamente D vai sentar no lugar errado.

Para os 2/4 restantes, é o caso de A sentar em b ou c. Daí, é como se transferisse a decisão para frente.

Se A sentou em b, B pode sentar em a, c, d.
Se B sentar em a, fecha o ciclo (A-b e B-a) e resolve o problema.
Se B sentar em d, o último passageiro vai necessariamente sentar no lugar errado.

E se B sentar em c, passa o problema para frente. E C pode sentar em a ou d, ou resolve a vida de D ou bagunça de vez.

Note a simetria. Cada sub sub problema tem a mesma estrutura. Igual chance de resolver o problema ou bagunçar tudo de uma vez. Se não for nenhuma dessas alternativas, a definição fica para a passageiro seguinte, que terá o mesmo comportamento.

Só por desencargo de consciência, vejamos outro caso.

Se A sentou em c, B pode sentar em a, b, d.

B senta em b — ou seja, passa a definição do destino de D para o próximo, o C.

C pode sentar em a e d — se sentar em a, resolve tudo (A-c e C-a), e d pode sentar no lugar certo. Se C
sentar em d, aí necessariamente d vai sentar em algum outro assento.

No final das contas, o último terá 50% de chance de sentar no lugar certo.

Ou seja, é sempre assim, dada a simetria das opções e as sub estruturas idênticas do problema.

4) Caso com N passageiros

Já deu para pegar a ideia?

O primeiro passageiro tem chance 1/N de sentar no lugar dele (e todo mundo sentará correto) e 1/N de chance de sentar no lugar do último (que sentará no lugar errado).

Cada um dos N-2 casos restantes terá chance 1/N.

Todos os passageiros vão sentando no lugar correto, até chegar a vez de quem teve o assento tomado (Digamos, o primeiro sentou no décimo lugar, aí só vai dar problema para ele).

Digamos que tenha sobrado K cadeiras. Ele vai ou sortear o primeiro assento com probabilidade 1/K, fechando o ciclo e resolvendo o resto; ou sortear a última com probabilidade 1/K (bagunçando a vida do último) ou vai sortear algum outro assento em chance (K-2)/K. Porém, o próximo vai ter exatamente o mesmo comportamento. Dada a simetria do problema, a resposta é que a chance é de 50%, independente do tamanho de N.

Bônus. Fiz uma simulação em Python para verificar.

Segue um print, para 8 passageiros. Note que o último ou senta correto, ou senta no primeiro assento.

Segue link do Github para o código completo. https://github.com/asgunzi/Puzzle_Assentos

Originally published at http://ideiasesquecidas.com on November 4, 2024.