9.2 PROBABILISTIC ALGORITHMS 2519.2.6
- On a recent outing in the woods, you found a cave that had a map, a large
computer, and a magic button in the wall. The map indicates the location of
two islands that are each five days travel away from where you are now and
are also five days travel apart. (You can imagine that you and the two islands
are at the corners of an equilateral triangle.) A gnome appeared and told you
that when you press the button, a treasure consisting of 15 bars of pure gold
encrusted with diamonds, emeralds, rubies, and other priceless gems will
appear randomly on one of the two islands. The computer will begin to cal-
culate the location of the bars, but it will take four days to get the answer.
The computer is not portable and so you would have to wait four days for
its answer before you could start out. The problem is that there is a dragon
that takes one of these bars away every night to a place that is completely
inaccessible. The gnome has offered to tell you the correct location of the
gold bars in exchange for three of the bars. The gnome also tells you that
each time you return from your journey, you can press the button again, and
another treasure will randomly appear on one of the two islands.
Considerall of your possible choices and their potential return, and
decide what choice gives you the best possible return in the long run (in
other words, if you go treasure hunting a number of times). Your answer
should list all of the possibilities you have considered along with the amount
you would expect to get for each. You should assume that you will repeat
the treasure hunt at least 10 times. Because there is no limit on the number
of times you can go on the treasure hunt, you should not include the time
of your return to the cave in your analysis.
For problems 2 through 4, use the table of random numbers in Appendix A. For each
question, begin at the start of the table and work through until you reach either the
end of the problem or the end of the table. If you reach the end of the table, just con-
tinue from the first number of the table.
The function x^3 can be integrated directly, and the result is 0.25 in the range
0 to 1. Use the function Integrate from Section 9.2 with 20 darts. Com-
pare the answers you get after 5, 10, 15, and 20 darts with the correct
answer of 0.25. (Show all work.)
Run the Monte Carlo prime testing process for the number 182 (2 (^7)
- and for 255 (3 (^5) 17) showing the numbers chosen and the result
■9.2.6 EXERCISES