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,9The 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
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.
No comments:
Post a Comment