Tổng quan
Đây là câu đố hiếm mà đáp án trông như bất khả. Đoán ngẫu nhiên độc lập cho mỗi tù nhân 50% cơ hội, nên việc tất cả thành công lẽ ra phải cực kỳ khó — nhưng một chiến lược đẩy nó lên khoảng 31%, và giữ nguyên bất kể bạn thêm bao nhiêu tù nhân.
Cách giải Tù Nhân Và Những Chiếc Hộp từng bước
- Mỗi tù nhân bắt đầu ở chiếc hộp mang số của chính mình, đọc phiếu, và đi tới chiếc hộp mà phiếu đó ghi.
- Vì các phiếu là một phép thế, chuỗi này là một chu trình cuối cùng phải quay lại hộp ban đầu — và chiếc phiếu khép chu trình chính là số của bạn.
- Vậy bạn thành công đúng khi chu trình của mình không dài hơn số hộp được mở, và TẤT CẢ thành công đúng khi chu trình dài nhất của phép thế không quá n/2.
Mấu chốt
Chiến lược làm cho vận mệnh của các tù nhân tương quan tối đa thay vì độc lập. Họ không còn cần 100 lần tung xu may mắn — họ cần một phép thế may mắn, và chu trình dài thì hiếm: P(không có chu trình > n) = 1 − ln 2 ≈ 30,7%.
Biến thể & liên hệ
- Đã được chứng minh là tối ưu: không chiến lược nào vượt 1 − ln 2 với n lớn.
- Nếu các tù nhân được đổi chỗ nội dung của hai hộp trước, họ có thể phá chu trình dài duy nhất và thắng hơn 99% số lần.
Câu hỏi thường gặp
Làm sao việc làm các kết quả tương quan lại giúp được?
Vì các tù nhân chỉ quan tâm TẤT CẢ đều thành công. Các cơ hội 50% độc lập nhân lại thành gần như không; chiến lược khiến cả nhóm cùng thắng hoặc cùng thua dựa trên một điều kiện duy nhất khá dễ xảy ra.