Bài toán tìm con mèo sau cánh cửa

Đề bài:

Một hành lang thẳng có năm cánh cửa dọc theo một bên. Đằng sau một trong các cánh cửa đó có một con mèo. Nhiệm vụ của bạn là tìm ra con mèo bằng cách mở đúng cánh cửa. Mỗi ngày bạn chỉ có thể mở một cánh cửa. Nếu con mèo ở đó, bạn thắng.

Nếu con mèo không ở đó, cánh cửa sẽ đóng lại, và bạn phải đợi đến ngày hôm sau trước khi bạn có thể mở cửa lại. Con mèo di chuyển không ngừng nghỉ và mỗi đêm nó chuyển đến ngồi sau một cánh cửa khác. Cánh cửa mà nó di chuyển tới sẽ là cánh cửa bên trái hoặc bên phải của vị trí nó đang ở.

Bạn cần bao nhiêu ngày để chắc chắn tìm được con mèo?

Bài toán đang yêu cầu bạn tìm một chiến lược để đảm bảo bạn sẽ bắt được con mèo trong một số ngày cố định, bất kể nó bắt đầu đằng sau cánh cửa nào và di chuyển đến đâu vào ban đêm. Chìa khóa để giải quyết vấn đề là bắt đầu với một số cửa nhỏ hơn, tìm ra mô hình và sau đó tăng số lượng cánh cửa.

Chúng ta hãy thử bắt đầu bài toán với trường hợp chỉ có ba cánh cửa. Nếu bạn mở cánh cửa ở giữa vào hai ngày liên tiếp, bạn sẽ đảm bảo bắt được con mèo, vì nếu con mèo không ở đằng sau cánh cửa ở giữa vào ngày thứ nhất, nó phải ở phía sau một trong hai cánh cửa ở hai đầu. Và nếu nó ở đằng sau một trong hai cánh cửa ở hai đầu vào ngày thứ nhất, nó không có lựa chọn nào khác ngoài việc di chuyển đến cánh cửa ở giữa vào ngày thứ hai.

Nếu có bốn cánh cửa, bạn có thể bắt được con mèo trong bốn ngày. Bạn có thể tìm được lời giải thích ngay trong đáp án bên dưới, nhưng trước đó, bạn hãy thử tự mình giải thích xem sao. Hãy nhớ rằng, con mèo chỉ di chuyển đến cánh cửa ngay bên phải hoặc bên trái của nó và có thể trở lại cánh cửa mà nó đã từng ngồi phía sau trước đây. Tin rằng bạn sẽ cảm thấy sung sướng khi tìm được lời giải thích.

>>>Đáp án

Võ Quốc Bá Cẩn

Giáo viên Toán, trường Archimedes Hà Nội