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

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 riddle instead of just guessing or trying to play Where's wally with the question.

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 had lesser weights, $$52$$, $$46$$ and $$49$$ kilograms respectively. The latter however does not know how to pilot the rescue shuttle. After thinking a wisely they came up with a solution and found a way to transport the all four to the nearby spaceship. How many times the least possible the rescue shuttle must cross to carry the astronauts?.

The alternatives given in my book are as follows:

$$\begin{array}{ll} 1.&9\\ 2.&8\\ 3.&7\\ 4.&4\\ \end{array}$$

I don't know really what can sort of thing should I do to solve this riddle. In my attempt to solve I thought that the way to minimize the 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?.

By checking on the answers sheet the answer supposedly is $$7$$ but I have no idea how to get there.

Can somebody guide me on exactly which sort of steps or algorithm (if any) can be used to solve this riddle?.

Regarding the source of this problem. I found it in a collection textbook which doesn't indicate the author. It is such reason that I hope somebody could help me here as I often see this situation in repeated scenarios including, ferries, elevators and so on.

Your question is a bit confusing, but here some answers : We always need a passenger in the shutle, in boyh way. since Terry is at the limit capacity, he is always alone on the shutle, whitch 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.

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.

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.