You are Mr. Jones, a famous treasure hunter.
You just arrived at a site where it is said a magnificent treasure lies.

After gathering info, here is what you know

There are 10 rooms connected as shown below.

1 -> 2,3
2 -> 1,4
3 -> 1,4,5
4 -> 2,3,6
5 -> 3,6,7
6 -> 4,5,8
7 -> 5,8,9
8 -> 6,7,10
9 -> 7,10
10 -> 8,9

The treasure is in room 9 or 10.
4 rooms are filled with deadly monstrosities.
Anyone who enters a deadly room will scream themselves to death.
Although the correct path is unknown, the treasure can safely be reached.

Unfortunately, Mr. Jones is getting too old for this stuff. So he decided to hire guides to do the risky exploration for him.
He also lost most of his money due to alimonies from fooling around too much in his prime. So he must keep it cheap.

Guide agency
Guide model 1
Type : Kamikaze
Price : 20$
Orders willing to take : 1
Number of rooms willing to explore per orders : No limits

Guide model 2
Type : Happy-go-lucky
Price : 30$
Orders willing to take : 2
Number of rooms willing to explore per orders : 3

Guide model 3
Type : Paranoid
Price : 40$
Orders willing to take : 5
Number of rooms willing to explore per orders : 1

Definition of order
An indication of a path to follow and a list of rooms to explore starting from any 100%-cleared room of choice.

Common sense
If you hear one of your guides scream, it won't give you precise indications on the location of a deadly room unless the order was to examine only one room.
After a room has been 100% cleared, you can go there without risks to yourself and give a new order to a guide if needed.

Find the cheapest way to hire guides to discover a safe path to the treasure starting from room 1 or 2. (Take into account all possible outcomes)

Let's assume life is sacred... What is the solution that will result in the fewest dead people while still trying to keep it as cheap as possible.

The guide agency is quite shifty. Odds are that if a guide gets into the treasure room before you, he will take the treasure and run away. Are changes to your plan needed to prevent that?

  • 1
    $\begingroup$ Hello puzzlers! I am trying a new kind of puzzles for your enjoyment. It is still a work in progress and I am not 100% satisfied with it yet but I would be tremendously grateful for any comments to help me improve onto the next one I might make if this kind of puzzles prove to be popular. Thank you! $\endgroup$ – stack reader Jan 23 '17 at 9:21
  • 1
    $\begingroup$ Does Mr Jones know that it is possible to reach the treasure? For example if both room 1 and 2 are deadly, and the deadliness of a room isn't cleared when an eplorer dies, there's no way to reach the treasure. Also, can the treasure rooms be deadly, too? $\endgroup$ – M Oehm Jan 23 '17 at 9:36
  • 1
    $\begingroup$ For guide model 3 (Paranoid), does his willingness to explore only 1 room per order mean that I can only get him to go into room 1 or 2, then he's done? What would be the purpose of 5 orders, then? $\endgroup$ – Xenocacia Jan 23 '17 at 9:37
  • 1
    $\begingroup$ Since we can start in either room 1 or room 2... Are they both considered 100% clear, or does that mean there are two entrance by wich we may start sending in our guides? $\endgroup$ – Dorian Fusco Jan 23 '17 at 10:08
  • 1
    $\begingroup$ Yeah, I know, but I wanted to optimize my number of orders to optimize the informations I get from a 30$ guide. I think such a move should be available, but then we'd need to limit the numbers of rooms a Kamikaze is willing to explore, otherwise it's too easy to exploit, as I stated above. $\endgroup$ – Dorian Fusco Jan 23 '17 at 16:06

The site's layout is:

Site plan

The site has two long corridors that are connected. There are two entrances to the west and two possible locations for treasure to the east.

Further, it is known ...

... that there are eactly four deadly rooms and that there is a safe route to the treasure. There are C(10, 4) = 210 possibilities to make 4 rooms of 10 deadly, but only 16 of them provide safe paths:

Safe routes

The lower routes are the upper outes mirrored along the site's principal symmetry axis. Basically, there is one cross connection in each of the possible paths. The principal, west-east path can either contnue along the same corridor or along the other corridor after the cross connection. The cross connection may be in the starting or treasure rooms.

A possible first draft for a strategy might be:

Send a paranoid scout to room 1. He will survive in 9 of 16 cases.

If he dies, it is clear that the path must be one of the last seven above. Go to room 4 via room 2, which both are clear, and send a paranoid scout to room 6, 8 and 10, each time following him after clearing a room. Whether the scout dies or not, it is clear which layout the site has.

If the first scout survives, send him to room 3, 5, 7, and 9, each time following him after he has cleared a room. Again, whether the scout dies or survives, the layout of the site should be clear. We have now used our 5 orders on this scout. If he survives, it is not clear whether room 10 is deadly or not, but the path to it leads via room 9. If the treasure is in room 9, room 10 need not be entered.

The cost of this approach is \$40 in 9/16 of all cases and \$80 in the rest, giving an expected cost of \$57.50.

If the first scout survies the first step, he will survive in 5 of the 9 remaining cases. The second scout will survive in 4 of the 7 cases. That means 5 cases don't lose any lives. 4 + 4 lose one life and three cases lose two lives, giving an expected loss of 11/16 or 0.6875 lives.


Kamikazes all the way.

Send the #0 kamikaze forward 2 spaces (spaces 1,3) If he lives, then we're in the first 8 scenarios from M Oehm's answer. If he's dead, it's the last 8 scenarios. Since the 2 options are mirror images. I'll just paste the first 8: Upper 8 Possibilities

For the remaining 8, when visited from the top row exactly one of the squares marked in yellow will not result in a scream. May as well check them in order. First kami scout is "lucky" and has 5/8 where he stays alive.
Test Order
So: 1. kamikaze goes all 5 spaces $40 total, 5/8. 2. kamikaze goes 4 spaces then down 1. $60, 1/8 3. kamikaze goes 3 spaces then down 1. $80, 1/8 The last yellow square is the answer if the #3 kami screamed. $80, 1/8 Total cost: ($40 * 5/8 + $60 * 1/8 + $80 * 1/8 + $80 * 1/8) = $52.50
Note: If a happy-go-lucky was willing to work for 1 penny less, I could use a happy in-place of the first/second kamikaze. Half the time he'd survive to use his second order (save \$10). Half the time he wouldn't (extra \$10 cost).

Despite using all kamikazes, the cost in lives is surprisingly "low":
0. kami: 50-50 survival odds (4/8 chance of death) 1. kami: 5/8 survival odds (3/8 chance of death) 2. kami: 5/8 + 1/8 = 6/8 (2/8 chance of death) 3. kami: 6/8 + 1/8 = 7/8 (1/8 chance of death) Expected casualties is: 10/8 = 1.25

Bonus 2
Very similar to the base scenario, but test only the bottom 3 yellow squares.
Bonus 2 order
Cost is:
$40 2/8 $60 2/8 $80 4/8 = $65

And the lives lost is:
0. kami: 50-50 survival odds (4/8 chance of death) 1. kami: 2/8 survival odds (6/8 chance of death) 2. kami: 2/8 + 2/8 = 4/8 (4/8 chance of death) 3. kami: 4/8 + 2/8 = 6/8 (2/8 chance of death) You: 7/8 (1/8 chance of death) Expected Casualties is: 17/8 = 2.125
Warning: You want the #1 kamikaze dead (2nd one sent). If he survives you're stuck with a choice, pay a scout $20 to take the 50-50 risk of death for treasure. Or do it yourself. Since you're nearly bankrupt, what have you got to lose?
Are you feeling lucky?


Mr Jones can get to the treasure room by spending:

\$60 or up to \$100 depending on the rules as discussed later.

First we have to notice, that the room layout forms a ladder, for lack of any graphical skills, ASCII will have to do:

1 - 3 - 5 - 7 - 9
|   |   |   |   |
2 - 4 - 6 - 8 - 10

Now its worth noticing that we should first find out which of the two rooms (1, 2) is safe. Seeing as in 50% of cases we will lose this guide, i propose hiring a Kamikaze.

Let's assume that room 1 is safe. Knowing that the layout has 4 terrible rooms, there are now only a few options left. We know room 3 is safe as well, because the treasure room is reachable. So the layouts possible are:

+ - good

x - bad

++xxx   +++xx   ++++x   +++++   +++++   +++++   +++++   +++++ 
x++++   xx+++   xxx++   xxxx+   xxx+x   xx+xx   x+xxx   +xxxx

We can notice that now what we want is to push forward to see how far we can continue along the top row. If at any point we encounter a terrible room, we know the rest of the path leads along the bottom row and we don't need to hire anybody else because we know it's clear. (In case this doesn't fit the 100% clear-ness rule, we hire a kamizae to clear the path which is obviously clean)

So, now we hire a Paranoid and send him to the next room in the row, clearing them one by one. Once we reach the end ( room 9 ) and still haven't found the treasure (in room 9) then we know room 10 is clear and has the treasure, and we can use the paranoid to clear that room as well, or like i said, enter it knowing its clear.

Now, a discussion about starting by hiring a paranoid (because we could be lucky and get room 1 to be clear and have 4 more uses of a paranoid)

If we have to clear a room to enter it, then we could hire a paranoid first - he could clear up to the last room in the row, then we hire a kamikaze to clear room 10 if we were unlucky. However if we hit a terrible room first - we hire a kamikaze to clear the bottom row which we know is safe. So total cost is again $60.

However, if the first room happens to be a terrible room, then we're pretty much in square one, we have to hire another paranoid for \$40 to finish the job, and another \$20 for a kamikaze if we're unlucky again.

If we only have to be sure that a room is clear to enter it, without having to clear it physically, then my earlier approach gives us a constant cost of \$60 (first \$20 for a kamikaze for room 1. Then \$40 for a paranoid for the rest)

  • $\begingroup$ If room 1 is safe, there is still one more possible case, where the terrible rooms are 3, 5, 7, 9. $\endgroup$ – justhalf Jan 25 '17 at 2:47
  • $\begingroup$ @justhalf that's true, however if we send our paranoid to check room 3, he will die, and we know the only route to the treasure is 1->2->4->6->8->10, so it still falls into my approach. To quote myself: "[...] what we want is to push forward to see how far we can continue along the top row. If at any point we encounter a terrible room, we know the rest of the path leads along the bottom row" - in this case 'at any point being room 3. $\endgroup$ – Piotr Pytlik Jan 25 '17 at 14:22

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.