Một câu đố đến lúc biết lời giải cũng không tin nổi!

Thoạt tiên, nếu phân tích theo cách thông thường, mỗi tù nhân được mở 50 hộp, và không được tiết lộ thông tin gì cho các tù nhân khác có thể được hiểu là:

• Đây là một phép thử có xác suất là \(50\% = \frac 1 2\)

• Các phép thử hoàn toàn độc lập

Như vậy, xác suất để toàn bộ 100 tù nhân được tha (ai cũng mở được hộp mang tờ giấy có mã số của mình) là \(\left( \frac 1 2 \right)^{100} = \frac 1 {2^{100}} \) . Một xác suất siêu siêu siêu nhỏ!!!

Tuy nhiên, Giáo sư Peter Bro Miltersen đã đưa ra một chiến lược tuyệt vời để đẩy xác suất thắng của trò chơi lên con số gần \(30\%\) trong bài báo “The cell probe complexity of succinct data structures”. Bạn hoàn toàn có thể tìm kiếm bài báo này của ông trên internet.

Chiến thuật dò theo dây chuyền

Thực ra, giáo sư không hề đặt tên cho chiến thuật này, mình tạm thời đặt tên cho chiến thuật này dựa trên mô tả của nó:

• Bước 1: Mỗi tù nhân mang mã số X bước vào phòng, tìm hộp có nắp cùng với mã số của mình rồi mở nó ra và nhìn thấy tờ giấy trong hộp mang mã số Y

• Bước 2: Nếu Y khớp với mã số X của anh ta ==> dừng và rời khỏi phòng.

• Bước 3: Nếu X khác Y thì tiếp tục tìm đến hộp nó nắp có mã số là Y và quay lại Bước 1.

Các search loop…

Đầu tiên, có thể nhận xét rằng cách dò tìm dây chuyền như trên sẽ tạo ra một vòng loop tìm kiếm dây chuyền. Thật vậy, nếu bỏ qua điều kiện giới hạn số lượng hộp mở, khi một tù nhân mã số X, bắt đầu mở nắp hộp mang nhãn X, tìm thấy giá trị X1, lại tìm kiếm nắp hộp X1, mở nắp và thấy giá trị X2 và cứ tiếp diễn như vậy. Vì số lượng hộp là có giới hạn, nên tới một lúc nào đó, anh ta sẽ chắc chắn kiếm được hộp có giá trị X. Chính lúc tìm thấy giá trị X, cũng là lúc anh ta khép lại vòng loop (vì nếu vẫn làm theo chiến thuật dây chuyền, anh ta sẽ đến hộp mang nhãn X ban đầu).

Như vậy chỉ có 2 trường hợp xảy ra với cách tìm kiếm như thế này:

• Vòng loop có độ dài quá 50, tù nhân phải ngừng tìm kiếm.

• Hoặc, anh ta tìm được X vì vòng loop có độ dài bé hơn hoặc bằng 50.

Một câu hỏi đặt ra rằng liệu có khi nào dây chuyền này ngừng giữa chừng ngay tại hộp nhãn Xk mà ko tạo ra một vòng loop không? Không! Vì:

• Lý do bạn mở mộp hộp nhẵn Xk nào đó là vì trước đó bạn đã tìm thấy giá trị Xk ở một hộp khác.

• Mỗi giá trị Xk chỉ xuất hiện 1 lần duy nhất, nếu đã tìm thấy Xk ở hộp khác rồi thì hộp mang nhãn Xk không thể có giá trị là Xk.

Xác suất các vòng loop

Chúng ta có 100 chiếc hộp, như vậy, sẽ có thể có 100 độ dài của các vòng loop được tạo ra:

• Độ dài 1 tương ứng với hộp có chứa giá trị cùng với nhãn của nó.

• Độ dài 100 tương ứng với một dây chuyền mở ra tất cả 100 hộp.

Như vậy để chiến thắng trò chơi, nhất định không tồn tại một loop có độ dài quá 50. Nghĩa là, tỷ lệ chiến thắng có thể được tính bằng 1 trừ tổng xác suất để tồn tại loop có độ dài từ 51, 52, … đến 100.

Gọi \(P(L=k)\) là tỷ lệ để có loop độ dài \(k\) trong \(n\) phần tử. Tỷ lệ này được tính bằng tổng số loop độ dài \(k\) với \(n \) phần tử, \(S_n^k\), chia cho số hoán vị tạo ra được từ \(n\) phần tử, \(S_n\).

• \(S_n = n!\)

• \(S_n^k\) = [số loop riêng biệt độ dài \(k\) từ \(n\) phần tử] \(\times\)[số hoán vị của \(k\) phần tử trong loop đó] = \(\displaystyle [\frac {n.(n-1)(n-2)\dots(n-(k-1))} {k}] \times [(n-k)!] = \frac {n!} k\)

Vậy:

$$\boxed{ P(L=k) = \frac {S_n^k} {S_n} = \frac {\frac{n!}{k}} {n!} = \frac 1 k}$$

Như vậy, ta tính được tỷ lệ thắng cuộc của các tù nhân nếu áp dụng chiến thuật trên là:

$$P(win) = 1 - (\frac {1} {51} + \frac {1} {52} + \dots + \frac {1} {100}) \approx 1 - 0.69 = 0.31$$

Một cách tổng quát:

$$\boxed {P(win) = 1 - \int_n^{2n}\frac 1 xdx = 1 - (\ln|2n| - \ln|n|)}$$

Khi \(n \to +\infty:\)

$$\begin{align*} \ln |2n| - \ln |n| &= \ln 2n - \ln n \\ &= \ln 2n + \ln \frac 1 n \\ &= \ln (2n. \frac 1 n) = \ln2 \approx 0.693 \\ &\implies P(win) = 1 - 0.693 = 0.307 \end{align*}$$