Cách chắc ăn nhất để giải câu đố ai nói thật ai nói dối là giả sử từng trường hợp: lần lượt cho mỗi người là hiệp sĩ (luôn nói thật) hoặc kẻ nói dối (luôn nói sai), rồi kiểm xem lời của từng người có khớp với loại người đó không. Kịch bản nào không vướng mâu thuẫn là đáp án. Với n người có tất cả 2ⁿ kịch bản, nên chỉ cần kiên nhẫn và một bảng kiểm gọn là không bao giờ sót.
Luật của đảo và bốn bước giả sử
Trên đảo hiệp sĩ và kẻ nói dối chỉ có hai loại người. Hiệp sĩ mỗi câu nói ra đều đúng. Kẻ nói dối mỗi câu nói ra đều sai. Không ai nói nửa đúng nửa sai, không ai đổi loại giữa chừng. Khung này được nhà logic Raymond Smullyan phổ biến rộng rãi trong cuốn What Is the Name of This Book? (1978), và từ đó thành dạng bài quen thuộc trong sách bồi dưỡng học sinh giỏi.
Từ luật đó rút ra một quy tắc dùng suốt bài:
Người nói là hiệp sĩ khi và chỉ khi câu người đó nói là đúng.
Quy tắc này cho vài hệ quả rất tiện:
X nói "Y là kẻ nói dối" thì X và Y khác loại. Nếu X là hiệp sĩ, câu đúng, Y là kẻ nói dối. Nếu X là kẻ nói dối, câu sai, Y là hiệp sĩ.
- X nói "Y là hiệp sĩ" thì X và Y cùng loại.
- Một câu chắc chắn đúng (kiểu "2 + 2 = 4") chỉ hiệp sĩ nói được. Một câu chắc chắn sai chỉ kẻ nói dối nói được.
Bốn bước giả sử từng trường hợp
- Ghi tên và lời từng người thật gọn, mỗi lời đổi thành một điều kiện có thể kiểm đúng/sai.
- Chọn người có lời nói "nặng" nhất (nhắc tới nhiều người, hoặc nói về số lượng) và giả sử người đó là hiệp sĩ. Suy ra mọi thứ kéo theo. Gặp mâu thuẫn thì loại nhánh này.
- Giả sử ngược lại: người đó là kẻ nói dối. Lời người đó phải sai, tức điều ngược lại là đúng. Suy tiếp.
- Kiểm lại toàn bộ mọi lời trong nhánh còn sống. Nếu chỉ một nhánh sống thì đáp án duy nhất. Nếu hai nhánh cùng sống, đề có nhiều đáp án và phải nói rõ như vậy, không được chọn bừa một nhánh. Cẩn thận với câu "nếu… thì…": vế "nếu" sai thì cả câu đúng.
Khi số người ít (2 đến 3), lập luôn bảng đủ 2ⁿ dòng là nhanh nhất. Khi số người nhiều hơn, dùng các hệ quả ở trên để cắt bớt dòng trước rồi mới lập bảng.
Câu đố 1: hai bạn ở bến đò
Ví dụ minh hoạ tự đặt. Chiều muộn ở bến đò của đảo, khách gặp An và Bình.
- An nói: «Bình là kẻ nói dối.»
- Bình nói: «Hai đứa mình cùng loại.»
Hỏi mỗi người thuộc loại nào?
Lời giải từng bước
Giả sử An là hiệp sĩ. Lời An đúng, nên Bình là kẻ nói dối. Bình nói "hai đứa cùng loại", nhưng thực tế An là hiệp sĩ, Bình là kẻ nói dối, tức khác loại. Câu của Bình sai, đúng với việc Bình là kẻ nói dối. Không mâu thuẫn.
Giả sử An là kẻ nói dối. Lời An sai, nên Bình là hiệp sĩ. Khi đó hai người khác loại, câu "cùng loại" của Bình sai. Nhưng Bình là hiệp sĩ thì không được nói sai. Mâu thuẫn, loại nhánh này.
Kết luận: An là hiệp sĩ, Bình là kẻ nói dối. Đáp án duy nhất.
| Kịch bản | Lời An ("Bình dối") | Lời Bình ("cùng loại") | Kết luận |
|---|---|---|---|
| An hiệp sĩ, Bình hiệp sĩ | Sai, nhưng An phải nói đúng | Đúng | Loại |
| An hiệp sĩ, Bình nói dối | Đúng, khớp | Sai, khớp | Khả thi |
| An nói dối, Bình hiệp sĩ | Sai, khớp | Sai, nhưng Bình phải nói đúng | Loại |
| An nói dối, Bình nói dối | Đúng, nhưng An phải nói sai | Đúng | Loại |
Câu đố 2: ba người bán hàng ở chợ đảo
Ví dụ minh hoạ tự đặt. Buổi sáng ở chợ, Cúc, Dũng và Hà đứng cạnh nhau.
- Cúc nói: «Cả ba chúng ta đều là kẻ nói dối.»
- Dũng nói: «Trong ba chúng ta có đúng một kẻ nói dối.»
- Hà nói: «Dũng là kẻ nói dối.»
Lời giải từng bước
Bước 1, xét Cúc. Giả sử Cúc là hiệp sĩ thì câu của Cúc đúng, nghĩa là Cúc cũng là kẻ nói dối. Vô lý. Vậy Cúc là kẻ nói dối, và câu của Cúc sai: không phải cả ba đều nói dối, tức có ít nhất một hiệp sĩ.
Bước 2, xét cặp Dũng – Hà. Hà nói Dũng là kẻ nói dối, nên Hà và Dũng khác loại: đúng một trong hai là hiệp sĩ.
Bước 3, đếm. Cúc là kẻ nói dối, cộng thêm đúng một kẻ nói dối trong cặp Dũng – Hà, tổng cộng có hai kẻ nói dối. Câu của Dũng ("đúng một kẻ nói dối") vì thế sai, nên Dũng là kẻ nói dối, kéo theo Hà là hiệp sĩ.
Bước 4, kiểm lại. Cúc nói dối, câu "cả ba nói dối" sai vì Hà là hiệp sĩ: khớp. Dũng nói dối, câu "đúng một kẻ nói dối" sai vì có hai: khớp. Hà hiệp sĩ, câu "Dũng là kẻ nói dối" đúng: khớp.
Kết luận: Cúc và Dũng là kẻ nói dối, Hà là hiệp sĩ. Bảng dưới kiểm đủ 8 kịch bản (H là hiệp sĩ, D là kẻ nói dối).
| Cúc – Dũng – Hà | Số kẻ nói dối | Lời Cúc | Lời Dũng | Lời Hà | Kết luận |
|---|---|---|---|---|---|
| H – H – H | 0 | Sai, không khớp | Sai | Sai | Loại |
| H – H – D | 1 | Sai, không khớp | Đúng | Sai | Loại |
| H – D – H | 1 | Sai, không khớp | Đúng | Đúng | Loại |
| H – D – D | 2 | Sai, không khớp | Sai | Đúng | Loại |
| D – H – H | 1 | Sai, khớp | Đúng, khớp | Sai, không khớp | Loại |
| D – H – D | 2 | Sai, khớp | Sai, không khớp | Sai | Loại |
| D – D – H | 2 | Sai, khớp | Sai, khớp | Đúng, khớp | Khả thi |
| D – D – D | 3 | Đúng, không khớp | Sai | Đúng | Loại |
Câu đố 3: bốn cầu thủ đội bóng xóm
Ví dụ minh hoạ tự đặt. Sau trận bóng chiều, bốn cầu thủ Khoa, Lâm, Minh, Nga ngồi nghỉ bên sân.
- Khoa nói: «Lâm và Minh đều là kẻ nói dối.»
- Lâm nói: «Nếu Khoa là hiệp sĩ thì Nga cũng là hiệp sĩ.»
- Minh nói: «Lâm là kẻ nói dối.»
- Nga nói: «Trong bốn chúng ta có ít nhất hai kẻ nói dối.»
Bốn người là 16 kịch bản. Thay vì lập đủ 16 dòng, ta cắt bớt trước.
Lời giải từng bước
Bước 1, cặp Lâm – Minh. Minh nói Lâm là kẻ nói dối, nên Minh và Lâm khác loại. Chỉ còn hai khả năng: Lâm hiệp sĩ – Minh nói dối, hoặc ngược lại. Còn 8 kịch bản.
Bước 2, Khoa. Lâm và Minh khác loại nên không thể cả hai cùng nói dối. Câu của Khoa sai, Khoa là kẻ nói dối.
Bước 3, Lâm. Câu của Lâm có dạng "nếu… thì…". Trong logic, câu "nếu p thì q" chỉ sai khi p đúng mà q sai. Ở đây p là "Khoa là hiệp sĩ", mà Khoa là kẻ nói dối, nên p sai và cả câu của Lâm đúng, bất kể Nga thuộc loại nào. Người nói câu đúng phải là hiệp sĩ: Lâm là hiệp sĩ, kéo theo Minh là kẻ nói dối.
Bước 4, Nga. Đã có hai kẻ nói dối là Khoa và Minh. Nếu Nga là hiệp sĩ, số kẻ nói dối là 2, câu "ít nhất hai" đúng: khớp. Nếu Nga là kẻ nói dối, số kẻ nói dối là 3, câu vẫn đúng, nhưng kẻ nói dối không được nói đúng: loại. Vậy Nga là hiệp sĩ.
Kết luận: Khoa và Minh nói dối, Lâm và Nga là hiệp sĩ.
| Khoa – Lâm – Minh – Nga | Lời Khoa | Lời Lâm | Lời Minh | Lời Nga | Kết luận |
|---|---|---|---|---|---|
| H – H – D – H | Sai, không khớp | Đúng | Sai | Sai (1 kẻ dối) | Loại |
| H – H – D – D | Sai, không khớp | Sai | Sai | Đúng | Loại |
| H – D – H – H | Sai, không khớp | Đúng | Đúng | Sai | Loại |
| H – D – H – D | Sai, không khớp | Sai | Đúng | Đúng | Loại |
| D – H – D – H | Sai, khớp | Đúng, khớp | Sai, khớp | Đúng, khớp | Khả thi |
| D – H – D – D | Sai, khớp | Đúng, khớp | Sai, khớp | Đúng, không khớp | Loại |
| D – D – H – H | Sai, khớp | Đúng, không khớp | Đúng | Đúng | Loại |
| D – D – H – D | Sai, khớp | Đúng, không khớp | Đúng | Đúng | Loại |
Tám kịch bản còn lại (Lâm và Minh cùng loại) đã bị loại ngay từ bước 1 vì lời của Minh.
Tự luyện
- Xuân nói: «Yến là hiệp sĩ.» Yến nói: «Xuân và Yến khác loại.» Hai người thuộc loại nào?
Đáp án: Xuân nói Yến là hiệp sĩ nên hai người cùng loại. Vậy câu của Yến sai, Yến là kẻ nói dối, và Xuân cũng là kẻ nói dối.
Tú nói: «Uyên là kẻ nói dối.» Uyên nói: «Tú là kẻ nói dối.» Biết được gì?
Đáp án: Chỉ biết hai người khác loại. Cả hai kịch bản (Tú hiệp sĩ – Uyên nói dối và ngược lại) đều khả thi, đề có hai đáp án.
Vy nói: «Thảo và Quý đều là hiệp sĩ.» Thảo nói: «Vy là kẻ nói dối.» Quý nói: «Thảo là kẻ nói dối.»
Đáp án: Quý và Thảo khác loại nên câu của Vy sai, Vy nói dối. Khi đó câu của Thảo đúng, Thảo là hiệp sĩ, Quý là kẻ nói dối.
Ba người, mỗi người nói: «Hai người còn lại đều là kẻ nói dối.» Có bao nhiêu hiệp sĩ?
Đáp án: Đúng một. Nếu có hai hiệp sĩ trở lên thì mỗi hiệp sĩ lại gọi một hiệp sĩ khác là kẻ nói dối, vô lý. Nếu không ai là hiệp sĩ thì câu của mỗi người đúng, cũng vô lý. Với đúng một hiệp sĩ, câu của hiệp sĩ đúng, câu của hai người kia sai vì trong "hai người còn lại" của họ có hiệp sĩ. Ai là hiệp sĩ thì không xác định được.
Dùng vào đâu
Thói quen "giả sử rồi kiểm đến cùng" là nền của rất nhiều việc. Trong bài thi trắc nghiệm, đó là cách thử từng phương án thay vì đoán. Trong lập trình, bảng 2ⁿ kịch bản chính là vòng lặp vét cạn, cách máy tính giải đúng các câu đố này trong tích tắc. Danh mục này còn các bài đi sâu từng biến thể: câu tự nói về mình, ngã ba đường, người thường lúc thật lúc dối. Khi đọc một tình huống tranh chấp đời thường, nó nhắc ta tách từng giả thiết và xem giả thiết nào dẫn tới chỗ vô lý.
Câu hỏi thường gặp
Cách giải câu đố ai nói thật ai nói dối nhanh nhất là gì?
Tìm ngay các cặp người nói về nhau: ai gọi người kia là kẻ nói dối thì hai người khác loại, ai gọi người kia là hiệp sĩ thì cùng loại. Sau đó giả sử người có câu nói nặng nhất là hiệp sĩ, suy ra, rồi thử nhánh ngược lại. Cuối cùng kiểm lại mọi lời.
Có bao nhiêu trường hợp cần xét khi có n người?
Mỗi người có hai khả năng nên n người có 2ⁿ kịch bản: 2 người là 4, 3 người là 8, 4 người là 16. Dùng các quan hệ cùng loại, khác loại để cắt bớt trước sẽ đỡ nhiều công.
Làm sao biết đề có đáp án duy nhất?
Phải xét hết mọi nhánh, không dừng ở nhánh hợp lệ đầu tiên. Nếu đúng một kịch bản sống sót thì đáp án duy nhất; nếu nhiều kịch bản sống thì đề có nhiều đáp án, còn nếu không kịch bản nào sống thì đề mâu thuẫn.
Vì sao "nếu Khoa là hiệp sĩ thì Nga là hiệp sĩ" lại đúng khi Khoa nói dối?
Trong logic, câu "nếu p thì q" chỉ sai trong đúng một trường hợp: p đúng mà q sai. Khi p sai, câu được coi là đúng bất kể q. Đây là quy ước của phép kéo theo, không phải mẹo riêng của câu đố.
Hiệp sĩ và kẻ nói dối là của ai nghĩ ra?
Khung đảo hiệp sĩ và kẻ nói dối gắn với tên nhà logic Raymond Smullyan, được ông phổ biến trong cuốn What Is the Name of This Book? năm 1978. Các câu đố trong bài này là ví dụ tự đặt để minh hoạ phương pháp.
