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: regarding posted solution by Ravi Raja)
But the goal of the problem is to maximize the return, not simply choose the largest slip correct? As I mentioned in my comment, this exception should only be used when this is so, not when the player will only be paid for finfding the largest slip.
Your strategy is quite correct from the outset, but as events pass, the probibilities change. A smart player will be able to use this to better their expected outcome (I hate that word when used in math - "expected", but even I can't escape it). As the user gets closer and closer to the end of the stack without finding a winner, the chances increase for him that he won't. I can't explain it any better than I previously did, but I can give a similar probibility example.
Should we play a game where I flip a coin 5 times and win if I get all heads, you would easily calculate that the "fair" entry price for the game is 2^5 times the prize value. Now say that the player is allowed to enter in at any time, accepting the however many previous tossed he wishes. Well, the player could simply wait until a string of 4 heads comes up, then join the game and expect to win half the time. This is a case of the probibilities changing as the events transpire.
My point is that, when coming to the second last slip, there is only a 1/n chance that the next slip is the greatest slip, but a(n almost) 1/2 chance that the next slip is a greater than the current one. And depending on the proximity of the current slip to the largest seen so far, it may very well be in the players interest to chooses it, even though it is not the largest. It all comes down to judgement of the specific situation, which of course cannot be included in a general solution, other than to state that such a condition MAY exist.
re(2): regarding posted solution
