Than tham tho map

Để cho đơn giản thì tạm coi là chỉ có 5 người với 6 màu mũ từ 1 đến 6. (tại lười ngồi tính hoán vị chẵn lẻ của chuỗi 101 số).

Trước tiên chúng ta phải giải thích về tính chẵn lẻ của một hoán vị.

Ví dụ 1: từ hoán vị [3,5,2,1,4,6], cần đổi chỗ bao nhiêu lần để thu được hoán vị xếp tăng [1,2,3,4,5,6] ? Trước tiên chúng ta cần đổi chỗ số 1 và 3 cho nhau, thu được [1,5,2,3,4,6]. Tiếp đến cần đổi chỗ số 2 và 5 cho nhau, thu được [1,2,5,3,4,6]. Tiếp tục đổi chỗ số 3 và 5 cho nhau, thu được [1,2,3,5,4,6]. Cuối cùng là đổi chỗ 4 và 5 cho nhau để thu được [1,2,3,4,5,6] => tất cả cần 4 lần đổi chỗ => Ta gọi [3,5,2,1,4,6] là hoán vị chẵn (vì cần chẵn lần đổi chỗ để thu được hoán vị [1,2,3,4,5,6]).

Ví dụ 2: từ hoán vị [5,1,2,3,6,4], cần đổi chỗ bao nhiêu lần để thu được hoán vị [1,2,3,4,5,6] => đổi 1 và 5 cho nhau, thu được [1,5,2,3,6,4], đổi 2 và 5 cho nhau thu được [1,2,5,3,6,4], đổi 3 và 5 cho nhau thu được [1,2,3,5,6,4], đổi 4 và 5 cho nhau thu được [1,2,3,4,6,5], cuối cùng là đổi 5 và 6 cho nhau thu được [1,2,3,4,5,6] => cần 5 lần đổi chỗ => ta gọi [5,1,2,3,6,4] là hoán vị lẻ (vì cần lẻ lần đổi chỗ).

(có thể thấy quy trình trên chính là quy trình sort hay xếp tăng dãy số, nhưng chúng ta tạm bỏ qua vấn đề làm sao để sort chuỗi 101 số một cách nhanh nhất, thôi cứ giả sử như tất cả đám nô lệ này đều có khả năng tư duy toán học đỉnh cao đi vậy )

Giả sử mũ dư ở ngoài có màu 3 còn 5 người nô lệ đội mũ tạo thành chuỗi 4,5,2,1,6. Người nô lệ phải đoán đầu tiên sẽ tưởng tượng có 1 người đứng sau mình đang đội mũ dư để tạo thành 1 chuỗi 6 số hoàn chỉnh là 3-4-5-2-1-6. Tuy nhiên, do người này chỉ nhìn thấy mũ của những người đứng trước (5-2-1-6) nên luôn luôn bị phân vân giữa 2 khả năng, cụ thể như trong ví dụ này thì sẽ phân vân giữa 4-3-5-2-1-6 hoặc 3-4-5-2-1-6 (tức là không biết mình đổi mũ màu 3 hay màu 4, mũ dư ở sau lưng mình là màu 4 hay màu 3). Do 2 chuỗi này chỉ sai khác nhau đúng 1 lần đổi chỗ, nên chắc chắn có 1 hoán vị chẵn và 1 hoán vị lẻ. Những người nô lệ sẽ quy ước sẵn với nhau là người đầu tiên luôn luôn chọn đoán hoán vị chẵn => cụ thể trong tình huống này thì sẽ đoán 4-3-5-2-1-6, tức là đoán bản thân đang đội màu 3. Khá đen cho anh trong tình huống 50/50 này anh đã chết. Tuy nhiên, sự hy sinh của anh không phải là vô nghĩa, vì điều này đã giúp những người còn lại biết được hoán vị đúng phải là hoán vị lẻ => Kể từ những người sau, tất cả đều chọn đoán hoán vị lẻ (giả sử như người đầu tiên đoán hoán vị chẵn và sống sót thì mọi người sẽ đều chọn đoán hoán vị chẵn). Chú ý đề bài có giả thiết quan trọng đó là "từng người sẽ đoán màu mũ của mình, nếu đoán đúng sẽ được tha chết, đoán sai sẽ bị hành quyết ngay lập tức", nghĩa là những người phía sau dựa vào việc người đầu tiên có bị hành quyết ngay lập tức không để biết được chuỗi hoàn chỉnh là hoán vị chẵn hay lẻ.

Tiếp tục với ví dụ trên, sau khi người đầu tiên đoán màu 3 và chết, chúng ta biết được chuỗi đầy đủ là hoán vị lẻ. Người tiếp theo (đội mũ màu 5) nhìn thấy trước mặt mình là dãy 2-1-6, và nghe được người đầu tiên đoán màu 3 (sai) nên suy ra mũ dư là màu 3, nên bản thân mình sẽ đội mũ màu 4 hoặc màu 5 (và mũ của người đầu tiên là màu 5 hoặc màu 4) => phân vân giữa 3-4-5-2-1-6 (hoán vị này lẻ) hoặc 3-5-4-2-1-6 (hoán vị này chẵn). Do chúng ta biết được chuỗi đầy đủ là hoán vị lẻ => chọn 3-4-5-2-1-6, tức là đoán bản thân mình đội mũ màu 5 => chính xác và sống sót.

Tương tự cho người tiếp theo (đội mũ màu 2), nhìn thấy trước mặt mình là dãy 1-6, nghe được người đầu tiên đoán màu 3 (sai), và người tiếp theo đoán màu 5 (đúng) => phân vân giữa 3-4-5-2-1-6 (lẻ) và 3-2-4-5-1-6 (chẵn), (tức là phân vân giữa mũ của mình và mũ của người đầu tiên, ai là 2 ai là 4) => chọn đoán hoán vị lẻ => đoán bản thân đội màu 2 => chính xác và sống sót.

....

Mỗi người còn lại đều phân vân giữa 2 lựa chọn (sai khác nhau 1 lần đổi chỗ nên luôn luôn có 1 hoán vị chẵn và 1 hoán vị lẻ) => Do trong ví dụ này, người đầu tiên đoán hoán vị chẵn và chết ngay lập tức nên những người còn lại lựa chọn đoán hoán vị lẻ là đều chính xác hết

=> Nếu như chuỗi hoàn chỉnh là hoán vị lẻ thì chỉ có người đầu tiên chết, 99 người còn lại sống, còn nếu chuỗi hoàn chỉnh là hoán vị chẵn thì toàn bộ 100 người đều sống.