Print

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

[-Stef-]

Suppose you're in a group of 200 people in a room. Everyone is handed out a random unique dominion card (yes they just bought DA).
In the next room, someone put another copy of the same 200 dominion cards in 200 envelopes, one in each.
Now one by one, a person is selected to go to the next room. In that room, he's allowed to look in 100 enveloppes. His task is to find the enveloppe containing his own card.
After looking at cards in enveloppes, this person will always put the cards back, leave the room in exactly the same state as it was before he came in, and leave the scene through the back door. No communication back to the group is allowed whatsoever.

You win if everyone in the group finds his own card. Your goal is to make a plan that maximizes this chance.

You are allowed to make a plan for all of the 200 people before the first one starts, and everyone else will do whatever you suggest. In this plan, you can assume some order on the enveloppes, so your instructions could include something like "open up the first enveloppe", "open up enveloppe 32 - 132" or "open up the first enveloppe, and if it's a card that costs $4 or more continue with enveloppe 67".

The solution has a theoretical upper limit of 50% because the first person has a 50% chance of failing no matter what you come up with. If everyone has a chance of 50%, your total score would only be 0.0000000000000000000000000000000000000000000000000000000000062%, rather disappointing. How high can you go?

[Qvist]

Yeah, a rip-off of my thread. Just to be sure: "leave the room in exactly the same state as it was before he came in" means that no clues are allowed like putting a card in the envelope in a specific state.?

[sitnaltax]

Hints below.

Hint 1: Number the cards.
Hint 2: The chance of success can be brought surprisingly high.
Hint 3: Solve for a small number of cards, like 2 and then say 6. If you can solve it for 10, you can figure out the pattern.
Hint 4: Remember, you're not trying to maximize the number of correct guesses. You're trying to maximize the chance that everyone guesses correctly. You need to find a way to put all your eggs into fewer baskets.

[nomnomnom]

Hint:
A person should assume that all previous persons guessed correctly because if one of them did not it is a failed attempt no matter what is done next.

Solution:
Let's say the first player took all the odd numbers. Then the second player should only choose even numbers because all of those are still possibly where his card is whereas one of the odd numbers is definitely a blank. It is the card of the first person after all.
For the third player it doesn't matter which card he chooses because 99 out of 100 odd numbers and 99 out of 100 even numbers could still be the right guess for him. The fourth player should act similarly to the second player and choose the cards that were not chosen by the third player. And so on.

Success rate=100/200 * 100/199 * 99/198 * 99/197 * 98/196 * 98/195 * ... * 2/4 * 2/3 * 1/2 * 1/1
                  = 1.1 * 10^-59

That is almost 20 times the success rate if all players choose randomly.

PS Of course it does not matter in which order the players are in or which subsets exactly are chosen. As long as there are 100 pairs of players so that the two players of each pair collectively look at all 200 cards it should work.

[jeb56]

I believe the chance of success is
<span style="color: #000000; background: #000000;" onmouseover="this.style.color='#FFFFFF';" onmouseout="this.style.color='#000000';"> removed</span>.

I apparently failed to copy the roll-over un-hiding accurately,  so I have removed my estimate. 

How should I format it, so that things are properly hidden?

[Grujah]

[ spoiler][ /spoiler]

without the space.

[GendoIkari]

Wait, if someone finds his own card, does he still put it back?

[shMerker]

I apparently failed to copy the roll-over un-hiding accurately,  so I have removed my estimate. 

How should I format it, so that things are properly hidden?

Most forums strip out HTML so just use board code.

Code: [Select]

[spoiler]like this[/spoiler]
like this

Also there's a button that looks like this: that will make the spoiler tags for you.

[ spoiler][ /spoiler]

without the space.

The code tag is your friend.

It would be pretty slick if this board had a tag that could generate dominion costs like the ones on cards and in the rulebooks. Or at least coin and potion emotes.

[jeb56]

I believe the chance of success is just over 30%.

[shMerker]

Wait, if someone finds his own card, does he still put it back?

Does it matter? He leaves behind the envelope and doesn't tell anyone if he found it.

[GendoIkari]

Wait, if someone finds his own card, does he still put it back?

Does it matter? He leaves behind the envelope and doesn't tell anyone if he found it.

Well for one I was making sure he does leave the envelope behind... also, if someone opens an envelope and it is empty, this could theoretically be used as an instruction to look in a certain different envelope next...

[GendoIkari]

It would be pretty slick if this board had a tag that could generate dominion costs like the ones on cards and in the rulebooks. Or at least coin and potion emotes.

Yeah, that would be awesome. The Draw3Cards StackExchange site for Magic has that for Mana symbols and other things; it's awesome. We could always post these images inline:

[Davio]

It would be pretty slick if this board had a tag that could generate dominion costs like the ones on cards and in the rulebooks. Or at least coin and potion emotes.

Yeah, that would be awesome. The Draw3Cards StackExchange site for Magic has that for Mana symbols and other things; it's awesome. We could always post these images inline:

It makes a lot of the fan card descriptions a lot nicer to look at.

When I used to run a Poker forum, I included all the card and suit symbols. 

[Grujah]

It would be pretty slick if this board had a tag that could generate dominion costs like the ones on cards and in the rulebooks. Or at least coin and potion emotes.

Yeah, that would be awesome. The Draw3Cards StackExchange site for Magic has that for Mana symbols and other things; it's awesome. We could always post these images inline:

It makes a lot of the fan card descriptions a lot nicer to look at.

When I used to run a Poker forum, I included all the card and suit symbols. 

You've got those in unicode already, no?

[Davio]

Just the suits, but I had small images for each card.

[GendoIkari]

So..... solution?

[SwitchedFromStarcraft]

It would be pretty slick if this board had a tag that could generate dominion costs like the ones on cards and in the rulebooks. Or at least coin and potion emotes.

Yeah, that would be awesome. The Draw3Cards StackExchange site for Magic has that for Mana symbols and other things; it's awesome. We could always post these images inline:

It makes a lot of the fan card descriptions a lot nicer to look at.

When I used to run a Poker forum, I included all the card and suit symbols. 

What poker forum did you use to run?

[Captain_Frisk]

Wait, if someone finds his own card, does he still put it back?

Does it matter? He leaves behind the envelope and doesn't tell anyone if he found it.

Well for one I was making sure he does leave the envelope behind... also, if someone opens an envelope and it is empty, this could theoretically be used as an instruction to look in a certain different envelope next...

It makes a big difference.  Taking the envelope, or taking the card in the envelope is extra information that can be passed back.

Take a 4 player game for example: (Players can open 2 envelopes)


Before entering, agree on a number mapping system, so each card has a #

Player 1 opens the first envelope.  If it isn't his envelope, then he opens the envelope # corresponding to the card # he found in the first envelope.

If he loses - game over.

Assuming that he wins, Player 2 enters the room with 2 possibilities

1 - envelope 1 is missing
In this case player 2 does the same plan with envelope 2.  (only a 33% chance of being wrong)

2 - Another envelope is missing
If its envelope 2 - then player 2 knows that his card is in envelope 1
If its 3 or 4, then player 1 knows that E1 contains that #, and his card resides in one of the other 2, so he gets his card

Players 3 and 4 win by default.

So - with the ability to pass this information back, The team wins almost 46% of the time.  I started working out what that limit drops off to as N approaches 200, but got bored, and saw that it might be illegal.

If you don't have this ability - then the solution is different, and I'm curious to see what it is.

[ehunt]

With no information sharing I can get probability "number of permutations in Sn with no cycles of length greater than n/2" over n factorial, don't know a closed formula for that number though.

[ehunt]

(the method is a minor modification of frisk's, will type it when not phone posting.)

[tyr10n]

This was my favorite homework problem in the randomized algorithms class I took. The hint on the homework had us first solve a seemingly unrelated math problem:

What is the probability that a random permutation of 2n elements has be no cycle of length greater than n ?  The answer to this is 1 - 1/(n+1) - 1/(n+2) ... - 1/(2n) which is approximately 1 - log(2) or 31%

If the players use the right strategy this is the same as the probability of success.

[Watno]

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

[Captain_Frisk]

If you want to be a jerk, it should be noticeable whether an envelope has or does not have a card in it. 

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

[Captain_Frisk]

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.

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