A box is filled with 'N' slips of paper. On each slip of paper is written some positive integer (note that any positive integer may appear on the slips - not just the integers from 1 to 'N'). The integers do not necessarily appear in any sequence or pattern. Each of the slips has a different integer on it, so there is just one slip with the greatest integer.

A person who has no prior knowledge of which numbers appear on the slips - but who does know that there are 'N' slips - is to blindly pull slips from the box one by one. The person looks at each slip, then either agrees to accept that number (of Rupees) and quit or decides to go on and choose another slip.

Note that the person looks at each slip as he/she proceeds, and then decides whether to quit or to go on. That person can go forward, but cannot go back. If no choice is made by the time the 'N'th slip is reached, then the person must accept the number (of Rupees) on the 'N'th slip.

Does there " EXIST " a 'Best Strategy' for the person ? If " YES ", then what is that strategy ? (Here the term " Best Strategy" means that the person will get the greatest amount of Rupees).

Let r be the number of slips that we let pass by before we begin to look for the largest seen so far and take that. First let's get a formula for the probability that using this r will lead to success in getting the highest of all n slips.

This results in a probability that depends on r, of p(r)=((n-r)/n)(1/(n-r))(r/r + r/(r+1) + ... + r/(n-1)) = (r/n)(1/r + 1/(r+1) + ... + 1/(n-1))

Unfortunately the number of terms varies with r, so we can't differentiate this with respect to r.

There are two probabilities to consider: (1) that the slip with the highest number will come up after, rather than before, r slips have gone by, and (2) given that the highest number comes after r slips have gone by, the prob that some other number higher than any of the first r does not come by before the highest of the n.

The first probability is easy: it is (n-r)/n that the largest slip comes after position r.

The second, conditional, probability is compound in the sense that there are n-r sub-cases, as there are n-r equally likely positions that the highest slip could have assuming it's after position r. In the case the highest slip is in position r+1, then the conditional prob is 1, or better, r/r. In the general case if the highest slip is in pos. r+i, the prob that another number higher than the first r does not occur before the total set's highest is r/(r+i-1), as this is just the probability that the highest of the first r+i-1 slips falls in the first set of r. Each of these conditional probs has to be multiplied by the 1/(n-r) prob that the highest is indeed in the given position. Then, when added together that total is multiplied by the (n-r)/n of the first probability.

Continued on next post.

Posted by Charlie on 2003-03-19 16:10:38