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

I remember that there is a best strategy for a more amorphous version of this question, such as if someone is seeking the best possible marriage partner. That strategy is to consider, but reject, the first prospect that comes along. Then continue seeking prospects and choose the first one that is better than that first one that had been rejected.

In the specific instance being presented now, I would think that this would have to be somewhat modified under the, admittedly unlikely, prospect that the first two numbers drawn are 1 and 2. In this instance, as the integers are assured to be positive and all different, we can be sure that something higher will be found. Other possibilities, for example, if it is known that n is 100, and the first several drawn are all under 100, we know that there must be at least one that is at least 100, and so we should continue at least until we get a number higher than n.

So possibly the best strategy is to bypass the first one and then take the next one that is higher than that first bypassed one so long as it is at least 'n'.

Posted by Charlie on 2003-03-18 03:59:33