4
$\begingroup$

You belong to an intelligence agency that is monitoring some terrorists. There are three of them in the Hideout A with three hostages and a bomb. Unfortunately, this hideout is extremely secure. But there is a chance to get them: inside informants report that they are leaving for the Hideout B in the next morning. As soon as they get all there (terrorists and hostages), the agency is going to surprise them. What you know is:

  • There are 3 terrorists, 3 hostages and 1 bomb to be transported;
  • They only have one horse that will transport them from Hideout A to Hideout B or back, if needed;
  • The horse needs a rider (terrorist or hostage) to move;
  • The horse only supports 2 persons, or 1 person and the bomb;
  • The journey takes the whole day, and the horse needs to rest until the next morning;
  • If there are more hostages than terrorists in one hideout, they will fight, so the terrorists will plan to avoid this. Hostages alone are permitted, though;
  • The hostages cannot escape in the desert, so they will ride the horse to the correct hideout as requested.

Horse travelling in the desert

So, assuming that the terrorists are perfect strategists, what would be the minimum number of days for them to leave completely the Hideout A and move all (terrorists, hostages and the bomb) to the Hideout B?

$\endgroup$
  • 2
    $\begingroup$ So they made a perfect plan to move everything to Hideout B, and then get surprised? And what is "my" job (as intelligence agency) here? Just monitoring them? Or helping them do the planning? $\endgroup$ – WhatsUp Oct 30 '19 at 0:45
5
$\begingroup$

My try:

I will assume that, in the rule "if there are more hostages than terrorists in one Hideout...", it doesn't count if there are no terrorists in that Hideout. Otherwise the game is simply impossible.

Terrorists = T, Hostages = H, Bomb = B. The sequence of horse-riders for each day:

TH, T, TB, T, HH, H, TT, TH, TT, H, HH, H, HH

This completes the task in

13 days.

About the optimality:

An obvious lower bound is 11 days, and I wasted 1 round by letting TH ride back. This is the only meaningful option when there are TH in Hideout A and TTHH in HideoutB.
But I'm puzzle by the role played by the Bomb. It seems that there are many chances to move it to the other side, and it just adds one more round (2 days) to the result.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ You are right, I included a note about the allowance of hostages alone in one hideout. $\endgroup$ – Chaotic Oct 30 '19 at 13:34
  • 1
    $\begingroup$ after the beginning of your fourth day, the hostage would be able to inactivate or hide the bomb, (the bomb is a "sine qua non" of the hostage-terrorist difference) and so it is an immediate fail of the transport, but in this sense it is impossible to complete the mission, so the answer with 13 days is correct $\endgroup$ – balazs.com Oct 30 '19 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.