Câu đố khó nhất thế giới ?

Để 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.

Mình nghĩ là người thứ 100 sẽ nói màu mà được kết hợp giữa 2 màu còn thiếu, ví dụ 99 màu trước thiếu màu đỏ và màu vàng thì sẽ trả lời là màu cam (hoặc ví dụ về đánh số thì 100 + 101 = 201) từ đó người phía trước loại trừ mà chọn được đáp án đúng

Quy 101 màu về các số từ 1 -> 101. Người thứ 100 cộng các số của người thứ 1 -> 99, lấy số dư khi chia cho 101 rồi đọc màu tương ứng với số dư đó (người 100 chết). Người thứ 99 cũng cộng các số của người thứ 1 -> 98, lấy dư khi chia 101 rồi so sánh vs dư của người 100 vừa đọc để tìm ra số của mình. Những người còn làm làm tương tự thì sẽ cứu được 99 người. Cách này không biết có lỗ hổng nào không nhỉ?

wow

Để cứu được số lượng lớn nhất có thể (99 người), người cuối cùng trong hàng (người thứ 100) sẽ chọn chiếc mũ màu phổ biến nhất trong số các mũ mà người trước đó (người thứ 99) đang thấy. Điều này sẽ tăng khả năng người thứ 99 đoán đúng màu mũ của mình.

Dưới đây là cách thức hoạt động:

Người thứ 100 (người cuối hàng): Người này không thấy màu mũ nào cả, nhưng anh ấy có thể đếm số lượng các màu mũ trong hàng trước mắt mình. Nếu anh ấy thấy có một màu mũ xuất hiện nhiều nhất, anh ấy sẽ đoán màu của mình là màu đó. Người thứ 99: Người này có thể đếm số lượng mũ màu được chọn bởi người thứ 98, nếu một màu mũ nhất định được chọn nhiều hơn một màu khác, người thứ 99 sẽ đoán màu mũ của mình dựa trên màu mũ được chọn nhiều nhất này. Quy trình tiếp tục cho đến người cuối cùng (người thứ 1): Mỗi người sẽ xem xét màu mũ xuất hiện nhiều nhất trong số mũ được chọn bởi người đứng trước đó và đoán màu mũ của mình dựa trên thông tin này. Tuy nhiên, không thể chắc chắn cứu được 99 người vì kết quả cuối cùng phụ thuộc vào sự chọn lựa thông minh và may mắn của người thứ 100 khi quyết định chọn màu mũ dựa trên thông tin không chính xác (vì không có cách gì để người thứ 100 có thể biết chính xác màu mũ của mình).

Nếu một ngày bài này đủ 99 Upvote mình sẽ đưa ra lời giải :3 (mỗi upvote cứu 1 người)

Nếu nói màu của mũ thì khó hiểu nên mình sẽ thay đổi thành 101 mũ sẽ được đánh số từ 1 -> 101. Giả sử:

• Nô lệ từ 1 -> 99 sẽ đội mũ từ 1 -> 99 => lúc này nô lệ 100 thấy được số mũ của 99 nô lệ đứng trước sẽ biết được xác xuất số của mình là 50-50 (giả sử 100 hoặc 101)
• Nô lệ 100 sẽ đoán số mũ của mình và báo cho nô lệ 99 biết, nếu nô lệ 100 đoán đúng thì các nô lệ phía trước sẽ sử dụng phương pháp loại trừ từ những nô lệ đứng trước và đáp án của nô lệ 100
• Nếu nô lệ 100 đoán trúng thì có 100 nô lệ sống, nếu nô lệ 100 đoán sai thì sẽ có 99 nô lệ sống

Vì số mũ là 101 > 100 người nô lệ mà người nô lệ 100 đứng sau cùng thấy hết mũ của 99 người phía trước nên anh ta sẽ phải chọn 1 trong 2 mũ còn lại giả sử 2 màu mũ còn lại là x và y nếu người 100 chọn màu mũ x sẽ sảy ra 2 TH. TH1: người 100 đoán đúng Người 99 sẽ biết được 98 mũ phía trước + mũ x (người 100 vừa đoán đúng) vậy thì người 99 sẽ phải đoán 1 trong 2 mũ còn lại nếu người 99 chọn đúng, người 98 sẽ tiếp tục vòng lặp này cho đến khi có người chọn sai thì người phía trước sẽ nhảy xuống TH2 => chỉ có một người chết TH2: người 100 đoán sai và bị hành quyết ngay lập tức Người 99 sẽ biết được 98 mũ phía trước + mũ x (người 100 vừa chọn) + mũ y (màu mũ chắc chắn của người 100) => chỉ còn 1 mũ có thể chọn cũng là mũ chính xác của người 99 Người 98 sẽ tiếp tục suy luận theo cách người 99 vừa làm cho đến người đầu tiên => chỉ có người 100 phải chết => có thể cứu chắc chắn được 99 người

người 100 thay vì đoán màu mũ sẽ nói cho mọi người biết 2 màu còn thiếu (101 màu - 99 mũ phía trước ) để giúp mọi người loại trừ và đoán mũ.

người thứ 99 sẽ dựa vào 2 màu của người 100 + 98 mũ trước để đoán ,

người thứ 98 dựa vào 2 màu người 100 + 1 màu người 99 + 97 mũ trước

....

Vậy mấu chốt là làm sao để người 100 nói ra được 2 màu : họ sẽ nói ra màu được PHA TRỘN bởi 2 màu còn thiếu .

như vậy mọi người phía trước luôn phải chọn 1 trong 3 màu còn thiếu (màu thừa . mũ người 100 , mũ của mình) nhưng có dữ liệu màu tổng hợp của 2 màu sai (màu còn thừa và mũ người 100 ) -> họ sẽ đoán được mũ của mình

vị dụ : người 100 thấy còn thiếu 2 màu ĐỎ và Vàng thay vì đoán là đỏ hay vàng họ sẽ nói ra màu CAM

người 99 sẽ thấy thiếu 3 màu ĐỎ , VÀNG , TÍM (101màu - 98 người trước) : nhưng vì đã bàn bạc trước người 99 sẽ biết 2 trong 3 màu pha thành màu CAM sẽ là sai > họ sẽ loại được màu ĐỎ , VÀNG và chọn màu TÍM.

người 98 cũng sẽ thấy thiếu 3 màu ( 101màu - 97 người trước - 1người vừa đoán đúng) và họ cũng duy luận như người 99 và loại được 2 màu ĐỎ , VÀNG

Với cách này thì người 100 chắc chắn sẽ hy sinh cho 99 người trước

nếu thay màu mũ bằng các con số thì còn dễ hơn người 100 sẽ nói ra tổng của 2 số còn thiếu , Nếu có 3 số KHÁC NHAU mà bạn biết tổng của 2 số SAI , bạn sẽ luôn chon được số CÒN LẠI vì với 3 số ,a ,b ,c khác nhau thì a + b = X , thì a + c và b + c không thể = X

Đọc lời giải thì mấu chốt không phải cứu tất cả, mà là cứu 99 người phía trước, còn người thứ 100 sẽ chịu hy sinh để nhắc màu cho 99 người còn lại. Nhưng mà liệu có cách nào có thể cứu được tất cả 100 người không nhỉ?

100 mũ không trùng màu thì nô lệ hẳn là phải đọc mã màu dưới dạng hex