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 re(3): regarding posted solution by Ravi Raja)

Ravi, I think you misunderstand what Cory is saying.

If there are 100 slips of paper, we know that there is at least one slip that has either 100 or higher on it. The solution strategy is to let 37 pass by and take the next slip that shows up with a number higher than any seen before. If the highest seen in the first 37 was 50, your strategy calls for accepting, say, an 80 that comes up subsequent to slip 37. But that makes no sense in this instance as we KNOW there is at least one with at least 100 on it, and by accepting an 80 we are doomed to failure even when that 100 was NOT in the first 37. Cory is saying that it makes sense to impose a hard-and-fast lower limit of 100 on anything we accept for a 100-slip game.

Posted by Charlie on 2003-03-27 03:36:31