Khi n người ngồi quanh bàn tròn và ai cũng nói «Người bên trái mình là kẻ nói dối», hiệp sĩ (luôn nói thật) và kẻ nói dối (luôn nói sai) phải ngồi xen kẽ. Vì vậy n phải chẵn và có đúng n/2 hiệp sĩ: 8 người thì 4 hiệp sĩ, 10 người thì 5. Nếu n lẻ, tình huống đó không thể xảy ra.
Bàn tròn là dạng câu đố đảo hiệp sĩ – kẻ nói dối hay gặp trong sách bồi dưỡng học sinh giỏi, vì nó buộc người giải lập luận về cấu trúc thay vì thử từng người. Bài này giải ba câu đố tự đặt: "người bên trái là kẻ nói dối", "cả hai người bên cạnh là kẻ nói dối" và "đúng một người bên cạnh là hiệp sĩ". Hai câu sau có nhiều đáp án, và cái hỏi là có thể có bao nhiêu hiệp sĩ.
Vì sao bàn tròn khác hàng ngang
Xếp hàng ngang thì người đầu và người cuối thiếu một bên, nên luôn có chỗ "thả lỏng". Bàn tròn khép kín: đi một vòng sẽ quay về người xuất phát, và mọi ràng buộc phải khớp cả ở chỗ nối. Chính chỗ khép vòng này sinh ra điều kiện chẵn lẻ và những giới hạn số lượng trong các câu đố dưới đây.
Quy ước: đánh số chỗ ngồi 1, 2, …, n theo chiều kim đồng hồ; "bên trái" của người số i là người số i − 1, và bên trái người số 1 là người số n.
Câu đố 1: tám người ở bữa cơm làng
Ví dụ minh hoạ tự đặt. Tám người ngồi quanh mâm cơm tròn trong bữa cơm chung cuối tuần của xóm. Ai cũng nói: «Người ngồi bên trái mình là kẻ nói dối.» Có bao nhiêu hiệp sĩ?
Lời giải từng bước
Bước 1, quan hệ từng cặp. Trên đảo, X nói "Y là kẻ nói dối" thì X và Y khác loại: X là hiệp sĩ thì Y nói dối; X là kẻ nói dối thì câu sai, Y là hiệp sĩ. Vậy mỗi người khác loại với người bên trái mình.
Bước 2, đi vòng quanh bàn. Người 1 khác loại người 8, người 2 khác người 1, người 3 khác người 2… Loại người đổi liên tục: hiệp sĩ, kẻ nói dối, hiệp sĩ, kẻ nói dối…
Bước 3, khép vòng. Sau 8 lần đổi, ta quay về người 1. Số lần đổi là chẵn nên người 1 trở lại đúng loại ban đầu: khớp. Có hai cách xếp (người 1 là hiệp sĩ hoặc là kẻ nói dối), cả hai đều có 4 hiệp sĩ.
| Kịch bản | Ghế 1 → 8 | Mỗi người khác loại người bên trái? | Chỗ khép vòng (ghế 1 với ghế 8) | Số hiệp sĩ |
|---|---|---|---|---|
| Ghế 1 là hiệp sĩ | H D H D H D H D | Có | Khác loại, khớp | 4 |
| Ghế 1 là kẻ nói dối | D H D H D H D H | Có | Khác loại, khớp | 4 |
(H là hiệp sĩ, D là kẻ nói dối.) Mọi cách xếp khác đều có ít nhất một cặp cạnh nhau cùng loại, làm câu của người bên phải trong cặp đó sai luật.
Nếu số người lẻ
Với 7 người, sau 7 lần đổi loại ta quay về người 1 với loại ngược loại ban đầu: mâu thuẫn. Bảy người không thể ngồi quanh bàn mà ai cũng nói câu đó.
| Số người n | Khép vòng được? | Số hiệp sĩ |
|---|---|---|
| Chẵn (6, 8, 10…) | Có, hai cách xếp | n/2 |
| Lẻ (5, 7, 9…) | Không | Vô nghiệm |
Câu đố 2: mười người, «cả hai người ngồi cạnh mình đều là kẻ nói dối»
Ví dụ minh hoạ tự đặt. Mười thành viên câu lạc bộ đọc sách ngồi quanh bàn tròn. Ai cũng nói: «Cả hai người ngồi cạnh mình đều là kẻ nói dối.» Có thể có bao nhiêu hiệp sĩ?
Lời giải từng bước
Bước 1, điều kiện cho hiệp sĩ. Câu của hiệp sĩ đúng: hai người cạnh hiệp sĩ đều nói dối. Vậy không có hai hiệp sĩ ngồi cạnh nhau. Mười ghế quanh bàn chứa được nhiều nhất 5 người đôi một không kề nhau, nên số hiệp sĩ K ≤ 5.
Bước 2, điều kiện cho kẻ nói dối. Câu của kẻ nói dối sai: không phải cả hai người cạnh mình nói dối, tức mỗi kẻ nói dối ngồi cạnh ít nhất một hiệp sĩ.
Bước 3, đếm. Mỗi hiệp sĩ có đúng hai người ngồi cạnh, nên "phục vụ" được nhiều nhất hai kẻ nói dối. Có 10 − K kẻ nói dối, mỗi người cần ít nhất một hiệp sĩ cạnh mình: 10 − K ≤ 2K, tức K ≥ 10/3, mà K nguyên nên K ≥ 4.
Bước 4, dựng ví dụ cho K = 4 và K = 5.
K = 5: H D H D H D H D H D. Hiệp sĩ nào cũng kẹp giữa hai kẻ nói dối; kẻ nói dối nào cũng có hai hiệp sĩ bên cạnh.
- K = 4: H D D H D D H D H D (ghế 1 đến 10). Kiểm từng kẻ nói dối: ghế 2 cạnh ghế 1 (H); ghế 3 cạnh ghế 4 (H); ghế 5 cạnh ghế 4; ghế 6 cạnh ghế 7; ghế 8 cạnh ghế 7 và 9; ghế 10 cạnh ghế 9 và ghế 1. Hiệp sĩ ở ghế 1, 4, 7, 9 đều có hai bên là kẻ nói dối. Khớp.
| Số hiệp sĩ K | Hiệp sĩ không kề nhau? | Đủ hiệp sĩ cho mọi kẻ nói dối? (10 − K ≤ 2K) | Kết luận |
|---|---|---|---|
| 0 | Có | Không (10 > 0) | Loại |
| 1, 2, 3 | Có | Không (9 > 2; 8 > 4; 7 > 6) | Loại |
| 4 | Có | Có (6 ≤ 8) | Khả thi |
| 5 | Có | Có (5 ≤ 10) | Khả thi |
| 6 trở lên | Không (buộc có hai hiệp sĩ kề nhau) | — | Loại |
Kết luận: có 4 hoặc 5 hiệp sĩ. Đề này có hai đáp án về số lượng, và rất nhiều cách xếp cụ thể; câu hỏi đúng phải là "có thể có bao nhiêu", không phải "ai là hiệp sĩ".
Câu đố 3: chín người, «đúng một người ngồi cạnh mình là hiệp sĩ»
Ví dụ minh hoạ tự đặt. Chín người ngồi quanh đống lửa trại trên bãi biển. Ai cũng nói: «Trong hai người ngồi cạnh mình có đúng một hiệp sĩ.» Có bao nhiêu hiệp sĩ?
Lời giải từng bước
Bước 1, hiệp sĩ. Câu đúng: mỗi hiệp sĩ có đúng một hiệp sĩ bên cạnh. Vậy hiệp sĩ đi theo từng cặp liền nhau, không có cụm ba và không có hiệp sĩ đứng lẻ.
Bước 2, kẻ nói dối. Câu sai: số hiệp sĩ cạnh kẻ nói dối là 0 hoặc 2.
Bước 3, xét chỗ tiếp giáp. Nếu có ít nhất một cặp hiệp sĩ, kẻ nói dối ngồi ngay sát cặp đó đã có một hiệp sĩ bên cạnh, nên phải có 2: người bên kia của kẻ nói dối cũng là hiệp sĩ, tức là đầu một cặp khác. Vậy giữa hai cặp hiệp sĩ chỉ có đúng một kẻ nói dối, và cả vòng có dạng lặp lại H H D.
Bước 4, đếm. Khuôn H H D dài 3 ghế, 9 ghế chứa đúng 3 khuôn: 6 hiệp sĩ, 3 kẻ nói dối. Còn nếu không có hiệp sĩ nào, mỗi kẻ nói dối có 0 hiệp sĩ bên cạnh, câu sai: cũng khớp. Vậy có hai khả năng: 0 hoặc 6 hiệp sĩ.
| Kịch bản | Ghế 1 → 9 | Lời hiệp sĩ | Lời kẻ nói dối | Kết luận |
|---|---|---|---|---|
| Toàn kẻ nói dối | D D D D D D D D D | — | 0 hiệp sĩ cạnh, câu sai, khớp | Khả thi (0 hiệp sĩ) |
| Khuôn H H D | H H D H H D H H D | Đúng một hiệp sĩ cạnh, khớp | 2 hiệp sĩ cạnh, câu sai, khớp | Khả thi (6 hiệp sĩ) |
| Có hiệp sĩ đứng lẻ, ví dụ H D D … | — | 0 hiệp sĩ cạnh, câu sai, không khớp | — | Loại |
| Cụm ba hiệp sĩ H H H | — | Người giữa có 2 hiệp sĩ cạnh, không khớp | — | Loại |
| Hai kẻ nói dối liền nhau sát cặp H H | — | — | Người sát cặp có đúng 1 hiệp sĩ cạnh, câu đúng, không khớp | Loại |
Nếu đề cho thêm "có ít nhất một hiệp sĩ", đáp án thu về duy nhất một con số: 6. Còn với 10 người thì khuôn H H D không lấp kín vòng (10 không chia hết cho 3), chỉ còn kịch bản toàn kẻ nói dối.
Ba công cụ cho mọi câu đố bàn tròn
- Đổi lời nói thành ràng buộc cục bộ: "người bên trái nói dối" thành "khác loại người bên trái"; "cả hai bên nói dối" thành "hiệp sĩ không kề nhau, kẻ nói dối có ít nhất một hiệp sĩ cạnh".
- Đi một vòng và xét chỗ khép: điều kiện chẵn lẻ, chia hết thường lộ ra ở đây.
- Đếm hai chiều: chặn trên (không kề nhau thì tối đa n/2) và chặn dưới (mỗi hiệp sĩ phục vụ tối đa hai người), rồi dựng ví dụ cụ thể cho từng giá trị còn lại.
Tự luyện
- Bảy người quanh bàn, ai cũng nói «Người bên trái mình là kẻ nói dối». Có bao nhiêu hiệp sĩ?
Đáp án: Không thể xảy ra: loại người phải đổi qua mỗi ghế, 7 lần đổi (số lẻ) khiến người 1 phải khác loại chính mình.
Sáu người, ai cũng nói «Người bên trái mình là hiệp sĩ».
Đáp án: Mỗi người cùng loại với người bên trái, nên cả bàn cùng loại: toàn hiệp sĩ hoặc toàn kẻ nói dối. Hai đáp án: 6 hoặc 0 hiệp sĩ.
Bảy người, ai cũng nói «Ít nhất một người ngồi cạnh mình là kẻ nói dối».
Đáp án: 4 hiệp sĩ. Kẻ nói dối nói sai nên cả hai bên là hiệp sĩ: kẻ nói dối đứng lẻ. Hiệp sĩ cần ít nhất một kẻ nói dối cạnh mình nên đi thành cụm 1 hoặc 2. Với L kẻ nói dối có L cụm hiệp sĩ, tổng 7 − L hiệp sĩ nằm giữa L và 2L, chỉ L = 3 thoả, nên có 4 hiệp sĩ.
Mười hai người, ai cũng nói «Cả hai người ngồi cạnh mình đều là kẻ nói dối». Có thể có bao nhiêu hiệp sĩ?
Đáp án: Cùng lập luận câu đố 2: K ≤ 6 và 12 − K ≤ 2K nên K ≥ 4. Có thể là 4, 5 hoặc 6.
Dùng vào đâu
Câu đố bàn tròn là cửa ngõ vào toán tổ hợp: ràng buộc "không kề nhau" và "mỗi người cạnh ít nhất một…" chính là các khái niệm tập độc lập và tập trội trên chu trình, gặp lại khi học lý thuyết đồ thị. Kỹ thuật "chặn trên, chặn dưới, rồi dựng ví dụ" là khuôn chung của rất nhiều bài thi học sinh giỏi dạng tìm giá trị lớn nhất, nhỏ nhất. Trong đời thường, nó giống bài toán xếp chỗ ngồi hay bố trí ca trực sao cho người nào cũng có người hỗ trợ bên cạnh.
Câu hỏi thường gặp
Ai cũng nói người bên trái là kẻ nói dối thì có bao nhiêu hiệp sĩ?
Hiệp sĩ và kẻ nói dối phải ngồi xen kẽ, nên số người phải chẵn và có đúng một nửa là hiệp sĩ. Ví dụ 8 người thì 4 hiệp sĩ. Nếu số người lẻ thì tình huống đó không thể xảy ra.
Vì sao số người phải là số chẵn?
Mỗi người khác loại người bên trái, nên loại người đổi qua từng ghế. Đi hết một vòng phải quay về đúng loại ban đầu, điều này chỉ xảy ra khi số lần đổi là số chẵn.
Mười người nói "cả hai người cạnh mình là kẻ nói dối" thì có mấy hiệp sĩ?
Có thể 4 hoặc 5. Hiệp sĩ không được ngồi cạnh nhau nên nhiều nhất 5, và mỗi kẻ nói dối phải ngồi cạnh ít nhất một hiệp sĩ nên cần ít nhất 4. Cả hai con số đều dựng được cách xếp cụ thể.
Câu đố bàn tròn khác câu đố xếp hàng thế nào?
Bàn tròn khép kín nên người đầu và người cuối cũng ngồi cạnh nhau. Điều kiện ở chỗ khép vòng sinh ra các ràng buộc chẵn lẻ, chia hết mà hàng ngang không có.
Làm sao kiểm đáp án câu đố bàn tròn cho chắc?
Lấy cách xếp cụ thể, đi từng ghế và kiểm lời người đó khớp loại, nhớ kiểm cả chỗ nối giữa ghế cuối và ghế đầu. Muốn chắc tuyệt đối thì viết chương trình duyệt hết 2ⁿ cách xếp.
