Bài toán "mỗi người đoán đúng một nửa" cho vài người đoán thứ hạng, mỗi người nêu hai ý và đúng đúng một ý. Cách giải: chọn một người, giả sử nửa đầu của người đó đúng (thì nửa sau sai), lần theo hệ quả qua các lời đoán khác cho tới khi gặp mâu thuẫn hoặc ra một thứ tự trọn vẹn; rồi làm lại với nửa còn lại. Nhánh nào sống sót và kiểm lại khớp mọi lời đoán là đáp án.
Luật "đúng một nửa" nói gì, và không nói gì
Mỗi lời đoán gồm hai mệnh đề, ví dụ "Dũng nhì, An nhất". Ràng buộc "đúng một nửa" có hai nửa thông tin, người giải hay chỉ dùng một:
- Ít nhất một ý đúng: không được cả hai cùng sai.
- Nhiều nhất một ý đúng: không được cả hai cùng đúng.
Vế thứ hai mới là chỗ hay sinh lời giải. Nếu một ý đúng kéo theo ý kia cũng đúng (ví dụ "7C về cuối" và "7D về trước 7C" — đội về cuối thì ai cũng về trước nó), thì ý đó chắc chắn sai. Bỏ quên vế này, đề sẽ có thêm "đáp án" giả.
Một chi tiết nữa: các vị trí không trùng nhau. Trong cuộc thi chạy không có đồng hạng (đề luôn ngầm định thế, nên nói rõ khi giải). Hai ý "An nhất" và "Dũng nhất" không thể cùng đúng; "Dũng nhì" và "Dũng nhất" cũng vậy.
Câu đố 1: bốn bạn chạy, ba người đoán
Câu đố tự đặt để minh hoạ. Hội khoẻ Phù Đổng của trường có chung kết chạy 100 m với bốn bạn An, Bình, Cường, Dũng. Trước giờ chạy, ba bạn trên khán đài đoán:
- Lan: "Dũng nhì, An nhất."
- Minh: "Bình tư, Dũng nhất."
- Hoa: "An ba, Cường tư."
Không có đồng hạng. Kết quả cho thấy mỗi người đoán đúng đúng một ý. Thứ tự về đích thế nào?
Lời giải từng bước
Nhánh 1 — giả sử "An nhất" đúng (vậy "Dũng nhì" sai). An nhất thì "Dũng nhất" của Minh sai, nên "Bình tư" đúng. Hoa: "An ba" sai (An nhất), nên "Cường tư" đúng. Bình tư và Cường tư cùng lúc — vô lý. Nhánh này loại.
Nhánh 2 — giả sử "Dũng nhì" đúng (vậy An không nhất). Dũng nhì thì "Dũng nhất" sai, nên "Bình tư" đúng. Bình tư thì "Cường tư" của Hoa sai, nên "An ba" đúng. Còn Cường nhất. Thứ tự: Cường – Dũng – An – Bình.
| Nhánh | Từ lời Lan | Suy từ Minh | Suy từ Hoa | Thứ tự thu được | Kết luận |
|---|---|---|---|---|---|
| 1 | An nhất, Dũng không nhì | Bình tư | Cường tư | Bình và Cường cùng tư | Loại |
| 2 | Dũng nhì, An không nhất | Bình tư | An ba | Cường 1, Dũng 2, An 3, Bình 4 | Khả thi |
Kiểm lại với thứ tự Cường – Dũng – An – Bình:
| Người đoán | Ý thứ nhất | Ý thứ hai | Số ý đúng |
|---|---|---|---|
| Lan | Dũng nhì — Đúng | An nhất — Sai | 1 |
| Minh | Bình tư — Đúng | Dũng nhất — Sai | 1 |
| Hoa | An ba — Đúng | Cường tư — Sai | 1 |
Đáp án: Cường nhất, Dũng nhì, An ba, Bình tư. Vì Lan chỉ có hai nhánh và một nhánh đã loại, đáp án là duy nhất.
Câu đố 2: năm vận động viên, bốn lời đoán
Câu đố tự đặt. Giải chạy việt dã của xã có năm người vào chung kết: Hùng, Kiên, Lộc, Nam, Phú. Bốn cổ động viên đoán:
- Thảo: "Nam nhất, Lộc tư."
- Uyên: "Lộc năm, Kiên nhất."
- Vy: "Nam nhì, Hùng ba."
- Xuân: "Kiên tư, Phú năm."
Mỗi người đúng đúng một ý, không đồng hạng. Tìm thứ tự.
Lời giải từng bước
Nhánh 1 — "Nam nhất" đúng, "Lộc tư" sai. Vy: "Nam nhì" sai nên "Hùng ba" đúng. Uyên: "Kiên nhất" sai (Nam nhất) nên "Lộc năm" đúng. Xuân: "Phú năm" sai (Lộc năm) nên "Kiên tư" đúng. Còn Phú ở vị trí nhì. Thứ tự: Nam – Phú – Hùng – Kiên – Lộc. "Lộc tư" sai đúng như giả sử.
Nhánh 2 — "Lộc tư" đúng, Nam không nhất. Uyên: "Lộc năm" sai nên "Kiên nhất" đúng. Xuân: "Kiên tư" sai nên "Phú năm" đúng. Còn vị trí nhì và ba cho Nam và Hùng. Nếu Nam nhì, Hùng ba thì Vy đúng cả hai ý; nếu Nam ba, Hùng nhì thì Vy sai cả hai. Cả hai cách đều phạm luật. Nhánh loại.
| Nhánh | Thảo | Uyên | Xuân | Vy | Kết luận |
|---|---|---|---|---|---|
| 1 | Nam nhất | Lộc năm | Kiên tư | Hùng ba (Nam nhì sai) | Khả thi: Nam, Phú, Hùng, Kiên, Lộc |
| 2a | Lộc tư | Kiên nhất | Phú năm | Nam nhì, Hùng ba: đúng cả hai | Loại |
| 2b | Lộc tư | Kiên nhất | Phú năm | Nam ba, Hùng nhì: sai cả hai | Loại |
Đáp án: Nam nhất, Phú nhì, Hùng ba, Kiên tư, Lộc năm. Để ý nhánh 2: chính vế "không được đúng cả hai" đã loại dòng 2a. Ai chỉ nhớ "ít nhất một ý đúng" sẽ giữ dòng 2a và ra hai đáp án.
Câu đố 3: tiếp sức bốn lớp, có ý "về trước"
Câu đố tự đặt. Bốn lớp 7A, 7B, 7C, 7D chạy tiếp sức. Ba bạn đoán, mỗi bạn đúng đúng một ý:
- Bảo: "7C về tư, 7D về trước 7C."
- Châu: "7D về trước 7A, 7C về nhì."
- Duyên: "7B về nhì, 7B về trước 7C."
Lời giải từng bước
- Xét lời Duyên. Nếu "7B nhì" đúng thì "7B về trước 7C" phải sai, tức 7C về trước 7B — 7C nhất. Khi đó "7C tư" của Bảo sai, buộc "7D về trước 7C" đúng; nhưng 7C nhất thì không ai về trước 7C. Mâu thuẫn. Vậy "7B nhì" sai và "7B về trước 7C" đúng.
- Xét lời Bảo. Nếu "7C tư" đúng thì 7D tất nhiên về trước 7C — Bảo đúng cả hai ý, phạm luật. Vậy 7C không về tư, và "7D về trước 7C" đúng.
- Ghép lại. 7B và 7D đều về trước 7C, mà 7C không tư, nên 7C về ba và 7A về tư. 7B không nhì, nên 7B nhất, 7D nhì.
- Kiểm lời Châu. "7D về trước 7A": 7D nhì, 7A tư — đúng. "7C về nhì" — sai. Đúng một ý.
| Kịch bản | Bảo | Châu | Duyên | Kết luận |
|---|---|---|---|---|
| 7B nhì (7C nhất) | Hai ý cùng sai | — | Một ý đúng | Loại |
| 7B trước 7C, 7C tư | Hai ý cùng đúng | — | Một ý đúng | Loại |
| 7B 1, 7D 2, 7C 3, 7A 4 | Một ý đúng | Một ý đúng | Một ý đúng | Khả thi |
Đáp án: 7B nhất, 7D nhì, 7C ba, 7A tư. Ý dạng "X về trước Y" khó hơn ý "X về thứ k" vì nó không chốt vị trí, nhưng lại hay sinh ra cặp ý "kéo nhau cùng đúng" — đúng chỗ để khai thác luật "không được đúng cả hai".
Mẹo chọn nhánh để giải nhanh
- Bắt đầu từ người có ý "đè" lên nhiều lời đoán khác. Ý "Nam nhất" chạm cùng lúc tới "Kiên nhất" và "Nam nhì" — giả sử nó đúng là kéo được ngay ba hệ quả.
- Tìm cặp ý cùng vị trí. Hai người cùng nhắc vị trí nhất (hoặc cùng nhắc một bạn) là chỗ hai lời đoán "va" nhau.
- Tìm ý kéo theo ý. "X về cuối" kéo theo "Y về trước X". Ý kéo theo như thế không thể là ý đúng duy nhất.
- Luôn kiểm cả hai nhánh của người đầu tiên. Nhánh đầu cho đáp án không có nghĩa nhánh sau chết.
Tự luyện
Bài 1. Ba bạn Hải, Long, Cường chạy. Người thứ nhất đoán: "Hải nhất, Long nhì." Người thứ hai: "Hải ba, Long nhất." Mỗi người đúng một ý. Thứ tự?
Đáp án: Cường nhất, Long nhì, Hải ba. Nếu Hải nhất thì người thứ hai phải đúng "Long nhất" — trùng vị trí; vậy Long nhì, rồi "Long nhất" sai nên Hải ba.
Bài 2. Bốn bạn Ánh, Bích, Châu, Diệp. Lời đoán: "Châu tư, Ánh ba"; "Ánh nhất, Diệp nhì"; "Ánh nhì, Châu nhất". Mỗi lời đúng một ý.
Đáp án: Châu nhất, Diệp nhì, Ánh ba, Bích tư. Nếu Ánh nhất thì lời thứ ba sai cả hai ý; vậy Diệp nhì, kéo theo "Ánh nhì" sai, "Châu nhất" đúng, "Châu tư" sai, "Ánh ba" đúng.
Bài 3. Lập bảng xong thấy có hai thứ tự cùng khớp mọi lời đoán. Đề có lỗi không?
Đáp án: Đề không mâu thuẫn nhưng thiếu dữ kiện. Trả lời đúng là nêu cả hai thứ tự, hoặc thêm một lời đoán để loại bớt.
Dùng vào đâu
Dạng "đúng một nửa" có trong đề toán tư duy tiểu học, THCS và trong tuyển tập câu đố cổ điển. Ở mức sâu hơn, đây là một bài toán thoả mãn ràng buộc: mỗi lời đoán là một ràng buộc "đúng một trong hai", và mỗi lần chọn nhánh là một lần thử – lùi. Ai học lập trình sẽ gặp lại đúng thao tác này trong thuật toán quay lui (backtracking) và trong các bộ giải ràng buộc. Với người không học máy tính, kỹ năng mang về là thói quen kiểm cả hai nhánh trước khi tuyên bố có đáp án.
Câu hỏi thường gặp
Mỗi người đoán đúng một nửa nghĩa là gì?
Mỗi người đưa ra hai ý và đúng chính xác một ý: không được sai cả hai, cũng không được đúng cả hai. Nhiều người quên vế "không được đúng cả hai" nên ra thừa đáp án.
Nên bắt đầu giả sử từ lời đoán nào?
Chọn lời đoán có ý chạm tới nhiều lời đoán khác, ví dụ một ý về vị trí nhất mà người khác cũng nhắc tới. Giả sử ý đó đúng sẽ kéo ra nhiều hệ quả nhất, nhanh gặp mâu thuẫn hoặc nhanh ra thứ tự.
Có cần lập bảng 24 thứ tự cho bốn người không?
Không cần. Chia nhánh theo hai ý của một người là đủ, mỗi nhánh suy tiếp sẽ tự loại phần lớn khả năng. Bảng nhánh vẫn phải phủ mọi khả năng của người được chọn.
Nếu có đồng hạng thì sao?
Đề phải nói rõ. Khi cho phép đồng hạng, hai ý "An nhất" và "Dũng nhất" có thể cùng đúng, nên mọi suy luận dựa trên "vị trí không trùng" phải bỏ, và số khả năng tăng lên đáng kể.
