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(2): the solution by Ravi Raja)
OK Ravi, I'll have another go at stating my objections. Apologies for being unclear, I know something's wrong here, but I find it difficult to define. Here's my reasoning, I'd be happy if you (or anyone else) could point out if I've made a mistake:
Let's start by assuming there is a maximum possible number, say 1,000,000. We could have real numbers < 1,000,000 to avoid the maximum slip being chosen, I don't think it matters.
Say there are 20 slips and I choose to discard the first 7. If the highest among them is, say 400,000, no problem, go on with the strategy. But if the 6th slip says 999,000, surely the best strategy would be to keep that one? Unless there is a distribution of numbers favouring the higher ones, it seems this would be the best thing to do. In other words, ***the probability of there being a higher number in the remaining slips is dependent on the highest number you have found so far!*** Perhaps this is easiest to see with 2 slips. If the first is 5, I'd choose the other one. If the first is 999,000, I wouldn't.
You say, \"Aha! But there is no highest number!\" I now come back to my point that you can't have an even distribution over all positive integers. If there isn't a maximum, then the probabilities must start tapering off, e.g., for any
x > 1,000,000 the probability of x is p(x) = 0.5 p(x-1). One could still calculate the probability of any slip being greater than the highest one so far, if one knows the distribution.
In the case unlimited integers, I think your strategy only works if you have no clue whatsoever what the highest number is likely to be, not even the order of magnitude, and that you choose one slip or more among the ones to be discarded that is >> n. I hope I'm making at least some sense?
re(3): the solution
