All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Logic
The Best Strategy (Posted on 2003-03-18) Difficulty: 5 of 5
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).

See The Solution Submitted by Ravi Raja    
Rating: 4.1818 (11 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
re(2): What's the distribution? | Comment 25 of 47 |
(In reply to re: What's the distribution? by Ravi Raja)

Ravi, I'm curious to see your proof.

I recall a similar problem from a mathematics course. There were two slips, with one having twice the sum the other had. You had to decide, after looking at one, whether or not to change slips. It was proposed that the first slip had x, the second one had equal probability for 2x and 0.5x, for an expectancy of 1.25x. Therefore, paradoxically, you should always change slips! So how can that be?

The solution to that one relied on the fact that one *cannot* have an even distribution over an infinite set. The suggested strategy was to assess the largest likely sum to be given out, and act accordingly.

It seems to me something similar must be part of the solution to your problem. If you claim an even distribution over infinite integers, then I would say always choose the last slip. No matter what the highest number so far, the probability of the next being higher is 1!!! You have a finite set of numbers lower, versus an infinite set of numbers higher!


  Posted by pleasance on 2003-03-21 02:58:47

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (12)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information