Asked Nov 28th, 2023 6:50 a.m. 620 1 10
  • 620 1 10
+9

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

Share
  • 620 1 10

Đây là một câu đố mình tìm được trong một cuốn sách cổ nhưng không có lời giải, mình đã rất vất vả để giải quyết được nó nên mình muốn đăng lên cho mọi người thử sức. Câu đố này có tên "Nô lệ đoán màu mũ"

"Ở một vương quốc nọ có 100 người nô lệ cực kỳ thông minh bị ban tội chết, tuy nhiên đức vua muốn tha cho một số người trong số họ nên tổ chức 1 trò chơi. Luật chơi như sau: 100 người nô lệ đứng thành 1 hàng dọc, sao cho người trước không thể nhìn thấy người sau. Người 1 không thấy ai hết, người 2 thấy đầu người 1, người 3 thấy đầu người 1 và người 2, ... người thứ 100 thấy đầu 99 người phía trước. Có 101 chiếc mũ có màu xanh, đỏ, tím, vàng ... khác nhau (không có 2 chiếc mũ nào cùng màu). Bịt mắt 100 người nô lệ lại và đội lên đầu của mỗi người một chiếc mũ bất kỳ. Sau đó tháo dải bịt mắt của họ ra, 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. Bắt đầu từ người thứ 100 (đứng cuối hàng) sẽ đoán trước, tiếp theo sẽ đến người 99, 98 ... cho đến người số 1 đoán cuối cùng. Nô lệ được biết trước màu mũ của 101 chiếc mũ và có thời gian bàn bạc với nhau để tìm ra kế hoạch. Nếu bạn là một trong số các nô lệ, phải làm sao để số người chết là ít nhất? Liệu có thể chắc chắn cứu được 99 người không?"

Cập nhật: Đáp án từ bạn SuperIdol là hoàn toán chính xác

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ại làm tương tự thì sẽ cứu được 99 người

Tuy nhiên, nếu nhà vua thêm yêu cầu chỉ cho phép mỗi màu chỉ được nói 1 lần duy nhất thì sao?

Cập nhật gợi ý: Liên quan tới hàm sort trong lập trình.

Avatar Huỳnh Hòa @khanhhoa130894
Nov 29th, 2023 9:26 a.m.
Avatar Thiện Ngô @ngotienthienntt
Dec 5th, 2023 1:50 a.m.

Người thứ 100 sẽ đoán màu của người phía trước để cho người phía trước biết màu của mình. Cứ như vậy sẽ cứu được 99 người, còn người thứ 100 sẽ chết

0
| Reply
Share
Dec 5th, 2023 2:18 a.m.

@ngotienthienntt chưa đúng nha, những người 98 trở về trước làm sao mà biết được mũ của mình vậy bạn.

0
| Reply
Share

10 ANSWERS


Answered Dec 5th, 2023 3:07 a.m.
Accepted
+2

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ỉ?

Share
Avatar Tiến Trần Minh @minhtien1403
Dec 5th, 2023 6:43 a.m.

người thứ 2 so sánh kiểu gì để tìm ra số của mình đc nhỉ, mình đã thử setup một bài toán nhỏ hơn vs 10 người và tính thử theo cách của bạn thì người thứ 2 tính ra 11 trong khi số của họ là 10

0
| Reply
Share
Avatar Super Idol @superidol
Dec 5th, 2023 7:33 a.m.

@minhtien1403 mình thử vs case 5 người thôi, bạn xem thử nha IMG_0220.jpeg

0
| Reply
Share
Dec 5th, 2023 7:40 a.m.

@minhtien1403 Ví dụ người thứ 100 báo rằng tổng của 99 người trước chia 101 dư 0. (bằng cách nói số 101)

Lúc này người 99 đếm được tổng của 98 người trước chia 101 dư 13 chẳng hạn, sẽ suy ra mình là số 88 (vì 88 + 13 = 101 dư 0) Người 98 lại đếm được 97 người trước chia 101 dư 50 chẳng hạn, sẽ suy ra mình là số 64 vì 88 + 50 + 64 = 202 tương tự cho đến người cuối cùng

0
| Reply
Share
Avatar Tiến Trần Minh @minhtien1403
Dec 5th, 2023 10:01 a.m.

@superidol uhm do mình oánh nhầm số nên tính sai :v

0
| Reply
Share
Avatar Tan Le @TanLm
Dec 6th, 2023 6:54 a.m.

@superidol Bạn hãy giải thích tại sao người T5 thấy được số 6 mà vẫn đoán số 6 ?

0
| Reply
Share
Avatar Nam Do @dovannam115
Dec 8th, 2023 4:17 a.m.

@TanLm chắc là do người thứ 5 bị ngơ:))))

0
| Reply
Share
Avatar Super Idol @superidol
Dec 15th, 2023 6:35 a.m.

@TanLm thứ nhất là người thứ 5 nếu muốn sống thì đoán 1 trong 2 số 4 và 5, 50% sống hoặc chết chứ k chắc chắn sống. Thứ 2 là muốn chắc chắn cứu đc nhiều người nhất, nên người thứ 5 hy sinh để 4 người còn lại sống thôi. Đây là case 5 người, chứ case 100 hay 1000 người cũng vậy, hy sinh 1 người để 99 hoặc 999 người còn lại sống.

0
| Reply
Share
Avatar Tan Le @TanLm
Dec 19th, 2023 6:51 a.m.

@superidol mình nghĩ mỗi người đều phải đoán 1 trong 2 số;

  • người t5 phải đoán số 4,5 ;
  • người t4 phải đoán số 6 và (4 hoặc 5)
0
| Reply
Share
Answered Nov 30th, 2023 7:26 a.m.
+2

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

Share
Nov 30th, 2023 7:48 a.m.

Ý tưởng hay, nhưng đáp án chưa chính xác. Chỉ được trả lời 1 trong 101 màu hợp lệ thôi nhé.

0
| Reply
Share
Answered Nov 28th, 2023 7:41 a.m.
+1

wow

Share
Avatar Định Bùi @dinhbui3789
Nov 29th, 2023 1:46 p.m.
Answered Nov 29th, 2023 3:55 a.m.
+1

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

Share
Nov 29th, 2023 4:04 a.m.

Chat GPT à bạn :v Sai rồi nhé.

0
| Reply
Share
Avatar Huỳnh Hòa @khanhhoa130894
Nov 29th, 2023 9:26 a.m.
Answered Dec 1st, 2023 6:58 a.m.
+1

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)

Share
Answered Nov 29th, 2023 9:30 a.m.
0

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
Share
Nov 29th, 2023 11:05 a.m.

Chưa chính xác nhé. Bài toán này không liên quan đến xác suất. Đáp án là chắc chắn cứu được tối thiểu 99 người.

0
| Reply
Share
Avatar Huỳnh Hòa @khanhhoa130894
Dec 20th, 2023 8:36 a.m.

Mình không nói về xác suất, ý mình là nô lệ 100 sẽ có tỉ lệ 50% đoán được mũ của mình vì thấy được 99 mũ của 99 nô lệ trước đó, nên ở câu cuối mình chốt là nếu nô lệ 100 đoán trúng thì cứu được 100 người, còn đoán sai thì cứu được 99 người (cứu được chắc chắn 99 người như bạn nói) Có thể lời nói mình hơi khó hiểu nhưng bạn đọc kĩ lại thì có thể nó giống với ý lời giải bạn đang nghĩ đó

0
| Reply
Share
Answered Dec 1st, 2023 2:52 a.m.
0

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

Share
Dec 1st, 2023 6:52 a.m.

Sai rồi, nếu người 100 đoán sai => 1 người die Đến người 99 đoán, cũng chỉ thấy đc 98 mũ còn lại + loại trừ mũ của người vừa die nữa là 99 vẫn còn thiếu 2 mũ chưa đoán => lại không có cơ sở để đoán tiếp, nếu đoán sai tiếp cũng die luôn. Tương tự những người sau không có cơ sở gì.

Tóm lại theo cách của bạn không có gì chắc chắn ở đây cả, thậm chí xui rủi có thể 100 người đều chết :v

0
| Reply
Share
Answered Dec 2nd, 2023 3:38 a.m.
0

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

Share
Dec 2nd, 2023 3:52 a.m.

Câu trả lời này khá giống với Lê Tú đã trả lời ở trên, tuy nhiên đáp án này không chính xác vì CHỈ ĐƯỢC TRẢ LỜI 1 TRONG 101 MÀU MŨ ĐÃ CHO TRƯỚC

0
| Reply
Share
Answered Dec 7th, 2023 1:12 a.m.
0

Đọ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ỉ?

Share
Dec 7th, 2023 2:56 p.m.

người 100 tưởng chừng là người có nhiều thông tin nhất nhưng thực tế lại là người không đủ cơ sở để đoán màu mũ của chính mình (vì phải đoán đầu tiên) nên chắc chắn không thể 100% sống sót.

0
| Reply
Share
Answered Nov 28th, 2023 8:31 a.m.
-1

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 🤔

Share
Nov 28th, 2023 8:46 a.m.

@tranminhnhat Thay vì gọi tên màu cụ thể, bạn có thể xem là mũ 1 đến mũ 101 đi.

0
| Reply
Share
Viblo
Let's register a Viblo Account to get more interesting posts.