TransWikia.com

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

Puzzling Asked on April 1, 2021

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 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:

  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.

3 Answers

My analysis:


To summarise:

Answered by Weather Vane on April 1, 2021

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.

Answered by GAB on April 1, 2021

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.

Answered by Bass on April 1, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP