+ Tóm tắt lại đề :
Có 101 màu mũ khác nhau, đánh số từ 0 đến 100.
Có 100 người nô lệ, mỗi người được đội 1 chiếc mũ bất kỳ trong số 101 cái → luôn có 1 màu mũ bị thiếu (không ai đội).
Người đứng sau nhìn thấy mũ của tất cả người trước, người đầu hàng không thấy ai.
Mỗi người chỉ được nói 1 màu (một số từ 0 đến 100) để đoán mũ của mình.
Mục tiêu: Tìm chiến lược để ít nhất 99 người sống (tức nhiều nhất chỉ có 1 người chết).

+ Áp dụng kiến thức Số học đồng dư mod 101 :

1. Bước chuẩn bị:
Trước khi chơi, cả 100 người thống nhất đánh số các màu từ 0 → 100.
Tổng tất cả 101 số từ 0 đến 100:

T = 0 + 1 + 2 +…+ 100 = 100.1012 = 5050

Vậy : Tổng màu mũ thực tế đang đội = 5050 − m (với m là màu bị thiếu)

2. Người thứ 100 (cuối hàng) hành động:
Người 100 thấy màu mũ của 99 người trước → tính được tổng màu mũ của 99 người: gọi là SSS.
Vì không biết màu mũ của chính mình và không biết màu bị thiếu, nên người 100 sẽ đoán một màu để mã hóa giá trị màu mũ bị thiếu.
Ý tưởng: Người 100 sẽ đoán sao cho:

(Tổng tòan bộ mũ) ≡ 5050 ≡ (Tổng 100 mũ đang đội) + m    (mod101)

⇒Màu người 100 sẽ nói ra (gọi là c) = (5050 − S) mod  101

→ Người 100 có thể hi sinh nếu màu đoán không trùng màu mũ mình đang đội.

3. Người 99 trở đi suy luận (áp dụng đồng dư mod 101):
Người 99 biết:

Tổng S của 98 người phía trước (người 1 đến 98).
Biết màu đã đoán của người 100 là c.
Người 99 cũng nhìn được mũ người 1 → người 98 → tính được tổng S'.
Gọi x là màu mũ của người 99, người này sẽ giải phương trình:

x ≡ (5050 − m − S′) (mod101)

Vì người 99 đã biết m = (5050 - S - c) mod 101, thế vào là suy ra được chính xác màu của mình:

 x = (c + S − S′) mod  101

→ Tính được màu mũ của mình một cách chắc chắn.

4. Lập luận tương tự cho người 98 → 1:
Mỗi người tiếp theo đều đã biết:

Tổng các màu phía trước mình (nhìn thấy).
Các màu mà người sau đã đoán → có thể cộng vào.
Biết m từ người 100 đã nói.
Dựa vào:

M[i] = (5050 − m − Si) mod  101

→ luôn tính được màu của mình một cách chính xác.

+  Chỉ có người thứ 100 là không thể chắc chắn biết mũ của mình (vì không nhìn thấy ai).
Từ người 99 trở đi, ai cũng đủ thông tin để dùng modulo 101 suy ra chính xác màu mũ của mình.
➤ Vậy có thể chắc chắn cứu được 99 người.

+ Tóm tắt lại đề :
Có 101 màu mũ khác nhau, đánh số từ 0 đến 100.
Có 100 người nô lệ, mỗi người được đội 1 chiếc mũ bất kỳ trong số 101 cái → luôn có 1 màu mũ bị thiếu (không ai đội).
Người đứng sau nhìn thấy mũ của tất cả người trước, người đầu hàng không thấy ai.
Mỗi người chỉ được nói 1 màu (một số từ 0 đến 100) để đoán mũ của mình.
Mục tiêu: Tìm chiến lược để ít nhất 99 người sống (tức nhiều nhất chỉ có 1 người chết).

+ Áp dụng kiến thức Số học đồng dư mod 101 :

1. Bước chuẩn bị:
Trước khi chơi, cả 100 người thống nhất đánh số các màu từ 0 → 100.
Tổng tất cả 101 số từ 0 đến 100:

T = 0 + 1 + 2 +…+ 100 =
100
.
101
2
= 5050

Vậy : Tổng màu mũ thực tế đang đội = 5050 − m (với m là màu bị thiếu)

2. Người thứ 100 (cuối hàng) hành động:
Người 100 thấy màu mũ của 99 người trước → tính được tổng màu mũ của 99 người: gọi là SSS.
Vì không biết màu mũ của chính mình và không biết màu bị thiếu, nên người 100 sẽ đoán một màu để mã hóa giá trị màu mũ bị thiếu.
Ý tưởng: Người 100 sẽ đoán sao cho:

(Tổng tòan bộ mũ) ≡ 5050 ≡ (Tổng 100 mũ đang đội) + m (mod101)

⇒Màu người 100 sẽ nói ra (gọi là c) = (5050 − S) mod  101

→ Người 100 có thể hi sinh nếu màu đoán không trùng màu mũ mình đang đội.

3. Người 99 trở đi suy luận (áp dụng đồng dư mod 101):
Người 99 biết:

Tổng S của 98 người phía trước (người 1 đến 98).
Biết màu đã đoán của người 100 là c.
Người 99 cũng nhìn được mũ người 1 → người 98 → tính được tổng S'.
Gọi x là màu mũ của người 99, người này sẽ giải phương trình:

x ≡ (5050 − m − S′) (mod101)

Vì người 99 đã biết m = (5050 - S - c) mod 101, thế vào là suy ra được chính xác màu của mình:

x = (c + S − S′) mod  101

→ Tính được màu mũ của mình một cách chắc chắn.

4. Lập luận tương tự cho người 98 → 1:
Mỗi người tiếp theo đều đã biết:

Tổng các màu phía trước mình (nhìn thấy).
Các màu mà người sau đã đoán → có thể cộng vào.
Biết m từ người 100 đã nói.
Dựa vào:

M[i] = (5050 − m − Si) mod  101

→ luôn tính được màu của mình một cách chính xác.

+ Chỉ có người thứ 100 là không thể chắc chắn biết mũ của mình (vì không nhìn thấy ai).
Từ người 99 trở đi, ai cũng đủ thông tin để dùng modulo 101 suy ra chính xác màu mũ của mình.
➤ Vậy có thể chắc chắn cứu được 99 người.