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's assume the distribution is uniform on some interval so that if the top possibility is 1,000,000 rupees, then any particular amount up to that is equally likely, or if the top possibility is 1,000 rupees, then any particular amount up to that is equally likely. But the subject doesn't know the max value, and so can only judge based on what he/she sees.

If a strategy is used analogous to the one Cory presented for the classic case (of the highest slip vs. nothing at all), then we seek the number of slips to bypass before choosing the next one that comes up higher than any before. I've simulated this with a computer program for n=25, 50, 100 and 200. The simulation did 15,000 trials of each such bypass strategy and took the average take for each bypass value. For n=25 bypassing 4 maximizes expected value at 85.5% of the highest slip (82.2% of the high end of the distribution). For n=50, bypass 5 to expect 88.8% (87.0%). For n=100 bypass 9 to expect 91.6% (90.7%). For n=200 bypass 12 to expect 93.8% (93.3%).

These are lower than the n/e values of the classic problem as we'd rather not be stuck with having to take the last slip, which might be low, and we are not so concerned with getting the absolute highest.

Posted by Charlie on 2003-03-18 08:47:08