100 prisoners problem

 Bài toán 100 tù nhân - 100 prisoners problem này lần đầu tiên được công bố vào năm 2003 bởi nhà khoa học máy tính người Đan Mạch Peter Bro Miltersen. Bài toán 100 tù nhân có nhiều phiên bản khác nhau trong tài liệu toán học, nhưng nguyên tắc luôn giống nhau. Đây là một trong số các phiên bản của bài toán:

 

Cai ngục của một nhà tù cho 100 tử tù, được đánh số từ 1 đến 100, một cơ hội cuối cùng. Một căn phòng chứa một cái tủ với 100 ngăn kéo. Giám đốc đặt ngẫu nhiên số của một tù nhân trong mỗi ngăn kéo đã đóng. Các tù nhân lần lượt vào phòng. Mỗi tù nhân có thể mở và xem xét 50 ngăn kéo theo thứ tự bất kỳ. Các ngăn kéo được đóng lại sau đó. Nếu, trong quá trình tìm kiếm này, mọi tù nhân tìm thấy số của mình trong một trong các ngăn kéo, tất cả các tù nhân đều ân xá. Chỉ cần một tù nhân không tìm thấy số của mình, tất cả tù nhân sẽ chết. Trước khi tù nhân đầu tiên bước vào phòng, các tù nhân có thể thảo luận về chiến lược nhưng không được giao tiếp khi tù nhân đầu tiên bước vào để tìm trong các ngăn kéo.

 Chiến lược tốt nhất của tù nhân là gì?

(Nguồn: https://en.wikipedia.org/wiki/100_prisoners_problem)

  

Bản gốc bằng tiếng Anh

 

The director of a prison offers 100 death row prisoners, who are numbered from 1 to 100, a last chance. A room contains a cupboard with 100 drawers. The director randomly puts one prisoner’s number in each closed drawer. The prisoners enter the room, one after another. Each prisoner may open and look into 50 drawers in any order. The drawers are closed again afterwards. If, during this search, every prisoner finds his number in one of the drawers, all prisoners are pardoned. If just one prisoner does not find his number, all prisoners die. Before the first prisoner enters the room, the prisoners may discuss strategy—but may not communicate once the first prisoner enters to look in the drawers.

 What is the prisoners’ best strategy?

 

Lời giải cho bài toán

Nếu mỗi tù nhân chọn ngẫu nhiên 50 ngăn kéo, thì mỗi tù nhân sẽ có xác suất 0,5 để tìm số của chính họ và tất cả các tù nhân sẽ có xác suất kết hợp (1/2)^100 để được ân xá. Tuy nhiên, tồn tại một chiến lược mang lại cho các tù nhân xác suất thành công của hơn 30%. Chìa khóa của chiến lược đó là mỗi tù nhân có thể sử dụng thông tin từ các ngăn kéo trước đó để chọn mở ngăn kéo tiếp theo. Mấu chốt của chiến lược này là xác suất thành công của mỗi tù nhân là không không còn độc lập với xác suất thành công của các tù nhân khác.

Bạn có thấy bóng dáng của suy diễn Bayes trong bài toán này không 😊

 

Tài liệu tham khảo:

[1].              http://datagenetics.com/blog/december42014/index.html

[2].              https://math.mit.edu/~apost/courses/18.204_2018/Timothee_Schoen_paper.pdf

[3].              https://www.r-bloggers.com/2010/07/100-prisoners-100-lines-of-code/