[NG] Giáo viên chia sẻ cách giải bài toán đi qua hầm tối

Bài toán đi qua hầm tối như sau: Một gia đình gồm 4 người kí hiệu là A, B, C, D cùng nhau đi du lịch mạo hiểm. Họ cần vượt qua một hầm tối. Đường hầm này có không gian, kích thước cùng rất nhiều yếu tố nguy hiểm và có duy nhất 1 ngọn đuốc. Vì vậy, mỗi lượt chỉ có tối đa 2 người chung đuốc đi qua. Giả định thời gian đi của bốn người A,B,C,D lần lượt là 1 phút, 2 phút, 5 phút và 10 phút. Câu hỏi đặt ra là tổng thời gian ít nhất để tất cả A,B,C,D cùng đi qua hầm tối là bao nhiêu?

Chia sẻ về xuất xứ của bài toán trên, thầy Trần Phương cho biết, bài toán ra đời vào nửa cuối thế kỉ 20 và rất nổi tiếng trên thế giới. Tính đến nay, bài toán này đã xuất hiện tại hơn 100 quốc gia.

Theo thầy Phương, bài toán này có hai phương án giải. Phương án thứ nhất có tên gọi là thủ “lĩnh anh hùng cá nhân” (hay còn gọi là thủ lĩnh ôsin). Trong đó, người thủ lĩnh sẽ đóng vai trò phục vụ, lần lượt đưa từng người còn lại qua hầm. Đây là cách giải mà 95% dân số trên thế giới lựa chọn và đưa ra trong vòng 5-10 phút suy nghĩ.

Thầy Trần Phương phân tích về phương pháp “thủ lĩnh osin”: Cụ thể, người A có thời gian đi nhanh nhất nên A sẽ đảm nhiệm ví trí người dẫn đường. Đầu tiên, A sẽ đi cùng B qua hầm, thời gian mất 2 phút. Sau đó A quay lại đưa C qua hầm, thời gian mất 5 phút. Và cuối cùng A quay về đưa nốt D qua hầm, thời gian mất 10 phút. Trong đó, A có 2 lần một mình quay lại hầm để đón C và D, mỗi lần mất thêm 1 phút.

Như vậy, tổng thời gian để cả 4 người đi qua đường hầm là (2+1) + (5+1)+10 = 19 phút.

Tuy nhiên, phương án giải được thầy Phương đánh giá là tiết kiệm thời gian hơn cả đó là phương án mang tên ” ngưu tầm ngưu mã tầm mã”. Theo đó, những người đi nhanh sẽ đi chung với nhau và những người đi chậm sẽ đi chung với nhau. Trong trường hợp này, người A sẽ cùng người B đi qua hầm trước. Tiếp đó, A sẽ để B ở đó và quay lại đưa đuốc cho C để C và D cùng nhau đi qua hầm. Cuối cùng, B sẽ cầm đuốc quay lại đón A cùng đi qua hầm. Ở phương án này, A và B mỗi người sẽ có một lượt quay lại hầm để đưa đuốc, mất thêm số thời gian lần lượt là 1 phút và 2 phút.

Như vậy, tổng thời gian để cả 4 người cùng đi qua hầm là (2+1)+(10+2)+2 = 17 phút.

Đối với bài toán trên, thầy Trần Phương đưa ra thêm phần bình luận chỉ ra những yếu tố mới để bạn đọc có thể nhìn bài toán này một cách sâu sắc hơn. Thứ nhất, trong trường hợp có 4 người, cho dù có các cách sắp xếp cặp lượt đi khác nhau nhưng tổng số lượt đi là bất biến: 4 người sẽ có 5 lượt đi.

Bên cạnh đó, thầy Trần Phương cho biết, chúng ta thường quan niệm phương án thứ nhất, để người thủ lĩnh lần lượt đưa từng người qua hầm là bất lợi, không tiết kiệm thời gian bằng phương pháp “ngưu tầm ngưu mã tầm mã”. Nhưng sự thật không phải như thế. Trong trường hợp thời gian đi của mỗi người trong nhóm tăng lên thì sử dụng phương pháp “thủ lĩnh ô sin” là tối ưu nhất. Qua đó, thầy cũng nhấn mạnh, không thể khẳng định phương pháp “ngưu tầm ngưu mã tầm mã” luôn vượt trội hơn trong mọi hoàn cảnh. Điều này còn phụ thuộc vào thời gian đi của từng người. Đây cũng chính là nguyên nhân khiến bài toán không nâng lên thành dạng tổng quát được.

Xem đầy đủ lời giải bài toán Đi qua hầm tối nhanh nhất của thầy Trần Phương tại đây.

(Nguồn: HOCMAI)