Đề bài: Bốn cô gái A, B, C, D muốn đi qua một đường hầm tối nhưng họ chỉ có một ngọn đuốc. Biết A, B, C, D mỗi người lần lượt có thể đi qua đường hầm trong 1 phút; 2 phút; 5 phút; 10 phút. Giả sử rằng, họ cần đuốc để đi qua mỗi lần và đường hầm cho phép tối đa 2 cô gái đi qua trong một lần.
Hỏi số thời gian ít nhất để cho cả 4 cô gái đi qua được đường hầm là bao nhiêu? (Chú ý: Nếu 2 người cùng đi một lượt qua đường hầm thì thời gian chung tính theo thời gian của cô gái đi chậm hơn).
Sai lầm thường gặp
Do cô A có thời gian đi ít nhất nên rất nhiều người chọn giải pháp cho A đi qua lại đường hầm nhiều lần theo các bước sau đây:
1. AB cùng đi mất 2 phút; 2. A quay lại mất 1 phút;
3. AC cùng đi mất 5 phút; 4. A quay lại mất 1 phút;
5. AD cùng đi mất 10 phút.
Với giải pháp này thì tổng thời gian để cả 4 người đi qua đường hầm là 19 phút.
Hướng dẫn giải
Rất nhiều bạn đọc đã tham gia giải và bình luận cho bài toán này. Đây là một bài toán có tính chất “vận trù học” - sắp xếp tối ưu lộ trình thực hiện công việc nào đó.
Để giảm thời gian đi thì xu hướng ta ghép 2 người đi nhanh nhất (AB) và 2 người đi chậm nhất (CD) cùng đi một lượt. Từ đó ta có giải pháp sau đây:
1. AB cùng đi mất 2 phút; 2. A quay lại mất 1 phút;
3. CD cùng đi mất 10 phút; 4. B quay lại mất 2 phút;
5. AB cùng đi mất 2 phút.
Với giải pháp này thì tổng thời gian để cả 4 người đi qua đường hầm là 17 phút.
Chú ý: Một số người cho rằng cần phải chứng minh bằng toán học giải pháp 17 phút là tối ưu nhất. Thực tế đối với bài toán có ít đối tượng thì ta có thể dùng các phép thử để so sánh các giải pháp là đủ. Việc chứng minh khái quát cho bài toán là không cần thiết.
Trần Phương