How do I find the least number of times a shuttle can travel from one place to another?

Question

I often see this situation in exams and I'd like to know if there is any kind of algorithm or shortcut that I can use to solve this puzzle instead of just guessing.

The problem is as follows:

A space station must be evacuated to a nearby spacecraft which offered help. Four astronauts are trapped in the space station with only one rescue shuttle available to carry them to the other spaceship. However the shuttle has two major limitations; the first is that it has to be piloted manually and the second is that it has a maximum capacity of 100 kilograms, which is exactly the weight of Terry, the first astronaut. The other three, Henry, Charles and James have lesser weights, 52, 46 and 49 kilograms respectively. James, however, does not know how to pilot the rescue shuttle. After thinking, they came up with a solution and found a way to transport all the four to the nearby spaceship. What is the least number of times the rescue shuttle must cross, to carry the astronauts?.

The alternatives given in my book are as follows:

1. 9
2. 8
3. 7
4. 4

I don't know how to approach this puzzle. I thought that minimizing voyages would meant giving priority to the heaviest passenger first. But I'm confused about the condition which states that the rescue shuttle has to be piloted manually. Does it imply that to go back and fourth must always include a pilot on its way back to pick up the following passenger?

According to the answer sheet, the answer is 7, but I have no idea how to get there.

What sort of steps or algorithm (if any) can be used to solve this puzzle?

I found this in a collection textbook which doesn't indicate the author. I often see this situation in repeated scenarios including, ferries, elevators and so on.

Answer 1

Your question is a bit confusing, but here some answers:

We always need a passenger in the shuttle, going both ways. Since Terry is at the limit capacity, he is always alone on the shuttle, which mean that we need someone in the station to get the last pilot after Terry, since Terry can't be the last one.

Here how you can do it:

I can't prove that it is the best solution, but it easy to prove that 4 can't be a solution, since the answer need to be odd.

Answer 2

I don't think there can be a shortcut for the general version of the puzzle; if there were, you could very likely use the shortcut to solve the bin packing problem, which is known to be NP-hard. Finding a shortcut for solving that problem would prove that P equals NP, which would net you a million dollars on the spot.

This means that your best shot for a general solution is going to be to "try all the possibilities". You can of course choose the order in which to try, and you can use some heuristics to rule out some possibilities. However, the limitation of NP-hardness demands that every heuristic has to have some cases where it cannot be applied, or where it is ineffective.

Answer 3

My analysis:

- Clearly Terry the heaviest at $100$ kg cannot be the first off (because no-one can bring the rescue ship back) nor the last off (because someone has to bring the ship back for him).
- The only pairs who can share the journey are Henry + Charles or Charles + James.

Obviously the non-pilot James can't travel alone: so Charles must take him and return to the space station alone.
So after the first out-and-back the three people on the space station are Terry, Henry and Charles.

The only possibility next is for Henry and Charles to travel, and one of them returns alone.
So after the second out-and-back the two people on the space station are either Terry + Henry or Terry + Charles.

There is no point in either Henry or Charles leaving alone, because they only just returned.
So now the heaviest, Terry, leaves alone.
Then whichever pilot out of Henry and Charles is available, brings the rescue ship back.
So after the third out-and-back the two people on the space station are Henry and Charles.

Finally they both leave.
So that is $3$ return trips and $1$ single trip: $7$ journeys.

---

To summarise:

Charles takes James and returns.
Charles takes Henry and returns.
Terry leaves and Henry returns.
Charles and Henry leave.

The first two journeys can be swapped.

Answer 4

Working out a (conservative) lower bound:

You can carry $100$ kilos at once, but the lightest astronaut is Charles with $46$ kilos. So you can move at most $100-46=54$ kilos to the right side with each return. You have $247$ kilos to carry in total, so even if the last (returnless) trip outside carries $100$ kilos, at least $3$ returns would be necessary, so it must cross at least $7$ times.

The particular solution:

Let's get the heaviest people out of the way first, but the first trip outside has to involve $2$ people, or no one can return. Go outside with as much weight, but return with as little as possible. Never return with J.

Take H and C first, return with C.

Take J and C, return with C.

Take T, return with H.

Take C and H.