Monty Hall's Revenge

[Laramie]

Consider a variant of the problem in which there are two bags in front of you. You get to open one of them and count the money. You then have to choose between that bag and the other one. You get to keep the money if and only if you choose the bag with the highest amount. What should you do?

It seems that you cannot do better than a 0.5 probability of success here, but that is not the case. One might, for example, choose to accept the first bag with probability 1-e^(-x), where x is the amount observed. This increases your chances above 50%, no matter what the underlying distribution is and even if you have no prior belief about the underlying distribution.

[HyToFry]

bump to fix the times on the main page.

[Icarus]

I think I'm opening myself up for ridicule or sarcasim - but is there really anything you can do to increase your chances ? Maybe there isn't always an answer to a puzzle ?

Consider this before you answer - what if no matter how elaborate your scheme is, the very first bag you picked is the bag with the most money in it ?

No one would think to stop at the first bag. Upon opening the first bag, you have no idea what the other bags contain. So naturally you would choose one more bag. But by then, no matter how many times you pick another bag, you've already lost.

I'm sure mathematically someone is going to prove that there is a way to turn the odds ever so slightly in your favor. But in reality, greed always gets the best of you, and everyone will go to that next bag.

[mith]

I have decided I need to be more careful about these things, I'll end up spending a day writing the solution because I'll have to state and argue all the assumptions.

Assumption you can make about this puzzle:

The distribution of money in the bags, and the placement of the bags themselves, is random.

The first may be hard to accept; at least, we know there is a minimal value, 0, and a maximal value of some reasonable fraction of the car's value. However, while you could probably use this information if you picked bags with values at the extremes, the odds of you being in this situation isn't so great. Also, you don't actually know what the upper limit is. If you *did* know, that would tell you something, but you don't. As for the bags themselves, you are picking them. Yes, you could pick the one with the most money in it first. That's 1% you've eliminated, hardly the end of the world.

*~random rant~*

[Yossarian]

I am new to this forum, and I don't know if I am allowed to post only my solutions. So I am taking a risk and posting a solution from http://rec-puzzles.org

The maths for the problem amounts to this:

We have to pick the smallest x so that,
x/100 > x/100 * (1/(x+1) + ... + 1/(100-1)). From the math (and which math is that?), it turns out that the probability of a win is highest when the contestant has looked into 37 bags. So, (s)he ought to look into 37 bags and then, choose the highest that has come up until that. The probability of a win in this case itself is almost 37%.

[Zarriar]

In response to Icarus:

You do not have to sample the bags in any particular order. The gameshow host would have to be able to predict which bag you were going to take first for your point to be valid.

[Icarus]

I tried to keep my earlier reply short, and I think it cost me.

So far, everyone seems to have the same idea, pick "x" amount of bags for your sample, set your goal based on the highest amount found in your sample, and then continue hunting until you find a bag with more money than your highest sample bag. Obviously, "x" is the key factor. Exactly how many bags do you use for your sample ?

37 seems to be the favorite, so let's use that.

What I was trying to point out earlier, is, while you are obtaining your sample, you have to consider 1 of 2 possibilities.

1 - You've already found and passed up the bag with the most money in it while obtaining 37 bags

OR

2 - Let's say you establish your mark using 37 bags, and the highest amount, from bag 20, was $200. Now you begin searching the reamining 63 bags. 13 bags into your search you find $250. But you still have 50 unopened bags left. Will you really stop opening bags once you've beaten your mark ? I still say "NO".

Sure, If I find the bag with $250 in it and only have 1 bag left, I'll stop. But with 50 bags left, I doubt anyone would stop. Again, mathematically you can prove me wrong, but we're not Volcans.

I think the best way to optimize your chances is to divide the bags into 2 equal piles - 50 bags per pile.

Explore all 50 bags in pile 1. Set your mark from there. Now use pile 2 until you beat the highest amount from pile 1.

And yes, even if you have 49 bags left in pile 2, you must stop.

[Zarriar]

Icarus, what I believe you are saying is in line with what Laramie is saying. Basically the first 'x' amount of bags is used to get an idea of the distribution and then you find the first bag that is statistically, significantly greater than the standard deviation of the distribution. In this case I believe that optimal 'x' cannot be predicted prior to sampling the bags as it depends too heavily on the information gained in the process.

[Icarus]

Zarrier, Thank you. Yes, that is a good summary. No need for me to state any further.

[FlashBazbo]

I don't know if this is the solution Mr. Newman had in mind, but here goes...!

The key sentence is "You may KEEP the money in the bag you CHOOSE." Let's say I choose Bag #77 (in honor of Ray Bourque.) It's got a certain sum of bucks in it, and all's well. Now, I open another bag, which may have more, less, or as much cash as Bag #77. I take the cash OUT of this bag, and place it IN Bag #77! ...and I'm going to repeat this process until I've opened every dang bag, removed all the contents, and placed the whole swag into Bag #77!

That is, I am KEEPING the money in Bag #77 -- in the sense of keeping money in a safe. And at the end of the show, I'm CHOOSING to go home with Bag #77. In my spiffy '81 Wagon, no less.

Of course, my solution assumes that the bag is big enough to accommodate all the money or a majority of it (and that I'm strong enough to lug it around.)

Again, that's probably not what the puzzlemaker is looking for... but what the hey, there's my thought from left field for the day.

Comments?

[Chuck]

I think ChienFou had the intended problem solved in the first post of this thread. Everyone else is just torturing it for fun.

[Laramie]

As one of the torturers, I am deeply, deeply offended (just kidding of course). I'm sure you're right. I do think it's a fascinating puzzle when you drop some of the simplifying assumptions.

[Nenad]

I also think solution is 37 , or more precise:
"Open RANDOM 37 bags and then open (again randomly) unopened bags until you find larger sum then in any of previously opened bags."

Chance of finding max sum is around 36.7873% Opening random bags (as opposed to opening in order) just remove chance of host rigging results (ie. always putting largest sum in 1st bag)

Explanation:
We were looking for best N in 100bags 'Fattest stack'. Chance of winning bag being in 1st N bags is Pn=N/100. So we have Pn chance to loose, and less than (1-Pn) chance to win. If wining bag is in second stack , we have:
...1)Pn chance that 2nd best bag is in first stack, thus adding (1-Pn)*Pn chance to win
...2)Pn chance that 3rd is in first stack, and 1/2 chance that we will find best bag before 2nd best,
.....and (1-Pn)*(1-Pn) chance that 1st and 2nd are not in first stack,
.....so adding (1-Pn)*(1-Pn)*Pn*1/2 chance
...3)Pn chance that 4th is in first stack, and 1/3 chance that we will find best before 2nd/3rd best,
.....and (1-Pn)*(1-Pn)*(1-Pn) chance that 1st,2nd&3rd are not in first stack,
.....so adding (1-Pn)*(1-Pn)*(1-Pn)*Pn*1/3 chance
...4) etc...
In general, Chance= SUM (1-Pn)^i *Pn *1/i (for i=1 to N)

Best results are:
36 > 36.7794 %
37 > 36.7873 %
38 > 36.7682 %

[Curtis-Kun]

It seems logical, that the bag you pick will feel like the largest amount of money. Thus, if you picked a big with a dollar in it, then there is a chance that the other bags may have lower amounts than a dollar, so...

n = your bag
x = other bags

n > x

A simple equation, really. Mentally, you think you win, blah, blah, you got the highest, the stupid man is just being a liar, who cares about the car, blah.

[Shade_Shadowbane]

Okay...

Here's what I would do... as the show host said that if you pass a bag, you could not go BACK to it... I would line the bags in a circle, and keep going one at a time... FORWARD down the line... eventually continuing forward through the open bags...

Simplicity is sometimes the best solution...

Shadowbane

[MarceloG]

Since we all noticed that the text is a little ambiguous in some parts and some considerations are not very clear, can anyone determine the following issues?

1) ... "I'll let you open a bag" -> Is it obligatory to open the bag?
2) If I don't open the bag, may I go back?
3) All the bags are equal?
4) All the money in all the bags are the same? eg. all $100 or $50.

If ...

1) NO
2) YES
3) YES
4) YES

Then, I may consider to weight all the bags and choose the heaviest.

Sorry for all the ones who are making great work with numbers, but i think that always there must be an easier solution. I hope i am not trying to simplify in excess the problem.

[Icarus]

I find it funny that everyone keeps going back to the issue of which bag feels heavier, or line up the bags in a circle, etc.

Keep one thing in mind - on the original "Let's Make A Deal" show, somethimes people were offered a small box. They turned it down. The prize in the box was a trip. Did you actually think they were going to put a real DC-10 in a box. NO ! Inside the box was a picture of a plane. Hey guess what - what's to stop them from putting a card in each bag with the dollar amount printed on the card. Then guess what - all the bags would weigh the same.

And any time you have a choice of boxes, bags, or whatever - you usually don't get a chance to touch it anyway - the host always hands it to you. So once you decide you want bag number 2, the host takes bag number 1 away from you. What good is weighing the bag going to do you now.

[ChienFou]

This has got really boring. We can postulate anything we like, but, as the problem was actually set, I got the right answer about 15 minutes later. Sorry guys, but that's just a fact. There's a whole class of these problems and the answer is usually n/e or sometimes n-n/e where n is the sample size, and e is well, just e.

[blonde]

um.... this may be a really unlogical or logical answer... but wouldn't you just let the rest of the crowd go first? to increase ur chances? But then you might miss out on the car, as someone else may choose the bag first! ARGH! maybe you could just look at the bldy bags and see which one is the biggest *lol*

[DriftedIn]

I haven't read the whole of this thread, but everyone seems to take for granted the fact that the money inside the bags is in cash. What if they are just numbers written on a card?

If you ask the host what the maximum amount is, you have simply defeated the purpose of the game, because then you can go through the bags until you find the right amount. Its a good idea, but I somehow doubt the game show host would tell you. I have no solution to the problem myself, but just looking at it with my Yr 10 (UK) eyes, it seems you have a probability of 1/100 (nothing new to anyone huh) of winning the maximum amount.

If I remember correctly, this is conditional probability. So if the first bag wasn't the one you choose, the probability of getting the prize increases to 1/99. Now if you have the bad luck of choosing the maximum amount on the first draw, but pass it up because you believe there is more....

Where does that leave us?

[start pilot]

This expression is simpler and gives an easy way to find N/e as optimum for large N.
Open n bags and note the max amount. Continue until you find the bag #k with higher amount. This bag holds the absolute max amount if the max from bag #1 to #(k-1) is situated in bag #1 to #n AND if bag #k holds the absolute max. This means the probability of bag #k being the absolute max is n/(k-1)*(1/N). The probability that we find the absolute max when we discard n bags is then given by P(n)=n/N*sum(1/(k-1)) for k = n+1 to N.
You should find n-optimum = 37 bags.