Nếu mỗi tù nhân chọn 50 hộp một cách ngẫu nhiên, xác suất để một người thành công là $1/2$. Xác suất để cả 100 người cùng thành công sẽ là $(1/2)^{100}$, một con số cực kỳ nhỏ (xấp xỉ $0,0000000000000000000000000000008$), gần như bằng 0.

Tuy nhiên, có một chiến lược giúp họ nâng cơ hội chiến thắng lên đến hơn 30%.

Chiến lược: Theo đuổi các chu kỳ (Cycle-following)
Trước khi bắt đầu, các tù nhân đồng ý với nhau một quy tắc đơn giản: Mỗi người sẽ bắt đầu bằng cách mở chiếc hộp có số thứ tự trùng với số của chính mình.

Tù nhân số $k$ sẽ mở chiếc hộp số $k$.
Nếu số bên trong hộp là $k$, anh ta thành công.
Nếu số bên trong hộp là một số khác (gọi là $j$), anh ta sẽ tiếp tục mở chiếc hộp số $j$.
Anh ta cứ tiếp tục quá trình này: lấy số trong hộp hiện tại làm chỉ dẫn để mở chiếc hộp tiếp theo, cho đến khi tìm thấy số $k$ của mình hoặc đã mở đủ 50 hộp.
Tại sao chiến lược này lại hiệu quả?
Về mặt toán học, cách sắp xếp các con số trong 100 chiếc hộp tạo thành một hoán vị. Bất kỳ hoán vị nào cũng có thể được phân tích thành các chu kỳ rời nhau.

Ví dụ: Hộp 1 chứa số 5, Hộp 5 chứa số 2, Hộp 2 chứa số 1 $\rightarrow$ Đây là một chu kỳ độ dài 3 (1-5-2).
Điểm mấu chốt:

Nếu tù nhân số $k$ nằm trong một chu kỳ, anh ta chắc chắn sẽ tìm thấy số của mình nếu anh ta đi hết chu kỳ đó.
Vì mỗi người được mở 50 hộp, nên tất cả tù nhân sẽ thành công NẾU VÀ CHỈ NẾU hoán vị của các hộp không chứa bất kỳ chu kỳ nào có độ dài lớn hơn 50.
Xác suất thành công
Xác suất để một hoán vị ngẫu nhiên của 100 phần tử không có chu kỳ nào dài hơn 50 được tính bằng công thức:

$1 - \left( \frac{1}{51} + \frac{1}{52} + \dots + \frac{1}{100} \right)$
Giá trị này xấp xỉ 31,18%.

Kết luận
Bằng cách liên kết các lựa chọn lại với nhau dựa trên cấu trúc của các con số thay vì chọn ngẫu nhiên, các tù nhân đã biến một trò chơi gần như tuyệt vọng thành một cơ hội có xác suất thắng khá cao (gần 1/3).

Đây là một bài toán xác suất nổi tiếng được gọi là "Bài toán 100 tù nhân". Thoạt nhìn, cơ hội để tất cả 100 người cùng tìm thấy số của mình có vẻ cực kỳ thấp ($(\frac{1}{2})^{100}$, một con số gần như bằng 0). Tuy nhiên, có một chiến lược giúp họ đạt tỉ lệ thắng lên tới hơn 30%.

1. Chiến lược tối ưu: "Chiến thuật theo chu trình"
Thay vì chọn ngẫu nhiên 50 hộp, mỗi tù nhân sẽ tuân theo một quy luật liên kết giữa số của mình và số ghi trong hộp:

Bước 1: Tù nhân đầu tiên (người có số $k$) bước vào phòng và mở chiếc hộp số $k$.
Bước 2: Nếu số bên trong hộp là $k$, anh ta đã thành công và dừng lại.
Bước 3: Nếu số bên trong hộp không phải là $k$ (giả sử là số $m$), anh ta sẽ tiếp tục mở hộp số $m$.
Bước 4: Anh ta lặp lại quy trình này: dùng số tìm thấy trong hộp hiện tại để làm chỉ dẫn mở chiếc hộp tiếp theo, cho đến khi tìm thấy số $k$ của mình hoặc đã mở đủ 50 hộp.

2. Tại sao chiến lược này lại hiệu quả?
Trong toán học, việc sắp xếp 100 số vào 100 hộp có thể được coi là một hoán vị. Bất kỳ hoán vị nào cũng có thể phân tích thành các chu trình rời nhau.

Ví dụ: Hộp 1 chứa số 5, hộp 5 chứa số 2, hộp 2 chứa số 1. Đây là một chu trình: $1 \rightarrow 5 \rightarrow 2 \rightarrow 1$.
Điểm mấu chốt:

Nếu một tù nhân bắt đầu bằng chiếc hộp ghi số của chính mình, anh ta chắc chắn đang nằm trong chu trình chứa số đó.
Anh ta sẽ tìm thấy số của mình nếu và chỉ nếu độ dài của chu trình đó nhỏ hơn hoặc bằng 50.
Vì tất cả tù nhân trong cùng một chu trình sẽ cùng thắng hoặc cùng thua, vận mệnh của họ giờ đây chỉ phụ thuộc vào một điều duy nhất: Trong 100 chiếc hộp đó, có chu trình nào dài hơn 50 hay không?

3. Xác suất thành công
Các tù nhân sẽ được thả tự do nếu trong hoán vị ngẫu nhiên của 100 hộp không có chu trình nào dài hơn 50.

Xác suất để có một chu trình độ dài $L$ (với $L > 50$) là $\frac{1}{L}$. Vì không thể có hai chu trình dài hơn 50 cùng lúc, tổng xác suất thất bại là:

$P_{thua} = \frac{1}{51} + \frac{1}{52} + \frac{1}{53} + \dots + \frac{1}{100}$
Xác suất thành công sẽ là:

$P_{thắng} = 1 - \left( \frac{1}{51} + \frac{1}{52} + \dots + \frac{1}{100} \right) \approx 1 - \ln(2) \approx 0.3118$
Kết quả: Với chiến lược này, tỉ lệ thắng của họ là khoảng 31,18%, một con số kinh ngạc so với việc chọn ngẫu nhiên!