Tên của 100 tù nhân được xếp ngẫu nhiên trong 100 chiếc hộp khác nhau, mỗi hộp một tên. Hộp được xếp thành hàng ngang và đặt trong phòng kín. Từng tù nhân lần lượt vào phòng và được phép mở nhiều nhất 50 hộp tùy chọn để tìm tên mình. Sau khi xem tối đa 50 hộp, tù nhân rời phòng và tới lượt người tiếp theo vào.
Biết rằng tù nhân không được
- thay đổi vị trí các hộp,
- xáo trộn tên trong hộp,
- trao đổi thông tin với người khác dưới bất kì hình thức nào.
Họ có thể thảo luận cách chọn hộp trước khi trò chơi bắt đầu, nếu tất cả đều tìm thấy tên mình thì họ được trả tự do.
Làm thế nào để xác suất tất cả đều tìm thấy tên mình lớn hơn 30%?
Nếu ai cũng chọn 50 hộp bất kì thì xác suất một người tìm thấy tên mình là \(\frac{50}{100} = \frac{1}{2}\). Như vậy, xác suất cả 100 tù nhân đều tìm thấy tên mình là \((\frac{1}{2})^{100} \approx 8 \cdot 10^{−31}\). Còn nếu ai cũng chọn 50 hộp giống nhau thì họ bao giờ cũng thua. Xác suất lớn hơn 30% dường như không tưởng nhưng bạn không nghe nhầm đâu.
Xem lời giải
Các tù nhân quy ước với nhau mỗi người tương ứng với một số thứ tự riêng trong khoảng [1, 100], và hộp được đánh số 1 tới 100 từ trái qua phải. Khi tù nhân i vào phòng, anh ta mở hộp i và xem tên trong đó. Giả sử trong hộp i là tên người j, anh ta lại mở hộp j để kiểm tra. Anh ta cứ tiếp tục chọn hộp như vậy cho tới khi tìm được tên mình hoặc đã mở tới 50 hộp.
Tại sao làm như vậy thì tất cả đều tìm thấy tên mình với xác suất hơn 30%?
Quá trình đánh số thứ tự các tù nhân bản chất là chọn một hoán vị ngẫu nhiên 𝜑 của dãy số {1, 2, …, 100}. Cách mở hộp của mỗi tù nhân là lần theo chu trình hoán vị bắt đầu từ số thứ tự của tù nhân đó. Nếu 𝜑 không tồn tại chu trình nào nhiều hơn 50 phần tử, tất cả các tù nhân sẽ đều tìm thấy tên mình.
Xét trường hợp tổng quát: tính xác suất một hoán vị ngẫu nhiên của dãy số {1, 2, …, 2\(\cdot\) \(n\)} không có chu trình nào dài hơn \(n\).
Trước hết ta đếm số hoán vị có chu trình 𝐶 với độ dài \(k\), \(k > n\).
- Có \(\dbinom{2 \cdot n}{k}\) cách chọn \(k\) phần tử của chu trình 𝐶.
- Số cách sắp xếp \(k\) phần tử này trong chu trình 𝐶 là \(\frac{k!}{k}=(k-1)!\)
- Số cách sắp xếp \(2 \cdot n - k\) phần tử còn lại là \((2 \cdot n - k)!\)
Vì \(k > n\) nên chỉ có nhiều nhất một chu trình có độ dài \(k\) trong một hoán vị. Số hoán vị có chu trình 𝐶 với độ dài \(k\) là:
\begin{align} \dbinom{2 \cdot n}{k} \cdot (k-1)! \cdot (2 \cdot n - k)! = \frac{(2 \cdot n)!}{k} \end{align}
Xác suất một hoán vị ngẫu nhiên có chu trình có độ dài \(k\) là:
\begin{align} \frac{(2 \cdot n)!}{k} / (2 \cdot n)! = \frac{1}{k} \end{align}
Xác suất một hoán vị ngẫu nhiên không có chu trình dài hơn \(n\) là:
\begin{align} 1 - \sum_{k=n+1}^{2 \cdot n}\frac{1}{k} & \approx 1 - ln(2 \cdot n) + ln(n) \newline & \approx 1 - ln(2) \newline & \approx 0.30685 \end{align}
Xác suất cả 100 tù nhân đều tìm thấy tên mình là 30.685%.