10 tử tù đứng thành một hàng dọc. Mỗi người đội một chiếc mũ xanh hoặc đỏ hoàn toàn ngẫu nhiên. Ai cũng nhìn thấy mũ của những người phía trước nhưng không thấy mũ của mình và những người phía sau. Nói cách khác, người cuối hàng thấy mũ 9 người đứng trước, người tiếp theo thấy mũ 8 người trước… người đầu tiên không thấy gì. Từng người từ cuối tới đầu hàng phải lần lượt đoán màu mũ của mình, ai đoán đúng sẽ được trả tự do.
Họ có thể bàn luận trước khi chơi, nhưng khi trò chơi bắt đầu họ không thể trao đổi thông tin dưới bất kì hình thức nào. Người đoán chỉ được nói xanh hoặc đỏ, ai đoán sau cũng nghe thấy lời đoán của tất cả những người trước đó.
-
Họ phải làm thế nào để số người chắc chắn được trả tự do là nhiều nhất?
-
Nếu có \(K\) màu mũ khác nhau (\(K\) ≤ 10), số người chắc chắn được trả tự do là nhiều nhất là bao nhiêu?
Xem lời giải
1. Chỉ có mũ xanh và đỏ
Một phương án là người cuối hàng (người thứ 10) nói màu mũ của người thứ 9, người thứ 9 lặp lại như vậy. Tương tự, người thứ 8 cứu người thứ 7, người thứ 6 cứu người thứ 5… Làm như vậy, 50% số tử tù chắc chắn được trả tự do, tuy nhiên họ có thể làm tốt hơn như sau.
Người cuối hàng nói đỏ (hoặc xanh) nếu số người đội mũ đỏ phía trước mình là chẵn (hoặc lẻ). Dựa vào đó, người thứ 9 biết trong 9 người còn lại (kể cả chính mình) thì số người mũ đỏ là chẵn hay lẻ. Hơn nữa, người thứ 9 nhìn thấy mũ 8 người phía trước nên xác định được màu mũ của mình. Tương tự, người thứ 8 dựa vào lời nói của người thứ 9, 10 và màu mũ của 7 người phía trước để đoán ra màu mũ của mình. Cả 9 người ngoại trừ người cuối hàng (người phải đoán đầu tiên) đều đoán chính xác.
2. Có \(K\) màu mũ khác nhau
Gọi màu mũ của người thứ \(i\) là \(a_i\) (1 ≤ \(a_i\) ≤ \(K\), \(i\) = 1 -> 10, người 1 là đầu hàng, người 10 là cuối hàng). Người thứ 10 nói \(((\sum_{i=1}^{9}a_i)~mod~K) + 1\). Người thứ 9 dựa vào đó và biết \(a_1\) -> \(a_8\) nên đoán đúng màu mũ của mình \(a_9\). Tương tự, những người còn lại đều đoán đúng màu mũ của mình. Cả 9 người ngoại trừ người cuối hàng đều đoán chính xác.