Trong một kỳ thi Olympic Toán dành cho học sinh lớp 9 có bài toán "hiệp sĩ và kẻ lừa dối" khá thú vị. Bài toán gây nhiều khó khăn ...
Trong một kỳ thi Olympic Toán dành cho học sinh lớp 9 có bài toán "hiệp sĩ và kẻ lừa dối" khá thú vị. Bài toán gây nhiều khó khăn cho những ai lần đầu tiếp cận dạng toán như thế này.
30 người ngồi quanh một bàn tròn 30 chiếc ghế đánh số theo thứ tự từ 1 đến 30. Một số trong họ là hiệp sĩ, một số là kẻ lừa dối. Hiệp sĩ luôn nói thật còn kẻ lừa dối luôn nói dối. Mỗi người có đúng một người bạn trong số những người khác. Hơn nữa, bạn của hiệp sĩ là một kẻ lừa dối và bạn của kẻ lừa dối lại là một hiệp sĩ.
Mỗi người đều được hỏi: "Có phải bạn của anh đang ngồi cạnh anh không?". 15 người ngồi ở vị trí mang số lẻ trả lời: "Đúng".
Tìm số người ngồi ở vị trí mang số chẵn cũng trả lời: "Đúng".
Từ đề bài ta suy ra trong 30 người có đúng 15 cặp hiệp sĩ – kẻ lừa dối là bạn của nhau. Ta có thể dễ dàng đoán được đáp số của bài toán bằng cách “giả định” 15 người ở vị trí lẻ đều là hiệp sĩ. Khi đó, dĩ nhiên bạn của họ đều ngồi cạnh ở các vị trí chẵn và đều là kẻ lừa dối, do đó không có ai nói “Đúng”. Đáp số là 0.
Tuy nhiên, đó chỉ là dự đoán đáp số chứ không phải lời giải. Với cách hỏi ở đề bài, ta biết đáp số là 0. Nhưng để khẳng định điều này, ta phải chứng minh chứ không chỉ là đưa ra một ví dụ như vậy.
Bí quyết của lời giải là ở nhận xét quan trọng sau: Trong 2 người là bạn của nhau, chỉ có đúng 1 người nói “Đúng” cho câu hỏi "Có phải bạn của anh đang ngồi cạnh anh không?".
Thật vậy, nếu có hai người (1 hiệp sĩ và 1 kẻ lừa dối) là bạn của nhau. Xét 2 trường hợp:
1) Nếu họ ngồi cạnh nhau thì hiệp sĩ sẽ nói "Đúng", còn kẻ lừa dối nói “Không”.
2) Nếu họ không ngồi cạnh nhau thì hiệp sĩ nói “Không”, còn kẻ lừa dối nói “Đúng”.
Như vậy, vì ta có 15 cặp bạn nên ta có đúng 15 câu trả lời “Đúng”. Vì cả 15 người ở vị trí mang số lẻ đã nói “Đúng” nên tất cả những người ở vị trí số chẵn đều nói “Không”. Tức là đáp số bằng 0.
Đề bài toán "Hiệp sĩ và Kẻ lừa dối"
30 người ngồi quanh một bàn tròn 30 chiếc ghế đánh số theo thứ tự từ 1 đến 30. Một số trong họ là hiệp sĩ, một số là kẻ lừa dối. Hiệp sĩ luôn nói thật còn kẻ lừa dối luôn nói dối. Mỗi người có đúng một người bạn trong số những người khác. Hơn nữa, bạn của hiệp sĩ là một kẻ lừa dối và bạn của kẻ lừa dối lại là một hiệp sĩ.
Mỗi người đều được hỏi: "Có phải bạn của anh đang ngồi cạnh anh không?". 15 người ngồi ở vị trí mang số lẻ trả lời: "Đúng".
Tìm số người ngồi ở vị trí mang số chẵn cũng trả lời: "Đúng".
 |
| Ảnh minh họa |
Lời giải bài toán "Hiệp sĩ và Kẻ lừa dối"
Từ đề bài ta suy ra trong 30 người có đúng 15 cặp hiệp sĩ – kẻ lừa dối là bạn của nhau. Ta có thể dễ dàng đoán được đáp số của bài toán bằng cách “giả định” 15 người ở vị trí lẻ đều là hiệp sĩ. Khi đó, dĩ nhiên bạn của họ đều ngồi cạnh ở các vị trí chẵn và đều là kẻ lừa dối, do đó không có ai nói “Đúng”. Đáp số là 0.
Tuy nhiên, đó chỉ là dự đoán đáp số chứ không phải lời giải. Với cách hỏi ở đề bài, ta biết đáp số là 0. Nhưng để khẳng định điều này, ta phải chứng minh chứ không chỉ là đưa ra một ví dụ như vậy.
Bí quyết của lời giải là ở nhận xét quan trọng sau: Trong 2 người là bạn của nhau, chỉ có đúng 1 người nói “Đúng” cho câu hỏi "Có phải bạn của anh đang ngồi cạnh anh không?".
Thật vậy, nếu có hai người (1 hiệp sĩ và 1 kẻ lừa dối) là bạn của nhau. Xét 2 trường hợp:
1) Nếu họ ngồi cạnh nhau thì hiệp sĩ sẽ nói "Đúng", còn kẻ lừa dối nói “Không”.
2) Nếu họ không ngồi cạnh nhau thì hiệp sĩ nói “Không”, còn kẻ lừa dối nói “Đúng”.
Như vậy, vì ta có 15 cặp bạn nên ta có đúng 15 câu trả lời “Đúng”. Vì cả 15 người ở vị trí mang số lẻ đã nói “Đúng” nên tất cả những người ở vị trí số chẵn đều nói “Không”. Tức là đáp số bằng 0.
Theo Soha. Người đăng: Sơn Phan.
