Bốn anh lính đang bị địch truy kích phải vượt qua một cây cầu mới được an toàn. Do bị bom tàn phá nên cây cầu chỉ cho phép tối đa 2 người qua cùng một lúc và phải mang theo đèn (nếu không sẽ rớt vào các hố do bom phá :( ). Bốn anh lính chỉ có một cây đèn duy nhất. Do tình trạng bị thương nên các anh lính qua cầu mất thời gian lần lượt là 10, 5, 2, 1 phút. Hãy tìm phương án để các anh lính qua cầu an toàn và tốn thời gian ít nhất.
Rút ra bài học gì? Tổng quát hóa bài toán?
Do tốc độ qua cầu của 2 người phụ thuộc vào tốc độ người đi chậm hơn, nên cứ cho anh đi nhanh nhất cầm đèn mà đi cùng với từng người một.
3 lần qua cầu với 3 người đi chậm, 2 lượt cầm đèn quay về
minT=2+5+10+2*1=19 phút