wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Card Game
        
(Message started by: spanchap on Mar 22^nd, 2007, 10:12pm)

Title: Card Game
Post by spanchap on Mar 22^nd, 2007, 10:12pm

Hello.

Thanks to all the contributors for the many excellent puzzles. I am a puzzle freak and have enjoyed solving these puzzles tremendously.

Here is my first contribution - I do not know if this puzzle or a variation has been posted in the past

I suggest the following game to you: I have a deck of 52 cards where the cards are well shuffled and random.

You get to pick a card. If it is red and you choose to pick no more cards, I pay you a dollar. If it is black and you choose to pick no more cards, you pay me a dollar.

You can continue picking additional cards from the deck till you choose to stop. When you choose to stop, I pay you the number of dollars equal to # of red cards picked minus # of black cards picked. If you ended up picking more black cards, you pay me the number of dollars equal to # of black cards picked minus # of red cards picked. If # of black cards picked = # of red cards picked, we call it even and go to a bar and have a quite drink. What is the expected value of this game for you? What should your strategy be?

- Suresh

Title: Re: Card Game
Post by Grimbal on Mar 23^rd, 2007, 3:41am

Is it a standard 52 cards deck, i.e. with exactly half of them red and half of them black?

Title: Re: Card Game
Post by towr on Mar 23^rd, 2007, 3:44am

At worst you'd gain nothing and lose nothing, because you can always go to the end of the deck.

The problem sounds somewhat familiar..

Title: Re: Card Game
Post by spanchap on Mar 23^rd, 2007, 7:20am

It is a 52 card deck and yes, the value of the game is non zero as the worst you can do is to lose no money

Title: Re: Card Game
Post by Grimbal on Mar 23^rd, 2007, 10:47am

I did a ~~numerical simulation~~ calculation in ~~Ex...~~ a well-known spreadsheet program. I get a value of 2.6245.

For each possible number of reds and blacks I average the values for the situation with one red or one black card less, weighted with the probability of each possibility. I stop if the offered value (red-black) is larger than the expected earning.

Roughly you should stop if you have 25% +1 more reds than blacks.

Title: Re: Card Game
Post by SMQ on Mar 23^rd, 2007, 12:52pm

I agree with your expected value of the game, Grimbal, but not your characterization of the strategy -- near the beginning of the game you want to allow far more than 25% reds. For instance, if you start out drawing all reds, you don't want to stop until you have 6 reds and no blacks...

Empirically, one formula I found is that you want to stop iff your current score > (1/2) * (number of remaining cards)^0.618. I don't know if that 1/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cphi.gif (where http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cphi.gif is the golden ratio) in the exponent is a coincidence or not...

--SMQ

Title: Re: Card Game
Post by spanchap on Mar 23^rd, 2007, 1:00pm

The process used by Grimbal to calculate the expected value can also be used to find the optimum strategy. Essentially you can find the expected value of the game with r red cards left and b black cards left. You continue playing the game if the expected value of the game with the remaining cards is positive.

Title: Re: Card Game
Post by SMQ on Mar 23^rd, 2007, 1:43pm

Indeed, but I was phrasing the strategy in terms of the question: "if there are N cards remaining, what split of red and black cards gives a positive expected value?" And the empirical answer I found was: the expected value of a game of N cards is positive if and only if the number of black cards minus the number of red cards (i.e. the number of extra red cards you're already holding) is less than approximately (1/2)Nhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supphi.gif where http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cphi.gif^-1 -- a somewhat surprising formula given its apparent inclusion of the Golden Ratio -- a value which doesn't often appear in statistical formulas.

--SMQ

Title: Re: Card Game
Post by tiber13 on Mar 23^rd, 2007, 3:47pm

smq, how did you get the symbols on your post, i know you have to use ALT

Title: Re: Card Game
Post by tiber13 on Mar 23^rd, 2007, 3:48pm

as soon as you have more red than black pay out, and if that never happens just go to the end of the deck.

Title: Re: Card Game
Post by spanchap on Mar 23^rd, 2007, 4:00pm

tiber13,

Even if you are ahead by 1 ( 1 red more than black), you would want to continue the game if the expected value of playing a new game with the remaining cards is positive

Title: Re: Card Game
Post by spanchap on Mar 23^rd, 2007, 4:22pm

Grimbal,

Apart from running simulations, one could also derive the expected value as follows:

[hide]Expected value of game with R red cards and B blue cards = E(R,B) = Max(0, Probability of choosing R red cards from R+B cards times (E(R-1,B) + 1)) + Probability of choosing B black cards from R+B cards times (E(R,B-1) + 1)) )

Therfore E(R,B) = MAX (0, R/R+B * (E(R-1,B) + 1) + B/B+R * (E(R,B-1) -1))

Setting E(0,0) = 0, E(1,0) = 1 and E(0,1) = 0 and iterating for higher values of R and B results in E(26,26) = 2.6244755[/hide]

Title: Re: Card Game
Post by SWF on Mar 23^rd, 2007, 6:21pm

Perhaps towr is thinking of this similar question:

"A deck of 26 red and 26 black cards is shuffled into random order and placed face down. Then the cards are turned up one by one and observed by a guesser. He gets one guess: At a moment of his choice he may assert that the next card will turn up red. After this card is turned up the game ends and he wins if his assertion was correct, loses otherwise. And if he doesn't guess at all by the time all cards have been dealt, he loses by default. What guessing policy chosen in advance maximizes his chance of winning?"

Here is a link to thread (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1039561777) discussing it.

Title: Re: Card Game
Post by Icarus on Mar 23^rd, 2007, 8:04pm

on 03/23/07 at 15:47:19, tiber13 wrote:

smq, how did you get the symbols on your post, i know you have to use ALT

There are a number of ways of putting symbols in that are not universal, so if you use them, some part of your audience will not be able to see what you've done. Instead, they will see a meaningless string of characters. The ALT method you are thinking of is one of these methods.

There is, however, a method in this forum that is universal, since it makes use of gif images to produce the symbols. Exactly how has undergone several alterations, but the current method - due to SMQ - is explained in this thread (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_suggestions;action=display;num=1171644142).

Title: Re: Card Game
Post by Eigenray on Mar 25^th, 2007, 2:45am

If there are n={1,2,3,...} cards left, then in order to keep playing, the number of red cards left should be at least

R = {1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 8, 9, ...}.

In the first 10000 terms, every positive integer appears exactly twice, except for the numbers

A = {2, 4, 8, 13, 19, 27, 37, 47, 60, 73, 88, 105, 123, 142, 163, 185, 209, 234, 260, 288, 317, 348, 380, 413, 448, 485, 522, 562, 602, 644, 688, 733, 779, 826, 876, 926, 978, 1031, 1086, 1142, 1200, 1259, 1319, 1381, 1445, 1509, 1575, 1643, 1712, 1782, 1854, 1927, 2002, 2078, 2155, 2234, 2315, 2396, 2479, 2564, 2650, 2737, 2826, 2916, 3008, 3101, 3195, 3291, 3389, 3487, 3587, 3689, 3792, 3896, 4002, 4109, 4218, 4328, 4440, 4552, 4667, 4783, 4900},

which all appear three times each. The above list actually contains all the information you need to play the game with less than 10,000 cards. And for a standard deck, you only need to know the first five numbers.

For example, suppose there are 100 red cards left. Since there are 11 numbers http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 100 in the above list, you should keep playing as long as there are http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 2*100+11 cards remaining.

Doing a log-log fit on the last 50 entries, log A[x] ~ 1.995 log x - 0.317, so A[x] is apparently quadratic: A[x] ~ .709 x² + 0.180 x + 0.730.

So A contains ~ sqrt(r/.709) numbers less than r, and if there are r red cards left, there should be no more than n ~ 2r + (r/.709)^1/2 cards left to keep playing. Solving for r, if there are n cards left, there should be at least r ~ n/2 - (n/(8*.709))^1/2 red cards left, which means

n - 2r ~ (.840 n)^1/2

is the asymptotic threshold, agreeing with the analysis [link=http://groups.google.com/group/sci.math/tree/browse_frm/thread/d0e19f5f063af009/427aa21415f50739]here[/link] (but disagreeing with SMQ).

Attached is a plot of f(n) = n - 2R[n], as a function of n, where R[n], as above, is the smallest r for which it is worth playing when there are r red cards left (out of n). For the most part, R[n+1] is alternately R[n] or R[n]+1, so f(n+1) is alternately f(n)+1 or f(n)-1, respectively; but when R[n+2]=R[n] (so R[n] http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif A), we have f(n+2) = f(n)+2. That is, f(n) mostly alternates up 1, down 1, but occasionally (~1/sqrt(n) of the time) goes up twice in a row, so at this resolution, the plot appears to consist of horizontal bars, bounded on either side by those n for which R[n] http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif A.

In red is the best <1, sqrt(n)>-fit through the last 50 "middle" points (n, f(n)) -- those for which R[n-1]=R[n+1] http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif A -- given by f(n) ~ 0.840 sqrt(n) - 1.493. (For clarity, only n<1000 is shown.)

Title: Re: Card Game
Post by Grimbal on Mar 25^th, 2007, 7:06am

on 03/23/07 at 12:52:06, SMQ wrote:

Yep, I said "roughly". The optimal limit is at +/- 1 card.

Title: Re: Card Game
Post by Grimbal on Mar 25^th, 2007, 7:09am

on 03/23/07 at 16:22:32, spanchap wrote:

Grimbal,

Apart from running simulations, one could also derive the expected value as follows:

I should have said "calculation". My formulas look much like the one you give. Probably they are a variation.

Title: Re: Card Game
Post by BenVitale on May 11^th, 2008, 12:27pm

A new problem:

When playing a game of blackjack, what are the odds that you will be dealt BlackJack on the first deal?

Assume you are playing with one opponent and your opponent is the dealer.

10, Jack, Queen, King are worth 10.
Aces are worth 11.
There's only one deck of cards being dealt.

To get a BlackJack (a natural), you need an ace and a card that is worth 10.

Title: Re: Card Game
Post by towr on May 11^th, 2008, 12:48pm

[hide]Either you get the 10/J/Q/K first and then the A, or first the A and then 10/J/Q/K
So, 2* 4/13 * 1/13 = 8/169[/hide]

Title: Re: Card Game
Post by BenVitale on May 11^th, 2008, 1:45pm

Perhaps i'm missing something here. This is how i see it:

First:
There are 16 ways to get a face card or 10. And there are 4 ways to get an ace. So there are 16*4 ways to get blackjack this way.

Second:
There are 52 cards in the deck,
so, there are 52 ways to draw the first card
then the dealer gets his first card,
then you're dealt w/ your second card
and 50 ways to draw the second.

so, 52*50 (number of ways)

The probability of getting blackjack is then:

(number of ways to get blackjack) / 52*50 = p

This gives a probability, and change that to odds.

Title: Re: Card Game
Post by towr on May 11^th, 2008, 2:02pm

It doesn't matter whether a card is in the dealer's hand or in the stack.

But I did make a mistake, it should be
16/52*4/51 + 4/52*16/51 = 32/663

Title: Re: Card Game
Post by temporary on May 13^th, 2008, 7:14pm

Do I not get to see the card until I stop or what, because if I do it is too easy to win(or in the worst case, draw)? The expected payoff(assuming I see the cards and play optimally) is [hide]13[/hide].

Title: Re: Card Game
Post by ThudanBlunder on May 13^th, 2008, 7:38pm

on 05/13/08 at 19:14:31, temporary wrote:

It asked for the expected value of the game, not your age. ::)

Title: Re: Card Game
Post by JiNbOtAk on May 14^th, 2008, 4:44am

on 03/23/07 at 12:52:06, SMQ wrote:

I don't know if that 1/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cphi.gif (where http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cphi.gif is the golden ratio) in the exponent is a coincidence or not...

Very interesting SMQ. Anyone has any idea why ? And does it only work for 52 cards deck ? What if we had an 80 cards deck ( Assuming 20 cards for each suit ) ?

Title: Re: Card Game
Post by SMQ on May 14^th, 2008, 5:26am

on 05/14/08 at 04:44:10, JiNbOtAk wrote:

Very interesting SMQ. Anyone has any idea why ? And does it only work for 52 cards deck ? What if we had an 80 cards deck ( Assuming 20 cards for each suit ) ?

Eigenray's analysis above (with the graph) is much more thorough than mine and shows that the apparent http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cphi.gif is just an illusion.

--SMQ

Title: Re: Card Game
Post by jollytall on May 19^th, 2008, 9:37am

I put together a small spreadsheet, I guess the same as Grimbal's. Here it goes.
The yellow points are the exit points.

Title: Re: Card Game
Post by BenVitale on May 25^th, 2008, 1:04pm

Suppose you are playing Blackjack and the first two cards you receive sum up to 15. Furthermore, suppose that the dealer's initial card is a 7. If you decide to hold, what is the probability that you will win this round?

(the dealer stands on all 17s-- the dealer stands on a soft 17 or on a hard 17)