Sunday, January 23, 2011

Resource management

In the middle of the confounded desert, there is the lost city of "Ash". To reach it, I will have to travel overland by foot from the coast. On a trek like this, each person can only carry enough rations for five days and the farthest we can travel in one day is 30 miles. Also, the city is 120 miles from the starting point.

What I am trying to figure out is the fewest number of persons, including myself, that I will need in our Group so that I can reach the city, stay overnight, and then return to the coast without running out of supplies.

How many persons (including myself) will I need to accomplish this mission?

Reach for the sky!!

Reach for the sky!! is based on hollow lottery balls.Here is how it is played.

Your adversary is given 100 identical pieces of paper.In a room hidden from your view, he writes a number on each one - he can choose any value in the range 1 to 1 million but without duplicates - then inserts them into small opaque envelopes.Subsequently, these papers aree given to an independent third party called the stuffer. The stuffer works in full view of you and adversory at all times. He shows you 100 hollow and empty lottery balls. He then shuffles the envelopes and inserts one envelope into the first lottery ball, another into second, and so on upto 100. After inserting each envelope, he screws the ball shut. These balls have been examined using drop tests, bounce tests, and resiliometric tests to be sure they all share the same physical properties.

The stuffer then puts the balls into a lottery machine. The lottery machine mixes the balls thouroughly until one comes out. Call the ball number 1. The ball is opened and you are told the value on the paper(paper value). You have the option to 'capture' that paper value or not. If you capture it, you put it in your capture pile and you have used up one capture. If you don't, it goes in the discard pile never to come out, though you may find it useful to remember the discarded paper values. Repeat this procedure for all 100 balls. You are allowed three captures altogether. Your goal is to capture the highest paper value written by your adversory. If you do, you win $100,000, else you lose $100,000.Should you engage inthis bet? If so, what is your probability of winning?

Q1.What would be a good strategy for the $100,000 Reach for the sky!! game, where you have three captures?Using that strategy, what would be your chances of winning?

- adapted from Puzzles for programmers and pros, by Dennis E. Shasha, Wiley india Ed 2007..