Ở ngã ba có một người gác, không biết là hiệp sĩ (luôn nói thật) hay kẻ nói dối (luôn nói sai), muốn biết lối trái có về làng không thì hỏi: «Anh là hiệp sĩ khi và chỉ khi lối trái về làng, đúng không?». Nghe "có" thì đi lối trái, nghe "không" thì đi lối phải. Còn nếu có hai người gác, một thật một dối, chỉ cần hỏi một người: «Người kia sẽ chỉ lối nào?» rồi đi lối ngược lại.
Bài này giải ba câu đố ngã ba đường tự đặt, mỗi câu có bảng kiểm đủ các kịch bản, chỉ ra vì sao nhiều câu hỏi nghe hợp lý lại vô dụng, và rút ra một công thức đặt câu hỏi dùng được cho bất cứ điều gì muốn biết. Riêng kiểu câu hỏi lồng "nếu được hỏi thì anh sẽ trả lời thế nào" có bài phân tích riêng trong cùng danh mục.
Đề bài và chỗ khó thật sự
Câu đố ngã ba đường xuất hiện trong rất nhiều sách đố thế kỷ 20, không rõ ai đặt ra đầu tiên. Khung chung: khách đến chỗ đường rẽ đôi, một lối về làng, một lối vào rừng sâu. Ở đó có người của đảo hiệp sĩ – kẻ nói dối. Khách chỉ được hỏi một câu, người gác chỉ trả lời "có" hoặc "không".
Chỗ khó: một câu có/không chỉ mang về một mẩu thông tin. Ta có hai điều chưa biết (người gác thuộc loại nào, lối nào đúng), nhưng chỉ cần biết một trong hai: lối nào đúng. Câu hỏi phải được thiết kế sao cho loại của người gác "tự triệt tiêu" trong câu trả lời.
Câu đố 1: một người gác ở ngã ba rừng tràm
Ví dụ minh hoạ tự đặt. Một buổi sáng sương, khách đi bộ đến ngã ba trong rừng tràm. Một người gác đứng đó. Khách hỏi đúng một câu: «Anh là hiệp sĩ khi và chỉ khi lối bên trái dẫn về làng, đúng không?»
"Khi và chỉ khi" nghĩa là hai vế cùng đúng hoặc cùng sai. Câu hỏi đó đúng trong hai trường hợp: người gác là hiệp sĩ và lối trái về làng; hoặc người gác là kẻ nói dối và lối trái không về làng. Nếu ngại cụm từ ấy, có thể nói dài hơn mà cùng nghĩa: «Hoặc anh là hiệp sĩ và lối trái về làng, hoặc anh là kẻ nói dối và lối trái không về làng, đúng không?»
Lời giải: kiểm đủ bốn kịch bản
| Người gác | Lối trái về làng? | Câu hỏi thực tế | Người gác trả lời | Khách đi | Đúng? |
|---|---|---|---|---|---|
| Hiệp sĩ | Có | Đúng | "Có" | Trái | Đúng |
| Hiệp sĩ | Không | Sai | "Không" | Phải | Đúng |
| Kẻ nói dối | Có | Sai | "Có" (nói ngược) | Trái | Đúng |
| Kẻ nói dối | Không | Đúng | "Không" (nói ngược) | Phải | Đúng |
Cả bốn dòng, câu trả lời "có" trùng đúng với việc lối trái về làng. Lý do gọn: với hiệp sĩ, phần "anh là hiệp sĩ" đúng nên câu hỏi chỉ còn là "lối trái về làng không?", trả lời thật. Với kẻ nói dối, phần đó sai nên câu hỏi thành "lối trái không về làng?", rồi bị nói ngược thêm một lần. Hai lần đảo triệt tiêu nhau.
Câu đố 2: hai người gác trước hai cổng làng
Ví dụ minh hoạ tự đặt. Lần này có hai lối, mỗi lối có một cổng tre, trước cổng là một người gác. Khách biết chắc: một người là hiệp sĩ, người kia là kẻ nói dối, nhưng không biết ai là ai. Được hỏi một câu, cho một người.
Câu hỏi: chỉ vào một người bất kỳ và hỏi: «Nếu mình hỏi người kia lối nào về làng, người kia sẽ chỉ lối nào?». Rồi đi lối ngược lại với lối được chỉ.
Lời giải: kiểm đủ bốn kịch bản
| Người được hỏi | Lối đúng | Người kia sẽ chỉ | Người được hỏi báo lại | Khách đi (ngược lại) | Đúng? |
|---|---|---|---|---|---|
| Hiệp sĩ | Trái | Phải (kẻ nói dối chỉ sai) | "Phải" (báo thật) | Trái | Đúng |
| Hiệp sĩ | Phải | Trái | "Trái" | Phải | Đúng |
| Kẻ nói dối | Trái | Trái (hiệp sĩ chỉ đúng) | "Phải" (báo sai) | Trái | Đúng |
| Kẻ nói dối | Phải | Phải | "Trái" | Phải | Đúng |
Vì sao luôn phải đi ngược? Thông tin đi qua cả hai người, và trong hai người có đúng một kẻ nói dối. Dù hỏi ai, câu trả lời cũng bị đảo đúng một lần, nên nó luôn chỉ sai lối. Biết chắc nó sai thì cũng là biết lối đúng.
Câu hỏi của câu đố 1 cũng dùng được ở đây: hỏi bất kỳ người nào «Anh là hiệp sĩ khi và chỉ khi lối trái về làng, đúng không?» vẫn cho kết quả đúng, vì câu đó không cần biết người còn lại.
Câu đố 3: những câu hỏi nghe hợp lý mà vô dụng
Ví dụ minh hoạ tự đặt. Vẫn khung hai người gác, một thật một dối. Một bạn học sinh đề xuất năm câu hỏi. Câu nào giúp tìm lối đúng?
«Lối trái có về làng không?»
- «Anh có phải hiệp sĩ không?»
- «Người kia là hiệp sĩ phải không?»
- «Nếu lối trái về làng thì anh là hiệp sĩ, đúng không?»
- «Anh là hiệp sĩ khi và chỉ khi lối trái về làng, đúng không?»
Lời giải: soi từng câu
| Câu hỏi | Hiệp sĩ trả lời | Kẻ nói dối trả lời | Dùng được? |
|---|---|---|---|
| 1. Lối trái về làng? | Đúng sự thật | Ngược sự thật | Không: không biết ai đang trả lời |
| 2. Anh là hiệp sĩ? | "Có" | "Có" | Không: luôn "có" |
| 3. Người kia là hiệp sĩ? | "Không" (người kia nói dối) | "Không" (người kia là hiệp sĩ, nói ngược) | Không: luôn "không" |
| 4. Nếu lối trái đúng thì anh là hiệp sĩ? | "Có" (câu đúng vì vế sau đúng) | Lối trái đúng: câu sai, đáp "có"; lối trái sai: câu đúng, đáp "không" | Không: hiệp sĩ luôn "có" bất kể lối |
| 5. Anh là hiệp sĩ khi và chỉ khi lối trái đúng? | "Có" khi lối trái đúng | "Có" khi lối trái đúng | Có |
Câu 4 đáng soi kỹ. Với hiệp sĩ, vế "anh là hiệp sĩ" đúng nên câu "nếu… thì…" luôn đúng, hiệp sĩ luôn đáp "có", không nói gì về lối. Câu này chỉ có ích nếu người được hỏi là kẻ nói dối, mà ta không biết điều đó. Chỉ câu 5 đáp ứng yêu cầu ở mọi kịch bản.
Công thức chung: hỏi "X khi và chỉ khi anh là hiệp sĩ"
Muốn biết một điều X bất kỳ (lối trái về làng, cầu còn đi được, chợ hôm nay có họp) từ một người không rõ loại, hãy hỏi: «Anh là hiệp sĩ khi và chỉ khi X, đúng không?». Câu trả lời "có" nghĩa là X đúng.
Kiểm bằng ký hiệu cho người thích gọn. Gọi H là "người được hỏi là hiệp sĩ", X là điều cần biết, dấu ↔ đọc là "khi và chỉ khi".
- Nếu H đúng: câu hỏi H ↔ X có giá trị bằng X, hiệp sĩ báo thật, nên trả lời "có" đúng khi X đúng.
- Nếu H sai: câu hỏi H ↔ X có giá trị bằng "không X", kẻ nói dối báo ngược, thành X. Lại trả lời "có" đúng khi X đúng.
Người học điện tử sẽ nhận ra: phép ↔ chính là cổng XNOR, còn lời nói dối là một cổng NOT gắn thêm. Đặt một XNOR với "loại người nói" trước cổng NOT ấy là để hai lần đảo triệt tiêu nhau.
Giới hạn: một câu có/không chỉ chia được làm hai
Nếu đường rẽ thành ba lối, một câu hỏi có/không không đủ để luôn tìm ra lối đúng. Câu trả lời chỉ có hai khả năng, nên chỉ tách được ba lối thành hai nhóm; nhóm nào cũng có thể còn hai lối. Muốn chắc chắn cần câu hỏi thứ hai, mỗi câu dùng công thức trên. Đây là ý tưởng "một câu có/không mang về một bit" mà ngành thông tin học đo đếm kỹ hơn.
Tự luyện
- Một người gác không rõ loại. Hỏi một câu để biết người đó có phải hiệp sĩ không.
Đáp án: Hỏi một điều ai cũng biết chắc, ví dụ «2 + 2 = 4 phải không?». Đáp "có" là hiệp sĩ, đáp "không" là kẻ nói dối.
Hai người gác, một thật một dối. Hỏi một người «Anh và người kia cùng loại phải không?». Biết được gì?
Đáp án: Thực tế hai người khác loại nên câu đúng phải là "không". Đáp "không" là hiệp sĩ, đáp "có" là kẻ nói dối. Biết người mình hỏi thuộc loại nào, nhưng chưa biết lối nào đúng.
Dùng công thức để hỏi một người không rõ loại xem chợ phiên hôm nay có họp không.
Đáp án: «Anh là hiệp sĩ khi và chỉ khi chợ phiên hôm nay họp, đúng không?». Đáp "có" thì chợ họp.
Hai người gác, một thật một dối. Khách hỏi người A: «Người kia sẽ nói lối trái về làng chứ?». A đáp "có". Lối nào đúng?
Đáp án: Lời truyền qua cả hai người, bị đảo đúng một lần, nên "có" thực ra là "không": lối trái không về làng, đi lối phải.
Dùng vào đâu
Câu đố ngã ba đường dạy một kỹ năng ít ai để ý: thiết kế câu hỏi sao cho câu trả lời có ích bất kể người trả lời là ai. Kỹ sư làm việc này khi viết phép kiểm cho dữ liệu có thể bị đảo bit; người làm khảo sát làm việc này khi đặt câu hỏi kiểm tra chéo. Với học sinh, nó là bài tập tốt về "khi và chỉ khi", điều kiện cần và đủ, và bảng chân trị bốn dòng.
Ai muốn đi tiếp có thể đọc cuốn What Is the Name of This Book? (1978) của Raymond Smullyan; còn câu đố khó hơn nhiều với người trả lời ngẫu nhiên và từ "có/không" bằng tiếng lạ thuộc một chủ đề khác về câu đố logic nổi tiếng.
Câu hỏi thường gặp
Câu đố ngã ba đường hỏi câu gì là đúng?
Với một người gác không rõ loại, hỏi «Anh là hiệp sĩ khi và chỉ khi lối trái về làng, đúng không?». Đáp "có" thì đi lối trái. Với hai người gác một thật một dối, có thể hỏi một người «Người kia sẽ chỉ lối nào?» rồi đi lối ngược lại.
Vì sao phải đi ngược lại lối được chỉ?
Câu trả lời truyền qua cả hai người gác, trong đó có đúng một kẻ nói dối, nên bị đảo đúng một lần. Lối được chỉ vì vậy luôn là lối sai.
Hỏi "anh có phải hiệp sĩ không" có được không?
Không. Hiệp sĩ đáp "có" vì đúng, kẻ nói dối cũng đáp "có" vì nói ngược. Câu trả lời luôn giống nhau nên không mang thông tin gì.
Có câu hỏi nào dùng cho mọi điều muốn biết không?
Có: «Anh là hiệp sĩ khi và chỉ khi X, đúng không?». Với cả hiệp sĩ lẫn kẻ nói dối, câu trả lời "có" đều nghĩa là X đúng, vì lời nói dối và phép "khi và chỉ khi" đảo kết quả hai lần.
Ba lối đi thì một câu hỏi có đủ không?
Không đủ để luôn chắc chắn. Một câu có/không chỉ tách các lối thành hai nhóm, nên với ba lối có thể còn sót hai lựa chọn; cần thêm một câu hỏi nữa.
