The treasure hunt of Mr. Jones

Question

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.

Objective
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)

BONUS
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.

BONUS 2
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?

Answer 1

The site's layout is:

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:



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.

Answer 2

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:

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.

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.

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?

Answer 3

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)