Khi n người trên đảo lần lượt nói «Trong chúng ta có đúng 1 kẻ nói dối», «…đúng 2 kẻ nói dối», …, «…đúng n kẻ nói dối», thì nhiều nhất một câu đúng, nên có nhiều nhất một hiệp sĩ. Không thể không có hiệp sĩ nào (khi đó câu "đúng n" lại đúng), nên có đúng một hiệp sĩ: người nói «có đúng n − 1 kẻ nói dối». Mấu chốt của cả dạng bài là đổi cách đếm: thay vì xét 2ⁿ kịch bản, chỉ xét n + 1 khả năng của số kẻ nói dối.
Bài này giải bốn câu đố tự đặt về lời nói số lượng trên đảo hiệp sĩ (luôn nói thật) và kẻ nói dối (luôn nói sai): "đúng k", "ít nhất k", "nhiều nhất k", và cả nhóm cùng nói một câu. Mỗi câu có bảng kiểm theo số kẻ nói dối, có câu vô nghiệm, có câu hai đáp án.
Phương pháp: đếm theo số kẻ nói dối
Gọi D là số kẻ nói dối trong nhóm n người (D từ 0 đến n). Khi lời của mọi người đều nói về số lượng, chỉ cần biết D là biết được câu nào đúng, câu nào sai. Từ đó:
Với mỗi giá trị D, xác định những câu đúng.
- Người nói câu đúng phải là hiệp sĩ, người nói câu sai phải là kẻ nói dối. Đếm số kẻ nói dối suy ra từ bước 1.
- Giá trị D tự khớp (số kẻ nói dối suy ra bằng đúng D) là đáp án.
Với 10 người, cách này chỉ cần 11 dòng thay vì 1.024 kịch bản. Đây là lối nghĩ "tìm điểm bất động": giả định một con số, xem nó có tự tái tạo chính nó không.
Câu đố 1: năm người ở nhà văn hoá, «có đúng k kẻ nói dối»
Ví dụ minh hoạ tự đặt. Năm người đứng thành hàng ở nhà văn hoá đảo. Người thứ nhất nói: «Trong năm chúng ta có đúng 1 kẻ nói dối.» Người thứ hai: «…đúng 2 kẻ nói dối.» Cứ thế đến người thứ năm: «…đúng 5 kẻ nói dối.» Ai là hiệp sĩ?
Lời giải từng bước
Bước 1. Năm câu nói năm con số khác nhau về cùng một đại lượng, nên nhiều nhất một câu đúng. Vậy có nhiều nhất một hiệp sĩ, tức D ≥ 4.
Bước 2. Nếu D = 5 (không có hiệp sĩ nào), câu của người thứ năm "đúng 5 kẻ nói dối" đúng, mà người đó lại là kẻ nói dối. Mâu thuẫn.
Bước 3. Vậy D = 4: câu của người thứ tư đúng, người thứ tư là hiệp sĩ, bốn người còn lại nói câu sai, là kẻ nói dối. Đúng 4 kẻ nói dối: tự khớp.
| Giả định D | Câu đúng | Số hiệp sĩ suy ra | Số kẻ nói dối suy ra | Khớp D? |
|---|---|---|---|---|
| 0 | Không câu nào | 0 | 5 | Không |
| 1 | Người 1 | 1 | 4 | Không |
| 2 | Người 2 | 1 | 4 | Không |
| 3 | Người 3 | 1 | 4 | Không |
| 4 | Người 4 | 1 | 4 | Có |
| 5 | Người 5 | 1 | 4 | Không |
Kết luận: chỉ người thứ tư là hiệp sĩ. Tổng quát với n người: người nói "đúng n − 1" là hiệp sĩ duy nhất.
Câu đố 2: sáu cầu thủ bóng chuyền, «có ít nhất k kẻ nói dối»
Ví dụ minh hoạ tự đặt. Sáu cầu thủ đội bóng chuyền của đảo. Cầu thủ số 1 nói: «Trong đội có ít nhất 1 kẻ nói dối.» Số 2: «…ít nhất 2 kẻ nói dối.» … Số 6: «…ít nhất 6 kẻ nói dối.»
Lời giải từng bước
Bước 1. Nếu có D kẻ nói dối thì các câu "ít nhất 1", …, "ít nhất D" đúng, các câu còn lại sai. Số câu đúng là D (khi D ≤ 6).
Bước 2. Số câu đúng bằng số hiệp sĩ, tức 6 − D. Vậy D = 6 − D, suy ra D = 3.
Bước 3. Ba câu đúng là của số 1, 2, 3: họ là hiệp sĩ. Số 4, 5, 6 nói dối. Kiểm: đúng 3 kẻ nói dối, câu "ít nhất 3" đúng, câu "ít nhất 4" sai: khớp.
| Giả định D | Câu đúng | Số hiệp sĩ suy ra | Số kẻ nói dối suy ra | Khớp D? |
|---|---|---|---|---|
| 0 | Không câu nào | 0 | 6 | Không |
| 1 | Số 1 | 1 | 5 | Không |
| 2 | Số 1–2 | 2 | 4 | Không |
| 3 | Số 1–3 | 3 | 3 | Có |
| 4 | Số 1–4 | 4 | 2 | Không |
| 5 | Số 1–5 | 5 | 1 | Không |
| 6 | Số 1–6 | 6 | 0 | Không |
Kết luận: ba hiệp sĩ là số 1, 2, 3. Với đội năm người cùng kiểu lời nói, phương trình thành D = 5 − D, không có nghiệm nguyên: đề vô nghiệm. Kiểu lời "ít nhất k" chỉ có đáp án khi số người chẵn.
Câu đố 3: năm người bán hàng, «có nhiều nhất k kẻ nói dối»
Ví dụ minh hoạ tự đặt. Năm người bán hàng ở chợ đảo. Người thứ i (i từ 1 đến 5) nói: «Trong năm chúng ta có nhiều nhất i kẻ nói dối.»
Lời giải từng bước
Bước 1. Với D kẻ nói dối, câu "nhiều nhất i" đúng khi i ≥ D.
Bước 2, D = 0. Mọi câu đều đúng (i ≥ 0 luôn đúng), năm người là hiệp sĩ, số kẻ nói dối là 0. Tự khớp.
Bước 3, D ≥ 1. Các câu đúng là của người D, D + 1, …, 5: có 6 − D câu, tức 6 − D hiệp sĩ. Nhưng số hiệp sĩ phải là 5 − D. Hai số lệch nhau đúng 1, không bao giờ bằng. Loại mọi D ≥ 1.
| Giả định D | Câu đúng | Số hiệp sĩ suy ra | Số hiệp sĩ cần có (5 − D) | Khớp? |
|---|---|---|---|---|
| 0 | Người 1–5 | 5 | 5 | Có |
| 1 | Người 1–5 | 5 | 4 | Không |
| 2 | Người 2–5 | 4 | 3 | Không |
| 3 | Người 3–5 | 3 | 2 | Không |
| 4 | Người 4–5 | 2 | 1 | Không |
| 5 | Người 5 | 1 | 0 | Không |
Kết luận: cả năm người đều là hiệp sĩ. Đáp án duy nhất, và là trường hợp hiếm hoi một câu đố đảo mà không ai nói dối.
Câu đố 4: cả nhóm cùng nói một câu
Ví dụ minh hoạ tự đặt. Bảy người ngồi quanh bếp lửa, ai cũng nói cùng một câu: «Trong bảy chúng ta có đúng 3 kẻ nói dối.»
Lời giải từng bước
Bước 1, quan sát chung. Mọi người nói cùng một câu, nên câu đó hoặc đúng với tất cả, hoặc sai với tất cả. Vậy cả nhóm cùng loại: toàn hiệp sĩ hoặc toàn kẻ nói dối.
Bước 2, toàn hiệp sĩ. Khi đó D = 0, câu "đúng 3 kẻ nói dối" sai. Hiệp sĩ nói sai: loại.
Bước 3, toàn kẻ nói dối. D = 7, câu "đúng 3" sai: khớp với kẻ nói dối.
| Kịch bản | D | Câu "đúng 3 kẻ dối" | Khớp? |
|---|---|---|---|
| Bảy hiệp sĩ | 0 | Sai | Không |
| Bảy kẻ nói dối | 7 | Sai | Có |
Kết luận: cả bảy là kẻ nói dối. Nhưng nếu nhóm chỉ có ba người cùng nói câu này thì toàn hiệp sĩ cho câu sai, toàn kẻ nói dối lại cho câu đúng (D = 3): cả hai đều hỏng, đề vô nghiệm. Một con số trong đề đổi là kết luận đổi theo.
Bảng so sánh các dạng lời nói số lượng
| Người thứ i nói (n người) | Điều kiện tự khớp | Kết quả |
|---|---|---|
| «Có đúng i kẻ nói dối» | Đúng một câu đúng, D = n − 1 | Chỉ người n − 1 là hiệp sĩ |
| «Có ít nhất i kẻ nói dối» | D = n − D | n chẵn: nửa đầu hiệp sĩ; n lẻ: vô nghiệm |
| «Có nhiều nhất i kẻ nói dối» | Chỉ D = 0 khớp | Tất cả là hiệp sĩ |
| Ai cũng nói «Có đúng k kẻ nói dối» (1 ≤ k ≤ n) | Toàn kẻ nói dối và k ≠ n | k < n: toàn kẻ nói dối; k = n: vô nghiệm |
Tự luyện
- Năm người, người thứ i nói: «Trong chúng ta có đúng i hiệp sĩ.» Có bao nhiêu đáp án?
Đáp án: Hai. Gọi H là số hiệp sĩ. Nếu H ≥ 1 thì chỉ câu của người thứ H đúng, nên có đúng 1 hiệp sĩ, tức H = 1: người thứ nhất là hiệp sĩ. Nếu H = 0 thì không câu nào đúng, cả năm nói dối, cũng tự khớp. Đề có hai đáp án.
Năm người, người thứ i nói: «Có ít nhất i kẻ nói dối.»
Đáp án: Vô nghiệm, vì cần D = 5 − D mà 5 lẻ.
Bốn người cùng nói: «Số kẻ nói dối trong chúng ta là số chẵn.»
Đáp án: Cả nhóm cùng loại. Toàn kẻ nói dối thì D = 4, chẵn, câu đúng: loại. Toàn hiệp sĩ thì D = 0, chẵn, câu đúng: khớp. Cả bốn là hiệp sĩ.
Mười người, người thứ i nói: «Có đúng i kẻ nói dối.» Ai là hiệp sĩ?
Đáp án: Theo quy luật câu đố 1, chỉ người thứ chín.
Dùng vào đâu
Lối "giả định một con số rồi kiểm nó có tự khớp không" xuất hiện ở nhiều nơi: bài toán tìm điểm bất động trong toán, các câu hỏi tự tham chiếu kiểu "câu trả lời đúng cho câu hỏi này là đáp án C" trong đề luyện tư duy, hay khi lập trình viên kiểm một vòng lặp hội tụ. Với học sinh ôn thi học sinh giỏi, kỹ năng đổi biến đếm (từ "ai là ai" sang "có bao nhiêu") giúp bài toán từ hàng nghìn trường hợp còn chục dòng.
Dạng này cũng là bước chuẩn bị tốt cho câu đố bàn tròn, nơi mỗi người chỉ nói về hàng xóm của mình và câu hỏi chuyển thành "có thể có bao nhiêu hiệp sĩ".
Câu hỏi thường gặp
Mỗi người nói "trong chúng ta có đúng k kẻ nói dối" thì ai là hiệp sĩ?
Với n người nói lần lượt từ 1 đến n, các câu loại trừ nhau nên nhiều nhất một câu đúng. Không thể không có hiệp sĩ, nên có đúng một hiệp sĩ và số kẻ nói dối là n − 1. Người nói "đúng n − 1 kẻ nói dối" là hiệp sĩ.
Vì sao nên đếm theo số kẻ nói dối thay vì xét từng người?
Khi mọi lời nói chỉ nhắc tới số lượng, biết số kẻ nói dối là biết câu nào đúng. Thay vì 2ⁿ kịch bản, chỉ cần n + 1 dòng, mỗi dòng kiểm xem con số giả định có tự khớp không.
Câu đố "có ít nhất k kẻ nói dối" có đáp án khi nào?
Khi người thứ i nói "có ít nhất i kẻ nói dối", số câu đúng bằng số kẻ nói dối, nên cần số kẻ nói dối bằng một nửa số người. Đề chỉ có đáp án khi số người chẵn.
Nếu cả nhóm nói cùng một câu thì sao?
Cả nhóm phải cùng loại, vì một câu thì hoặc đúng với mọi người hoặc sai với mọi người. Chỉ cần thử hai kịch bản: toàn hiệp sĩ và toàn kẻ nói dối.
Câu đố đếm kẻ nói dối có thể vô nghiệm không?
Có. Ví dụ ba người cùng nói "có đúng 3 kẻ nói dối": toàn hiệp sĩ thì câu sai, toàn kẻ nói dối thì câu lại đúng. Không kịch bản nào khớp, tình huống đó không thể xảy ra trên đảo.
