Problem #63 MEDIUM
The Trapped Miners
Scenario Game Theory Optimization Logic
Problem Statement
A rescue coordinator named Suraj receives an emergency call from an iron ore mine in Jharkhand. A tunnel collapse has trapped six miners underground. They are safe for now but need to reach the surface through a single narrow escape shaft.
The shaft can only be climbed by one or two miners at a time — it is too narrow for more. Each miner climbs at a different speed: Miner A takes 1 minute, Miner B takes 3 minutes, Miner C takes 5 minutes, Miner D takes 8 minutes, Miner E takes 9 minutes, and Miner F takes 12 minutes.
When two miners climb together, they move at the pace of the slower one. A head torch must be used in the shaft — it is pitch dark. There is only one head torch and it must be passed back down after each trip (it cannot be thrown).
The support team above estimates the tunnel will become dangerously unstable in 45 minutes.
Suraj grabs his notepad. 'We can get everyone out,' he says to his team. 'Let me show you how.'
Six miners with climbing times 1, 3, 5, 8, 9, and 12 minutes must escape a shaft one or two at a time, with one shared head torch that must be returned after each trip. What is the minimum total time to evacuate all six miners, and what is the optimal sequence?
Answer & Quick Explanation
Think you've got it? Click below to check your answer.
All six miners escape in 37 minutes. Optimal sequence: A+B up (3), A down (1), E+F up (12), B down (3), A+B up (3), A down (1), C+D up (8), B down (3), A+B up (3). Total: 37 minutes — 8 minutes before the tunnel becomes dangerous.
Detailed Editorial Solution
Want to see the step-by-step breakdown? Click below to reveal the editorial.
With 6 miners, the torch must make 5 upward trips and 4 return trips (11 trips total). The naive approach has the fastest miner (A=1min) escort each person individually, costing 1+3+1+5+1+8+1+9+1+12 = 41 minutes. The optimal approach batches slow pairs.
Step 1: Trip 1 up: A+B (3 min). Trip 2 down: A returns (1 min). Elapsed: 4 min.
Step 2: Trip 3 up: E+F together (12 min — the two slowest). Trip 4 down: B returns (3 min). Elapsed: 19 min.
Step 3: Trip 5 up: A+B (3 min). Trip 6 down: A returns (1 min). Elapsed: 23 min.
Step 4: Trip 7 up: C+D together (8 min — next slowest pair). Trip 8 down: B returns (3 min). Elapsed: 34 min.
Step 5: Trip 9 up: A+B (3 min). All 6 miners are up. Total elapsed: 37 minutes. Under 45 minutes ✓.
Key Insight:
The saving over naive (41 min vs 37 min) comes from batching the two slowest pairs (E+F=12, C+D=8) so their slow trips are paid only once each. The cost of extra return trips by fast miners is less than the savings from avoiding individual escort of slow miners.