Math Puzzle

/sci/ has been getting boring recently.  Let me attempt something new.  This is a math puzzle I heard about ages ago.

There are N boxes, each with a real number such that no two boxes have the same number.

The first box is opened so that you can see its contents.  You can a) choose this box or b) discard this box and open the next one [with which you repeat the procedure].  If you choose a), and the current box contains the largest number, then you win $1000.  If you choose b), then you will not be given the option of going back to the discarded box.  Of course, discarding all the boxes means that you lose by default.

What is the strategy to optimize your chances of winning, and what is this probability?

N=1, P=1
N=2, P=1/2
N=3, choosing the 1st box gives P=1/3, but if you discard the 1st box and choose the next largest box, you get P=3/6=1/2 > 1/3.
N>3, ...?

N=4,
Choose 1st box, P=1/4
Choose 2nd largest, P=11/24
Choose 3rd largest, P=8/24=1/3
Discard 1st 2 boxes, and choose next largest, P=10/24=5/12

pi

Is this like the monty hall game?

>>4
It's vaguely related, but not quite.

The original monty hall game has exactly 3 boxes, and one is to choose one.  The mod then discards a fake box (which doesn't happen in this puzzle).  One then has a choice of switching, or staying with their current choice.

N = 5

FIRST BOX:
Choose 1st box, P = 1/5

SECOND BOX:
If opened box is largest so far: P = 1/4
If not, P = (THIRD BOX); (you are forced to open another box)
Since opening the second box has a 0.50 chance of being higher than the first, total P of winning with second box =
0.50(1/4) + 0.50P(THIRD BOX)

THIRD BOX:
If opened box is largest so far: P = 1/3
If not, P = (SECOND BOX); (you are forced to open another box)
Since opening the second box has a 0.50 chance of being higher than the first, total P of winning with second box =
0.50(1/3) + 0.50P(THIRD BOX)

and so on...

I guess you could make some kind of recursive function and then plot the probabilities for some large N.

Stats majors, am I doin it right, or doin it wrong but at least getting the right results, or just doin it wrong?

...no os dna

FOURTH BOX:
If opened box is largest so far: P = 1/2
If not, P = (FIFTH BOX); (you are forced to open another box)
Since opening the second box has a 0.50 chance of being higher than the first, total P of winning with second box =
0.50(1/2) + 0.50P(FIFTH BOX)

FIFTH (N'th) BOX: base case
If openend box is largest so far: P = 1, a winrar is you
If not, P = 0, a loserar is you
0.50(1) + 0.50(0) = 0.50

Returning the values of the recursive calls and tabulating:

1st box:                         1/5 (or 1/n)
2nd box: 0.50(1/4) + 0.50(1/2) = 3/8
3rd box: 0.50(1/3) + 0.50(1/2) = 5/12
4th box: 0.50(1/2) + 0.50(1/2) = 1/2
5th box:                         1/2

Oh fuck it doesn't have a 50% chance of being higher each time.


Anyways, the method is correct here, isn't it, except the 0.50 should be 1/i, where i is the ith box open?

There is no interesting strategy given just this information.  The optimal strategy is just to pick the first box that has a non-zero amount of money.

Just consider N=2.  Say I give you the first box and say it has 10 dollars in it.  According to the parameters of the game the 2nd box could have any amount of money except exactly 10 dollars and we know nothing other than that.  This information does not provide a means to assign a probability distribution to the possible outcomes of opening the 2nd box, i.e. assigning a distribution to the range [0,infinity)\{10}.

>>9
Boxes do not contain money.  They contain real numbers.  You get $1000 or you get no money at all.

>>10 Sorry about that, but it ends up being the same problem.  You can't assign a probability distribution to what number the box contains from this information.

>>11
Jesus, did you read the thread or even the OP? There are better selections than simply taking the first box, that much is verifiable. In particular, for the case with N boxes, discarding the first box and taking the next largest box gives 1/N * (1 + 1/2 + 1/3 + ... + 1/(N-1)), which is pretty obviously larger than the 1/N given by simply taking the first box.

>>12 I was thinking the same as >>9 .

N = 4

If you choose the first box the chance is 1/4
If you choose the second box the chance is 1/4...
The chance is always 1/4, why would it change?
I'm slow or something, can someone explain this?

YOU'RE ALL WRONG

>>14 is right
Given zero knowledge of the distribution, we can say nothing of the probability.

It's not possible to determine what an optimal strategy is with the given information. We can guess all we like, and we'll only know who's right after we have more information.

I READ SPIVAK SO I CAN SOLVE YOUR MATHS PROBLEM

I AM EXPERT ANALYSIST; YOUR COMBINATORICS MEAN NOTHING

TAKE THE LIMIT ON THE DIFFERENTIAL FORM AND THE TAYLOR SERIES GIVE YOU THE ANSWER

INTEGREAT ALONG THE MEASURE FUNCTION TO GET THE METRIC SPACE, PROCEED TO TAKE d/dx WITH THE STOKES' THEOREM

YOU ARE WELCOME. EXPERT ANALYSIST GLADY DONATE HIS TIME

NO DEAL

>>13
You're slow. If you discard the first box and choose the next box WHICH IS LARGER THAN THE FIRST, the probability is not 1/4.
Suppose A,B,C,D are boxes with A being the one containing the largest number, B being the next largest, and so on.

Here's the set of possible arrangements of the boxes, with "W" next to the winners by the strategy of discarding the first box and picking the next largest, and "L" next to the losers:

ABCD  L
ABDC  L
ACBD  L
ACDB  L
ADBC  L
ADCB  L
BACD  W
BADC  W
BCAD  W
BCDA  W
BDAC  W
BDCA  W
CABD  W
CADB  W
CBAD  L
CBDA  L
CDAB  W
CDBA  L
DABC  W
DACB  W
DBAC  L
DBCA  L
DCAB  L
DCBA  L

Sum up the W's and you get 11 wins, out of 24 possibilities. 11/24 > 1/4.

PS: To all the people saying "omg you don't know anything about the distribution": The entire fucking point of the exercise is that you gain knowledge about the distribution with each box you open, so how do you find the optimum strategy between opening every box (which gives you a 1/N chance of winning but perfect knowledge of the distribution) and choosing the first box (which leaves you with no knowledge of the distribution). No strategy is going to give you a "sure thing", but I've already shown in >>12 that some strategies are better than blind choosing.

>>9, 13, 14, 15
If you decide ahead of time which box to choose, then yes you're stuck with a 1/4 chance no matter what.  However, by doing that, you're discarding information that you receive by opening the first few boxes.

In particular, if you really like the # 2, and the second box happens to have a smaller number than the first box, you definitely do not want box #2.  Picking box #2 has a 100% chance of loss, whereas looking for another box has a < 100% chance of loss.

Put another way, consider again the N=4 case.  There are 4! = 24 ways to arrange 4 non equal real numbers.  Indeed, opening the first box tells you nothing, which is why choosing it has a low probability of winning.  However, opening the 2nd box tells you a lot: whether the number it contains is bigger or smaller than the first number cuts down half of the possible arrangements (to 12).  This gives you non zero information about the probability distribution (the more boxes you open, the more information you have; opening all the boxes gives you 100% knowledge, but only 1/N chance of winning).

Indeed, as >>9 pointed out, for N=2, there is no strategy, which is also what I noted in >>1.  As I pointed out in >>2, strategy definitely helps for N=4.  If you don't believe me, write a program and see for yourself.

>>18
Didn't know you were posting at same time I was writing lol.  Thanks for the more concise version (complete with example).

I wants lots and lots of some delectable pot!

Marijuana MUST be legalized.

I have another interesting puzzle - Mathematical Impressions: Bicycle Tracks : http://www.simonsfoundation.org/multimedia/mathematical-impressions-bicycle-tracks

I am doing a report on memory processes and need participants for a really short online memory test. If you have a spare 5 minutes I would really appreciate your help :)

https://www.surveymonkey.com/s/YFS7T73