Ba tử tù ngồi quanh một bàn tròn, mỗi người đội một chiếc mũ. Màu mũ của từng người được chọn hoàn toàn ngẫu nhiên, không phụ thuộc vào nhau, và có thể là xanh (50%) hoặc đỏ (50%). Cả ba đều thấy mũ hai người còn lại nhưng không thấy mũ của mình. Mỗi người được phát một tờ giấy và phải chọn một trong ba câu trả lời sau:
- Tôi đội mũ xanh
- Tôi đội mũ đỏ
- Bỏ qua
Nếu ít nhất một người đoán đúng và không ai đoán sai thì họ được trả tự do.
Khi trò chơi bắt đầu (khi ba người bắt đầu đội mũ), họ không thể trao đổi thông tin với nhau hoặc nhìn dự đoán của người khác dưới bất cứ hình thức nào. Họ phải trả lời thế nào để xác suất thắng cuộc là cao nhất?
Xem lời giải
Ba tử tù có thể đoán như sau: hai người luôn chọn Bỏ qua, người còn lại đoán mũ mình màu xanh (hoặc đỏ). Làm như vậy khả năng họ được trả tự do là 50%. Cách tối ưu dựa trên error coding theory (distance-3 Hamming code) như sau.
Bất cứ ai nếu thấy hai người còn lại đội mũ cùng màu sẽ đoán mũ mình có màu khác, còn không thì chọn Bỏ qua. Với cách này họ chỉ thua khi tất cả mang mũ đồng màu (xác suất 2/8 = 1/4). Nói cách khác, ba tử tù được trả tự do với xác suất 75%.