Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Insomniac]

Before selecting envelopes hold the envelope up to the light to see inside the envelope.

100% success rate.

[eHalcyon]

Taking the envelope provides additional information, taking the card out doesn't, because you know what card the people before you had to find and what envelopes they looked at (since they're all following the plan). So if you look into an envelope and see someone's card in there, and know that person looked at it, it's the same as the card missing. Don't see that helps though

No, taking the card out still provides info.  I don't have an idea of how it might be helpful, but the info is there.  Say player 1 looks in envelope 1, finds his card and removes it.  Then player 2 comes in and also looks in envelop 1 and sees that the card has been removed.  Now he knows that player 1's card was in that envelope, rather than some envelope down the line.  If the card was left there, player 2 would not have this info.  Again, I don't know how it could be helpful, but taking out the card can indeed provide additional information.

Whether the envelope contains card#1 or empty - its the same.  Actually leaving the card in provides more information, as player 3 would know which card it was, vs just 2 empty envelopes.

Each new player needs to assume that everyone before them has already won... otherwise its a waste of his time.

But I've kept that assumption.  Finding an empty envelope gives you the info that a previous player found their card in that envelope, rather than a different envelope down the line.

Eh, maybe it's not giving more info, but just different info.

[ehunt]

Full solution (assuming cards aren't removed). My write-up assumes familiarity with the symmetric group. I also don't know a proof that this is the theoretically best-possible solution.

The participants agree on an explicit ordering on the envelopes and cards (equivalently, the envelopes and the participants) ahead of time. The strategy will be: participant number j waltzes straight to the envelope marked j and looks for her card. If she finds card k in envelope j, she opens envelope k next. She proceeds in this way until she finds her card (or loses the game for the team).

That's it. The reason the odds that this succeeds are approximately 30% is as follows: we have a permutation f of the set {1, 2, ..., 200} given by the rule "if envelope number j contains card number k, then f(j) = k." Notice that the participants succeed using the given strategy if and only if this permutation does not contain a cycle of length greater than 100, since the strategy just has the participant loop in order through the cycle containing her number. So we just need to count these permutations. If a permutation in S_{2k} has a cycle of length greater than k, then it only has one such cycle. So the number of permutations of length m, where m > k, is given by the following formula (explained below):

(2k choose m)(m!/m)(2k-m)!

(Explanation of formula: we choose m elements to be "in" the cycle. We can order them in m! different ways, but two orderings are the same cycle if they differ by the n trivial reorderings which "cycle" the elements (couldn't think of a better verb there, sorry), so we divide by n. The (2k - m) elements that are "out" of the cycle can be grouped in any permutation in S_{2k - m}.

This formula simplifies to the much nicer looking

(2k)!/m.

So the probability that a permutation contains an m-cycle (i.e. is bad for our participants) is just 1/m, since there are (2k)! total permutations.

Thus our participants have probability 1/(k+1) + 1/(k+2) + ... + 1/(2k) of failing. This is a right-hand Riemann sum approximating the integral from k to 2k of dx/x, so is close to log(2k) - log(k) = log(2), which is where the 30% comes from (there are other ways to connect this sum to log(2) as well).


 

[Schneau]

Full solution...

This is so cool. At first I was "what" and then I was "how does that work" and then I was "I get it, that's awesome!".

The thing that you didn't explicitly say that I was having trouble with was: What if you finish a cycle - how do you choose which envelope to pick next? After thinking about it, I realized that if you finish the cycle, you have found your card, since your card is j and the first envelope you chose was j, meaning to cycle you have to find your card! You did say this, but in fewer and less explicit words. Great job, I'm convinced!

[DStu]

Why do. I loop through a cycle containing my number and not through any other cycle?
Edit: got it. It's almost magic.
Edit2:to explain. By construction, the last card of the cycle is the one you are looking for.