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).

(In reply to Monte Carlo Simulation by Charlie)

But for this problem, merely bypassing the first few and looking for one that beats the previous max has problems at the end. In the all-or-nothing case it didn't matter--if you didn't get something better than the previous max, you lost anyway. Here it matters.

As you're getting near the end you would want to lower your expectations before getting stuck with whatever is last. To guess at a strategy, I chose to simulate bypassing a certain number at the beginning to determine a max to try to exceed, but if the number of slips left gets to being less than that same number (the number we bypassed) then lower the threshold for accepting a number evenly from the max found before to 1/2 of that max. So if we had bypassed 10 with a maximum of 100 rupees, then when we got to only 10 slips left without finding anything higher, we'd lower our acceptable value to 95, then 90, then 85, etc.

Then the following are the optimal number to bypass at the front and to used lowered expectations at the end: for n=25, bypass 11 and expect 91.2% of highest slip (87.7% of high end of distribution); n=50 bypass 19 and expect 94.9% (93.0%); n=100 bypass 32 and expect 97.0% (96.0%); n=200 bypass 55 and expect 98.3% (97.8%). Note the optimal bypass doesn't increase linearly with n, and these are all higher expected values than the best we could do merely bypassing at the beginning (previous comment).

Of course this is nowhere near a proof of optimal strategy, only heuristic trials.

Posted by Charlie on 2003-03-18 08:55:05