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

Có 100 tù nhân được đánh mã số từ 1 đến 100. Một căn phòng chứa 100 chiếc hộp đậy nắp, trên nắp có đánh thứ tự từ 1 đến 100, mỗi hộp có chứa 1 tờ giấy cũng đánh số từ 1 đến 100. Lần lượt mỗi tù nhân bước vào căn phòng và được mở ngẫu nhiên 50 hộp để kiểm tra tờ giấy bên trong hộp. Sau đó anh ta phải rời khỏi phòng và không được chia sẻ cho bất cứ tù nhân nào khác về bất cứ thông tin gì về các cái hộp trong phòng. Nếu tất cả 100 tù nhân này đều mở được hộp chứa tờ giấy có mã số trùng với mã số của mình thì tất cả đều được tha bổng, ngược lại tất cả sẽ bị hành quyết. Trước khi chơi trò chơi, các tù nhân được bàn bạc thoải mái chiến thuật chơi. Liệu rằng có phương pháp nào tối ưu cơ hội sống sót cho các tù nhân không?

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\%$

• 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à $\displaystyle \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 (Search loop)

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\ne 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 2 cho đến khi tìm ra con số của mình hoặc buộc phải ngừng vì đã đạt đến $\displaystyle \frac 1 2$ số lần tìm kiếm

🤔 Yes, một chiến thuật cực kỳ đơn giản! Nhưng tại sao nó lại tăng khả năng chiến thắng lên một cách đáng kinh ngạc như vậy?

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ị $X_1$, lại tìm kiếm hộp nhãn $X_1$, mở nắp và thấy giá trị $X_2$ 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ị , cũng là lúc anh ta khép lại search 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:

• Search loop có độ dài quá $50$ (quá giới hạn tìm kiếm), tù nhân phải ngừng tìm kiếm.

• Hoặc, anh ta tìm được $X$ với search 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 $X_k$mà ko tạo ra một search loop không? Không! Vì:

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

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

Xác suất các search 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ừ cho tổng xác suất để tồn tại loop có độ dài từ $51,52,\dots$ đến $100$

😵‍💫 Xác suất để xảy ra loop độ dài k là bao nhiêu?

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:

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à:

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

Khi $n \to +\infty:$

Demo

Và như thường lệ, xin gửi đến bạn đọc một demo thực tế:

• Bạn sẽ thấy danh sách $n$ hộp trong hình, nhiệm vụ của bạn là phải giải cứu được $n/2$ số lượng tù nhân

• Bằng cách mở nắp hộp sao cho trong $n/2$ lần mở, bạn phải tìm được ô chứa số tương ứng với tù nhân đó

• Chú ý là mỗi lần giải cứu được một tù nhân, các con số ẩn trong những cái hộp sẽ bị xáo trộn lại nhằm tránh việc người chơi nhớ vị trí cũ.

💡 Mình có bổ sung thêm phần simulator để máy chơi 100 ván và đếm số lần chiến thắng của máy. Chiến thuật của máy vẫn là chọn lựa mở hộp theo các vòng loop, tù nhân thứ i sẽ mở hộp thứ i đầu tiên.