Probability puzzle: Coins in envelopes

by HonoreDB 1 min read2nd Dec 201118 comments

8


This went over well in the xkcd logic puzzle forum (my hand was not removed), so I thought I'd try it here.  It came to me in a dream, so by solving it you may be helping to summon an elder god or something.

 

You're spying on Alice and Bob, both of whom are perfect mathematicians. Alice shows Bob a set of m envelopes. "Each of these envelopes contains either a dollar coin or nothing," she says. "I chose how many envelopes to fill randomly. What is the expected monetary value of the contents of a random envelope?" 

Bob replies, "That depends on what random function you used to choose how many envelopes to fill. If you, say, flipped m coins and put each one that came up heads in an envelope, the expected value is $.50."

Alice explains what her random function was, and Bob calculates the expected value. For kicks, he pays her that amount, and she lets him pick a random envelope. It has a coin in it! Bob pockets the coin. Alice then takes the now-empty envelope back, and shuffles it into the others. "Congratulations," she says. "So, what's the expected value of playing the game again, now that there's one fewer coin?"

"Same as before," Bob replies.

Problem 1: Give a value for m and a random function for which this makes sense (there are many).
Problem 2: Suppose Alice chose the number of envelopes to fill by selecting an integer from 0 to m uniformly at random, and distributing that many coins among the envelopes. What is m?