Tổng quan
Một hàng tù nhân có thể cứu gần như tất cả chỉ bằng một quy ước chung và tính chẵn lẻ của những gì họ thấy — một cách dùng ấn tượng chỉ một bit thông tin công khai.
Cách giải Những Chiếc Mũ Tù Nhân từng bước
- Thống nhất rằng người cuối hàng thông báo tính chẵn lẻ số mũ đỏ họ thấy.
- Mỗi tù nhân phía trước theo dõi các câu đã đoán và các mũ còn thấy được.
- So sánh tính chẵn lẻ được công bố với những gì họ thấy và nghe, mỗi người suy ra màu của chính mình.
Mấu chốt
Một bit — tính chẵn lẻ của tất cả mũ ẩn — đủ để mọi người phía sau giải ra ẩn số của mình, vì mỗi câu đoán lộ thêm một mũ và cập nhật tính chẵn lẻ.
Biến thể & liên hệ
- Với vô hạn tù nhân, câu đố liên hệ tới các kết quả sâu dùng tiên đề chọn.
- Các mẹo chẵn lẻ/checksum lặp lại trong mã sửa lỗi.
Câu hỏi thường gặp
Bao nhiêu người chắc chắn sống?
Tất cả trừ có thể người nói đầu — tức n−1 trên n, người đầu có 50% cơ hội.