Có 5 cái hang nằm thẳng hàng, một hang trong đó có con cáo. Đêm nào cáo cũng chuyển sang hang liền kề bên cạnh, có thể trái hoặc phải, hoàn toàn ngẫu nhiên. Mỗi buổi sáng bạn có thể kiểm tra một hang bất kì, làm thế nào để chắc chắn bắt được cáo?
Với trường hợp có N hang, làm thế nào để bắt được cáo?
Xem lời giải
Đánh dấu các hang theo thứ tự từ trái qua phải là 1 tới 5. Gọi
- \(S_1\) là tập hợp các hang chẵn {2, 4}
- \(S_2\) là tập hợp các hang lẻ {1, 3, 5}
- \(h_i\) là hang con cáo ngày thứ \(i\)
Nếu \(h_1\) ∈ \(S_1\), ta có \(h_i\) ∈ \(S_1\) hoặc \(h_i\) ∈ \(S_2\) nếu \(i\) lẻ hoặc chẵn. Vì \(h_1\) ∈ \(S_1\), trong 3 ngày đầu tiên kiểm tra lần lượt 3 hang 2, 3, 4 chắc chắn sẽ bắt được cáo.
Nếu \(h_1\) ∈ \(S_2\), ta có \(h_i\) ∈ \(S_2\) hoặc \(h_i\) ∈ \(S_1\) nếu \(i\) lẻ hoặc chẵn. Vì \(h_4\) ∈ \(S_1\) nên trong ngày 4, 5, 6 kiểm tra lần lượt 3 hang 4, 3, 2 chắc chắn sẽ bắt được cáo.
Tóm lại, kiểm tra các hang như sau sẽ bắt được cáo.
| Ngày | 1 | 2 | 3 | 4 | 5 | 6 |
| Hang | 2 | 3 | 4 | 4 | 3 | 2 |
Với trường hợp N hang…
Nếu ban đầu cáo ở hang số chẵn, kiểm tra hang (2, 3, … N-1) trong N-2 ngày liên tiếp sẽ bắt được cáo.
Nếu không bắt được cáo nghĩa là ban đầu cáo ở hang số lẻ. Khi đó kiểm tra các hang (N-1, N-2, …, 2) trong N-2 ngày tiếp theo sẽ bắt được cáo.
Tóm lại, để bắt cáo ta cần kiểm tra lần lượt các hang 2, 3, …, N-1, N-1, N-2, …, 2 trong 2*(N-2) ngày.