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

  Submitted by Ravi Raja    
Rating: 4.1818 (11 votes)
Solution: (Hide)
Let us fix a value ‘k’, where k lies between 0 (inclusive) and N and consider the strategy that rejects the first k slips and then accepts the slip thereafter that has a number greater than the maximum among the ones observed on each of the first k slips that have been rejected. Let W be the event that the slip with the highest number is chosen and the person wins when this strategy is employed. Also, for i = 1,2,….,N, let B(i) be the event that the slip with the highest number is in position ‘i’. Exactly one of the events B(i), i = 1,2,….,N, must occur and so, upon conditioning on which event does occur, we obtain:

P(W) = [Summation from i = 1,2,….,N] P{W | B(i)}P{B(i)}

or, P(W) = (1/N)[Summation from i = 1,2,….,N] P{W | B(i)}

The final equality follows because the slip with the highest number is equally likely to be in any of the N positions and so, P{B(i)} = 1/N, for all i. Now since we are employing the strategy of rejecting the first k slips, it follows that there is no chance of obtaining the slip with the highest number if it is among the first k.

Consequently, P{W | B(i)} = 0, if i is less than or equal to k.

On the other hand, if the slip with the highest number is in position i, where i is greater than k, then this slip will be selected if the highest number on the first (i – 1) slips is among the first k.

However, conditional on the slip with the highest number being in position i, it is easy to see that all possible orderings of the other slips remain equally likely, which implies that each of the first (i – 1) slips is equally likely to be the one with the highest number on them.

Hence we obtain that: P{W | B(i)} = {k/(i – 1)}, if i is greater than k.

From the previous results we have:

P(W) = (k/N)[{Summation from i = (k+1),(k+2),….,N}1/(i – 1)]

or, P(W) = (k/N)[{Summation from j = k,(k+1),(k+2),….,(N – 1)} (1/j)]

Now, if we select (k/N) to be equal to (1/e), where e = 2.718281828459045 (approximately), then we have P(W) = 1/e

That is, the strategy that lets approximately the fraction (1/e) of all the slips go by and then accept the first one thereafter that is the greater than the maximum number yet observed (among the first k slips that have been rejected) has probability equal to (1/e) which is approximately equal to 0.37 of obtaining the slip with the highest number.

So, the best strategy is to reject the first k (= N/e) slips and then accept the slip thereafter which will bear the number greater than the maximum number observed in the first k slips rejected.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
Puzzle ThoughtsK Sengupta2023-06-14 22:29:01
Pigeonhole principleAditya2007-05-19 15:22:43
re(7): regarding posted solutionCharlie2003-03-29 09:59:35
re(6): regarding posted solutionRavi Raja2003-03-28 19:41:57
re(6): regarding posted solutionRavi Raja2003-03-28 19:38:00
re(5): regarding posted solutionRavi Raja2003-03-28 19:10:26
What i would probably do.charles2003-03-27 14:32:30
re(5): regarding posted solutionCory Taylor2003-03-27 04:05:57
re(4): regarding posted solutionCharlie2003-03-27 03:36:31
re(4): the solutionRavi Raja2003-03-26 20:35:23
re(3): regarding posted solutionRavi Raja2003-03-26 20:23:08
re(3): regarding posted solutionRavi Raja2003-03-26 20:09:51
re(3): the solutionpleasance2003-03-26 01:35:46
re(2): regarding posted solutionCory Taylor2003-03-25 04:51:30
re(2): regarding posted solutionCory Taylor2003-03-25 04:38:25
re(2): the solutionRavi Raja2003-03-25 03:56:10
re: regarding posted solutionRavi Raja2003-03-25 03:48:27
re: regarding posted solutionRavi Raja2003-03-25 03:37:45
re: the solutionpleasance2003-03-24 08:10:49
regarding posted solutionCory Taylor2003-03-24 04:10:36
re(3): What's the distribution?Ravi Raja2003-03-21 03:49:59
re(3): What's the distribution?Ravi Raja2003-03-21 03:41:06
re(2): What's the distribution?pleasance2003-03-21 02:58:47
re: solutionCharlie2003-03-19 16:22:39
SolutionsolutionCharlie2003-03-19 16:10:38
re: if we assume randomRavi Raja2003-03-19 04:12:32
re: Any integer?Ravi Raja2003-03-19 04:02:49
re(3): What's the distribution?Ravi Raja2003-03-19 03:52:50
re(2): Monte Carlo Simulation (continued)Ravi Raja2003-03-19 03:46:31
re(2): What's the distribution?Charlie2003-03-19 03:41:14
re: Monte Carlo SimulationRavi Raja2003-03-19 03:36:40
re: What's the distribution?Ravi Raja2003-03-19 03:32:33
re: Another differenceRavi Raja2003-03-19 03:27:06
re(3): solution to similar situationRavi Raja2003-03-19 03:24:37
re: solution to similar situationRavi Raja2003-03-19 03:22:49
re(2): solution to similar situationCharlie2003-03-19 03:09:22
re: partial solutionRavi Raja2003-03-19 03:03:17
re: solution to similar situationRavi Raja2003-03-19 03:00:04
Solutionif we assume randomAlan2003-03-18 13:42:24
Any integer?Gamer2003-03-18 10:51:20
re(2): Monte Carlo Simulation (the program)Charlie2003-03-18 09:09:30
re: Monte Carlo Simulation (continued)Charlie2003-03-18 08:55:05
Monte Carlo SimulationCharlie2003-03-18 08:47:08
Some ThoughtsWhat's the distribution?pleasance2003-03-18 07:34:42
Another differenceCharlie2003-03-18 05:31:04
partial solutionCory Taylor2003-03-18 04:56:05
Some Thoughtssolution to similar situationCharlie2003-03-18 03:59:33
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 (8)
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