Có \(N\) tử tù, ai cũng đội mũ và trên đó ghi một số tự nhiên bất kì từ \(1\) tới \(N\). Số trên mỗi chiếc mũ được chọn hoàn toàn ngẫu nhiên và không phụ thuộc vào nhau. Bất kì số nào trong khoảng \([1, N]\) cũng có thể xuất hiện trên mũ của nhiều người, hoặc không có trên mũ ai cả. Ví dụ \(N = 3\), số trên mũ của họ có thể là \((2, 3, 1)\), \((1, 1, 1)\), \((3, 2, 3)\)… có tất cả \(3^3=27\) trường hợp. Ai cũng nhìn thấy số trên mũ của những người khác ngoại trừ chính mình.
Tất cả phải đồng loạt đoán số trên mũ của mình. Nếu ít nhất một người đoán đúng thì tất cả sẽ được trả tự do.
Khi trò chơi bắt đầu (khi \(N\) tử tù bắt đầu đội mũ), không ai có thể trao đổi thông tin với nhau dưới bất cứ hình thức nào, tuy nhiên họ được thảo luận trước khi chơi. Họ phải làm thế nào để chắc chắn có ít nhất một người đoán đúng?
Xem lời giải
Giả sử số trên mũ của \(N\) tử tù là \(a_1, a_2, ..., a_N\).
Gọi \(S = ((\sum_{i=1}^{N}a_i)~mod~N) + 1\), ta có \(S \in [1, N]\).
\(N\) tử tù giao hẹn với nhau, người thứ \(i\) (\(i = 1 \rightarrow N\)) đoán \(a_i\) dựa trên giả định \(S = i\) và các số trên mũ của \(N-1\) người còn lại. \(N\) tử tù chọn \(N\) giá trị khác nhau của \(S\) nên luôn có một người chọn đúng \(S\) và sẽ đoán chính xác số trên mũ mình.