On a sold-out flight, 100 people line up to board the plane. The first passenger in the line has lost his boarding pass but was allowed in regardless. He takes a random seat. Each subsequent passenger takes their assigned seat if available, or a random unoccupied seat, otherwise.What is the probability that the last passenger to board the plane finds their seat unoccupied?

在售罄的航班上，有100人排隊等候登機。 排隊的第一位乘客丟失了登機牌，但無論如何都被允許進入。 他隨便坐。 如果有空位，則其后每位乘客都將坐上他們分配的座位，否則將坐一個隨機的空座位，最后登機的乘客發現自己的座位沒有座的可能性是多少？

If your first instinct is to map out the possibilities with a smaller number of people boarding the plane, I invite you to take a moment and try the puzzle out for yourself. This approach resulted in a great deal of suffering on my end, and I wouldn’t want to deprive you of that experience.

如果您的第一個直覺是在登機的人較少的情況下確定各種可能性，那么我請您花點時間為自己解決難題。 這種方法給我帶來了很大的痛苦，我不想剝奪您的經驗。

Alternatively, read on for a Monte Carlo simulation and an explanation of the analytic solution.

另外，請繼續閱讀以進行蒙特卡洛模擬和解析解的說明。

蒙特卡羅模擬 (Monte Carlo Simulation)

Annoyed at my failure to manually solve the problem, I quickly typed out a messy Monte Carlo simulation in Python:

由于無法手動解決問題而感到惱火，我很快用Python輸入了一個混亂的蒙特卡洛模擬：

import random
import numpy as npairplane = []#positive indicates that the criteria (last passenger reaches their seat) is fulfilled & vice versapositive = 0
negative = 0#constructing airplane
for i in range (1,101):
    airplane.append(i)def simulate():
    
    global airplane
    global positive
    global negative#first passenger
    airplane.remove(np.random.choice(airplane))#subsequent passengers
for i in range (2,100):
        if i in airplane:
            airplane.remove(i)
        else:
            airplane.remove(np.random.choice(airplane))if 100 in airplane:
        positive += 1
    else:
        negative += 1airplane = []
    for i in range (1,101):
        airplane.append(i)#running 100k trials
for i in range (0,100000):
    simulate()print(positive/(positive+negative)*100)Output: 50.076

By Monte Carlo, the probability of the last passenger finding his seat is about 50%. I found it surprising that the probability was this high, considering that it represents the last passenger sitting in one particular seat in a 100-person plane.

根據蒙特卡洛，最后一位乘客找到座位的可能性約為50％。 考慮到它代表了坐著100人的飛機上一個特定座位的最后一位乘客，我發現這種可能性如此之高令人驚訝。

This is yet another probability puzzle where our intuition fails us. It reminds me specifically of the Birthday Paradox, where most people also tend to vastly underestimate the probability of a certain outcome as a result of deeply-flawed mental calculations.

這是我們的直覺使我們失敗的另一個概率難題。 它特別讓我想起了生日悖論 ，因為大多數人也往往由于心理計算的嚴重缺陷而大大低估了某種結果的可能性。

分析解決方案 (Analytic Solution)

The real probability is exactly 1/2. Here’s why:

實際概率恰好是1/2 。 原因如下：

From this point forward, I refer to passengers and their assigned seats in order of entry, such that the first passenger to board is Passenger 1 and the last to board is Passenger 100. Similarly, Seat 1 is the assigned seat of Passenger 1, and so forth.

從這一點開始，我將按照進入的順序指代乘客及其分配的座位，這樣第一個登機的乘客就是乘客1，最后一個登機的乘客是乘客100。類似地，座位1是乘客1的分配座位，并且等等。

Fact: Passenger 100 will sit in either Seat 100 (his assigned seat) or Seat 1.

事實：乘客100將坐在座位100(他指定的座位)或座位1中。

I best understand this observation through the perspective of each passenger boarding in-between the first and last. There are two possibilities for Passengers 2–99.

我從頭一個和最后一個之間的每個乘客登機的角度來最好地理解這一發現。 2–99號旅客有兩種可能性。

1. The passenger’s assigned seat is empty. They sit in that seat.
   乘客分配的座位空著。 他們坐在那個座位上。
2. The passenger’s assigned seat is occupied. They sit in some other seat at random.
   乘客分配的座位已被占用。 他們隨意地坐在其他座位上。

After each of these passengers takes a seat on the plane, it is necessarily true that their assigned seat is occupied. Either it was previously unoccupied (option 1 above) and they sit in it, or it was already occupied (option 2).

這些乘客中的每一個在飛機上坐下之后，一定要占用他們分配的座位。 可能是以前沒有人住過(上面的選項1)，他們坐在了里面，或者已經有人住過了(選項2)。

Before the last passenger boards the plane, the assigned seats of Passengers 2–99 are occupied. At this point, 99 people (including Passenger 1) have taken a seat, meaning that only one seat remains vacant.

在最后一位乘客登機之前，已分配了2–99位乘客的指定座位。 此時，有99人(包括乘客1)已經就座，這意味著只有一個座位空缺。

Since there is one seat left and Seats 2–99 are guaranteed to be occupied, the vacant seat must be Seat 1 or Seat 100. It is impossible for both Seat 1 and Seat 100 to be occupied before the last passenger boards, because that would mean all 100 seats on the plane are occupied by only 99 passengers.

由于只剩一個座位，并且保證要占用2至99座位，因此空座位必須是1或100座位。在最后一個乘客登機牌之前，不可能同時占用1和100座位，因為那樣會表示飛機上的所有100個座位都只有99位乘客。

Fact: there is an equal probability of the last passenger sitting in Seat 1 and Seat 100.

事實：最后一位乘客坐在1號座位和100號座位的機率相等。

By the time the last passenger boards, the outcome of the lost boarding pass problem is already determined, as there is only one seat for them to choose. We must therefore look at the decisions faced by Passengers 1–99.

到最后一個乘客登機時，已經確定了丟失登機牌問題的結果，因為他們只能選擇一個座位。 因此，我們必須研究1–99號乘客面臨的決策。

For Passenger 1, there is equal probability of choosing any of the 100 seats. By extension, the probability of him choosing his own assigned seat and the probability of him choosing the last passenger’s assigned seat are equal.

對于乘客1，選擇100個座位中的任何一個的可能性均等。 通過擴展，他選擇自己的分配座位的概率與他選擇最后一個乘客的分配座位的概率相等。

The only way Passengers 2–99 sit in Seat 1 or Seat 100 is if their assigned seat is occupied. In this case, there is also an equal probability of sitting in any available seat.

2–99號乘客坐在1號或100號座位的唯一方法是，如果他們分配的座位被占用。 在這種情況下，坐在任何可用座位上的可能性也相等。

While both Seat 1 and Seat 100 are unoccupied, it is equally probable that either seat will be chosen. After one of these two seats is occupied, the other seat is guaranteed to remain unoccupied until the last passenger boards. The probability that Seat 100 is occupied by a previous passenger is 1/2.

雖然座位1和座位100均未占用，但同樣有可能會選擇其中一個座位。 在這兩個座位中的一個座位被占用之后，另一個座位將保證在最后一個乘客登機之前保持空置。 前座乘客占用座位100的概率為1/2。

Therefore, the probability that the last passenger finds his seat unoccupied is also 1/2.

因此，最后一位乘客發現自己的座位未被占用的概率也為1/2。

Though I’m a very inexperienced coder, it was still much faster to solve the lost boarding pass problem using Monte Carlo via Python than it was to wrap my head around the analytic solution. I could say something here about the power of simulations in problem solving, but you’ve probably heard it before.

盡管我是一個非常缺乏經驗的編碼員，但是使用Monte Carlo通過Python解決登機牌丟失問題的速度要比把頭放在分析解決方案上要快得多。 我可以在這里談談模擬在解決問題中的作用，但是您以前可能已經聽說過。

Instead, I will publicly thank whoever came up with the idea of airlines being able to print boarding passes at the gate.

相反，我將公開感謝誰想到航空公司能夠在登機口打印登機牌的想法。

資料來源 (Sources)

The lost boarding pass problem doesn’t have a massive online presence, though I was able to find versions with slightly different wordings here, here, and here.

丟失登機牌問題并沒有在網上廣泛使用，盡管我能夠在這里 ， 這里和這里找到措辭略有不同的版本。