Jump to content
BrainDen.com - Brain Teasers
  • 0

A Game of Probabilities


Yoruichi-san
 Share

Question

You and I are playing a little game (that is in no way whatsoever related to any game played on this site *cough*). There are 12 objects, 4 of which have the property M. The goal is to choose an object with the property M.

However, you and I are playing by different rules. For each round, first there is the N phase, in which you secretly choose an object (write down its number or something), then there is the D phase, during which I pick an object and it is revealed whether or not the object has property M.

If the object I pick has the property M, I win, if not we keep going. During any N phase, after you choose an object, you can call 'STOP' and the game will end. Then you reveal your choices, and if at least one has the property M, you win. If none have the property M, I win.

What is your play?

Bonus: Generalize to a case of n objects, k of which have the property M.

Link to comment
Share on other sites

18 answers to this question

Recommended Posts

  • 0

let me see if i have the riddle correct with an example.

let's say i have 12 playing cards, 4 of which are spades. all cards are over turned, so no one knows which is which.

player 1 chooses 1 card, and keeps it down turned.

then player 2 chooses 1 card. player 2's card is revealed. if it's a spade, he wins, else keep playing.

player 1 picks another card (assuming player 2 didn't win.) player 1 can call stop. if either of the two cards are spade, player 1 wins.

else, player 2 wins.

sound good?

Link to comment
Share on other sites

  • 0

let me see if i have the riddle correct with an example.

let's say i have 12 playing cards, 4 of which are spades. all cards are over turned, so no one knows which is which.

player 1 chooses 1 card, and keeps it down turned.

then player 2 chooses 1 card. player 2's card is revealed. if it's a spade, he wins, else keep playing.

player 1 picks another card (assuming player 2 didn't win.) player 1 can call stop. if either of the two cards are spade, player 1 wins.

else, player 2 wins.

sound good?

Only possible difference is that player 2 [i think] doesn't know which card player 1 has chosen.

E.g. P2 might choose one of them herself, and thus can 'steal' some of p1's chances.

Link to comment
Share on other sites

  • 0

The game seems simply to determine when to say Stop.

Seems that 2 draws puts your winning chances above 50%. 

So I'm stopping after my 2nd draw.

Generalizing to j and k,

I would compute player 2's chances with player 1 being silent.

On the turn the it exceeds 50%, I would say stop.

Link to comment
Share on other sites

  • 0

You and I are playing a little game (that is in no way whatsoever related to any game played on this site *cough*). There are 12 objects, 4 of which have the property M. The goal is to choose an object with the property M.

However, you and I are playing by different rules. For each round, first there is the N phase, in which you secretly choose an object (write down its number or something), then there is the D phase, during which I pick an object and it is revealed whether or not the object has property M.

If the object I pick has the property M, I win, if not we keep going. During any N phase, after you choose an object, you can call 'STOP' and the game will end. Then you reveal your choices, and if at least one has the property M, you win. If none have the property M, I win.

What is your play?

Bonus: Generalize to a case of n objects, k of which have the property M.

Here's an approximative strategy,

At every point of the game, we can summarize the current state of the game with the number of remaining objects (R), the number of unopened chosen objects (c), and the k number of objects with property M.

We define a function for the probability of winning at state (R, c, k) as

post-14842-0-81798300-1340501484_thumb.p

The strategy now is as follows,

1) At the beginning of N phase (before we choose an object), we calculate the chance we would win if we were to call stop at that N phase. Call this S0, which is defined as

S0 = W( R, c + 1, k )

2) We then calculate the chance we would win if we go through one more round and then stop at the next N phase. Call this S1, which is defined as

S1 = ( 1 - k/R ) * [ [ ( c + 1 )/R ] * W( R - 1, c + 1, k ) + [ 1 - (c+1)/R ]* W( R - 1, c + 2, k ) ]

3) If S1 > S0, then continue the game. Otherwise, stop the game.

Back to the example where R = 12 and k = 4. At the first turn where c = 0, which means the game state is (12, 0, 4), we get

S0 = .3333

S1 = .398

Which means that we should continue the game. If the opponent does not win the game during next turn, then there are two possible next states, which are

(11, 1, 4) - The opponent did not open your chosen door - The strategy above says that we should stop at this N phase.

(11, 0, 4) - The opponent did open your chosen door (essentially a new game with R = 11) - The strategy above says we should continue the game.

Continue until the strategy calls for a stop.

Edited by bushindo
Link to comment
Share on other sites

  • 0

Excellent, thank you Bushindo :)

I thought there might be multiple ways of looking at the problem, but felt that the differential method was the best, although I have no idea how to prove it. It makes a 'profit=marginal cost' kind of sense.

And yes, one of the key aspects, I think, is that the probabilities change each round, after you get information (that is, whether I choose your object). I.e., for the mth round, you calculate the probability you win if you stop at the (m+1)th round taking into account the probability that I choose your object, but during the (m+1)th round, you know whether I chose your card or not.

The other possible way I can see for looking at the problem is to assume an infinitely large n, such that at the stopping point, P(winning if you go one more round)=P(winning if you 'STOP' now), and working backwards.

Link to comment
Share on other sites

  • 0

The best strategy for N is to yell STOP only and as soon as he or she recieves something with property M because the payoff for losing is symmetrical to both ways of losing (D draws M or N calls STOP holding only not-M). It always pays to go another round after drawing not-M. It might be a more interesting game if there were different payoffs, though. What if it cost more to lose from D drawing M than from yelling STOP while only holding not-M? If that were the case, there would be a point at which it becomes more costly to continue playing. The payoff matrix would be based on the notion that k/(n-x) is the probability of winning the next round {where x is the number of the round, k is the number of objects with M, and n is the total number of objects}. I decided not to keep going and calculate the whole payoff because I need a function which is 0 when x is odd and 1 when x is even, and I'm a little too lazy for that.

  • Upvote 1
  • Downvote 1
Link to comment
Share on other sites

  • 0

Consider the decision tree.

You can calculate the probability that you will win, when you predetermine on which round you will say STOP (if you survive until that round).

The first round probability is 4/12=0.33

Second is 0.397979...

This increases, until some round to say STOP where the probability of winning will begin to drop.

Obviously the "general solution" is to say STOP on the round that produces the overall highest probability of winning relative to the beginning of the decision tree.

My solution would be a computation, rather than a calculation. There are multiple ways of presenting it, but none of them would look nice.

Link to comment
Share on other sites

  • 0

Some people are arguing that it's best for N to go 2 rounds because then he or she has over a 50% chance of winning. The problem is allowing round 2 gives D a 31.8% of winning. That means letting the game reach round 2 only gives N a 1.2% net advantage for allowing it vs. a 33% advantage for calling STOP after the first draw. I'd say N's best strategy is to call STOP after the first draw.

Link to comment
Share on other sites

  • 0

You can't say STOP after they've already won.

Of course not, but it doesn't matter. If N knows what he or she draws, then the only reason to continue the game is if he or she draws not-M. Calling STOP at this point would ensure a loss. Continuing gives a chance of victory and a chance of loss. So clearly it's better to allow another round. This logic continues until k=n, at which point whoever draws next wins.
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...