100 chiếc mũ
100 người thông minh xếp thành một hàng dọc và được người khác đội lên đầu mũ màu xanh hoặc màu đỏ. Không ai biết mũ của mình hoặc những người đứng sau mình màu gì, nhưng có thể nhìn thấy mũ của tất cả những người đứng trước. Người cuối hàng sẽ nói màu mũ của mình đầu tiên, sau đó lần lượt mọi người cho tới người đầu hàng nói màu mũ của mình. Trước khi xếp hàng họ đã bàn bạc với nhau để 99 người có thể nói đúng màu mũ của mình, hỏi họ đã bàn bạc với nhau như thế nào?
Lưu ý rằng mỗi người chỉ được nói màu mũ của mình, không được dùng ám hiệu. Mỗi người đều có thể nghe được câu trả lời của mọi người khác.
Mỗi người đều có thể nghe thấy mọi người đứng sau và nhìn thấy mọi người đứng trước. Làm thế nào để có thể tận dụng thông tin ấy? Phương pháp ở đây là dùng tính chẵn lẻ. Giả sử rằng một người biết rằng tính cả mình và tất cả những người đứng trước thì số mũ đỏ là chẵn, nhưng số mũ đỏ mà người đó nhìn thấy lại là số lẻ, thì người đó có thể kết luận mình đội mũ đỏ. Nếu tính chẵn lẻ đã được biết trước, thì kể từ người đầu tiên nói đúng màu mũ, tất cả những người đứng trước đều có thể nói đúng.
Từ quan sát trên ta có thể đề xuất phương án sau.
Bước 1: Người cuối cùng (vị trí 100)
Quan sát 99 người phía trước, đếm số mũ đỏ
Quy ước truyền thông tin:
Nếu số mũ đỏ nhìn thấy là chẵn → nói "Tôi đội mũ đỏ"
Nếu số mũ đỏ nhìn thấy là lẻ → nói "Tôi đội mũ xanh"
Lưu ý: Câu trả lời này không liên quan đến mũ thật của họ, chỉ là mã hóa thông tin chẵn/lẻ cho nhóm 99 người phía trước.
Bước 2: Người thứ 99
Nghe câu trả lời của người 100 → biết tính chẵn lẻ tổng số mũ đỏ từ vị trí 1 → 99
Quan sát 98 người phía trước → biết số mũ đỏ từ vị trí 1 → 98
Suy luận mũ của mình:
Nếu tính chẵn lẻ tổng (1→99) khớp với số mũ đỏ quan sát (1→98) → mũ mình là xanh
Nếu tính chẵn lẻ tổng (1→99) không khớp → mũ mình là đỏ
Trả lời đúng màu mũ thật của mình.
Tương tự như người thứ 99, tất cả mọi người còn lại sẽ đều có thể nói đúng màu mũ của mình.