# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Author Message
lostdummy
Daedalian Member

 Posted: Sun Mar 15, 2009 10:59 am    Post subject: 1 Another one that looked simple at first : Deck of 52 cards is shuffled, and then you predict color of each next card to be drawn. If you would guess at random black or red, expected number of correct guesses would be 26. But what would be expected number if you would guess color that has more cards remaining in deck (and random if even)? I'm still working on this one, although it shows certain similarities to one of previous problems ;p
ralphmerridew
Daedalian Member

 Posted: Sun Mar 15, 2009 1:19 pm    Post subject: 2 I get 3724430600965475/123979633237026 (def-auto avg-sum (r b) (cond ((= r 0) b) ((= b 0) r) ((>= r b) (/ (+ (* r (+ 1 (avg-sum (- r 1) b))) (* b (avg-sum r (- b 1)))) (+ r b))) (t (avg-sum b r)))) (avg-sum 26 26) Takes about .01s on my computer.
Zag
Tired of his old title

 Posted: Sun Mar 15, 2009 1:27 pm    Post subject: 3 I'm pretty sure you end up with a positive score (that is, greater than 26). Consider every sequence from the point that the count is even to when it is even again. Say the first card is black, so the deck is now +1, you are going to continue guessing red until the deck at zero again, which will net you one point. If we change the scoring so that you get +1 for a correct guess, -1 for an incorrect guess, and 0 if you choose not to guess (which you do whenever the count is zero). It is clear that you can guarantee a positive number. I don't see any way, other than simulation, to work this out, but my gut says that you will average about between 4-7 points.
ralphmerridew
Daedalian Member

 Posted: Sun Mar 15, 2009 1:29 pm    Post subject: 4 If I didn't make any mistakes in my algebra: Avg-sum(r,b) = sum (i = 0 to r+b-1: P(get i'th card correct)) Avg-sum(r,b) = sum (i = 0 to r+b-1: sum (j = 0 to i: P(get i'th card correct & exactly j red cards have been removed))) Avg-sum(r,b) = sum (i = 0 to r+b-1: sum (j = 0 to i: P(get i'th card correct | exactly j red cards have been removed) * P(exactly j red cards have been removed))) Avg-sum(r,b) = sum (i = 0 to r+b-1: sum (j = 0 to i: (max(r-j, b+j-i)/(r+b-i)) * (C(j,r)*C(i-j,b)/C(i,r+b))))
Zag
Tired of his old title

 Posted: Sun Mar 15, 2009 1:30 pm    Post subject: 5 Nice simulpost. You LISP guys kill me -- a write-only language.
ralphmerridew
Daedalian Member

Posted: Sun Mar 15, 2009 2:02 pm    Post subject: 6

Regarding Zag's alternate problem, I analyzed that (except this code will guess on an even split, but gets the same average result):
 Code: (def-auto avg-sum2 (r b)   (cond ((= r 0) b)         ((= b 0) r)         ((>= r b) (/ (+ (* r (+ 1 (avg-sum2 (- r 1) b)))                         (* b (+ -1 (avg-sum2 r (- b 1)))))                      (+ r b)))         (t (avg-sum2 b r))))

First, def-auto is a macro I wrote that memoizes a recursive function. (The first time it's asked for a value, it calculates the answer and stores it; the second time, it returns the stored value.

avg-sum2 (r, b) := expected number of points gained starting a deck with 'r' red cards and 'b' black cards. It works by the following rules:
- If there are no red cards, then you will get one point for each black card. (Can be removed due to the way I later wrote the function.)
- If there are no black cards, then you will get one point for each red card.
- If there are at least as many red cards as black, then it uses the rule
-- P(draw red)*(points for getting this card right + expected score with one less red card) + P(draw black)*(points for getting this card wrong + expected score with one less black card)
- Otherwise (more black cards than red), the result is the same as if the number of red & black cards are interchanged.

Alternately, avg-sum2(r, b) = (avg number of correct guesses with r red & b black) - (avg number of incorrect guesses with r red & b black)
= avg-sum (r, b) - (r + b - (avg-sum(r,b))
= 2*avg-sum(r,b) - (r + b)

Running the program gives that you wind up 500960136802799/61989816618513 to the good on average, or about 8.08.
lostdummy
Daedalian Member

 Posted: Sun Mar 15, 2009 5:31 pm    Post subject: 7 Nice work - I got same result, although this time for a change I solved it symbolically (without program): 1) "pk" is probability that after "m" draws we had "k" in specific color pk(m,k):= C(m,k)*C(52-m,26-k)/C(52,26) , or 0 if (k>m) or (m>26+k) 2) "pg" is probability to correctly make single guess, if "m" cards were previously drawn pg(m):=sum(k=0..26)[ pk(m,k)* (26-min(k,m-k))/(52-m)] 3) "Ec" is expected number of correct guesses Ec:= sum(m=0..51)[ pg(m) ] And it result in Ec=30.0406648 BTW, I started working on extension of this problem, which proved to be separate problem in itself: If person A use above approach (guess color that remained most) , and person B just guesses randomly, how often will person A win match after whole deck is dealt? So far I have solution for this by program calculation, but not sure if it is correct since I have no idea how to solve this one symbolically and I prefer waiting for someone else to solve to compare numbers over writing simulation to compare ;p
ralphmerridew
Daedalian Member

 Posted: Mon Mar 16, 2009 3:55 pm    Post subject: 8 (def-auto a-gets-n (n r b) (cond ((= b 0) (if (= r n) 1 0)) ((> b r) (a-gets-n n b r)) (t (/ (+ (* r (a-gets-n (- n 1) (- r 1) b)) (* b (a-gets-n n r (- b 1)))) (+ r b))))) (def-auto b-gets-n (n ct) (cond ((= ct 0) (if (= n 0) 1 0)) (t (/ (+ (b-gets-n (- n 1) (- ct 1)) (b-gets-n n (- ct 1))) 2)))) (defun a-wins (r b) (loop for a-n from 0 to (+ r b) sum (loop for b-n from 0 below a-n sum (* (a-gets-n a-n r b) (b-gets-n b-n (+ r b)))))) (a-wins 26 26) 4558408532693194411385847/5750778952414215943487488 0.7926593197917203d0
lostdummy
Daedalian Member

 Posted: Sat Mar 21, 2009 4:34 pm    Post subject: 9 I get similar number as result, although not exactly same: 1) chance for "optimal" strategy to guess correctly I use same formula for "pg" as posted in previous post - probability to correctly make single guess, if "m" cards were previously drawn , and if used "optimal" strategy (one with guessing color that most remained). 2) chance for "optimal" strategy to win k-th deal Probability that at k-th deal (any of 52 deals) "optimal" player will win over "random" player is half of his chances to guess right at that point (since one who guess random will in half of his correct guesses also guess correctly): wo(k)= pg(k-1)/2 Also, chance for "random" player to win any deal is half of cases when "optimall" guess wrong, ie: wr(k)= (1-pg(k-1))/2 BTW, chance that they are even (bot correct or both wrong) at every step is 1/2. 3) Probability of each possible score at each of 52 draws: Ps[s,d]= probability that after d-th deal we have score "s", such that sum(s=all s) Ps[s, d]=1 Ps[0,0]=1 for (d=1..52); for(s= -d+1 .. d-1); pold=Ps[s,d-1] // chance of this score (s) after previous deal Ps[s,d] += 1/2*pold // in half cases it is even, so score remains same Ps[s+1,d] += wo(d)*pold // if optimal win, score++ Ps[s-1,d] += wr(d)*pold // if random win, score-- 4) chance for "optimal" to win after 52 deals: pW = sum (s=1..52) Ps[s,52] When calculated above, pW= 0.75931 But after I did that, I saw potential problem with solution: chance for optimal player to win k-th deal is not independent of current score before k-th deal.
extropalopakettle
No offense, but....

Posted: Sun Mar 22, 2009 3:23 pm    Post subject: 10

 ralphmerridew wrote: def-auto is a macro I wrote that memoizes a recursive function

First, let me say: AWESOME! that someone here knows LISP.

Second, awesome idea for a macro!

(carry on)
Thok
Oh, foe, the cursed teeth!

Posted: Sun Mar 22, 2009 5:52 pm    Post subject: 11

 Zag wrote: I'm pretty sure you end up with a positive score (that is, greater than 26). Consider every sequence from the point that the count is even to when it is even again. Say the first card is black, so the deck is now +1, you are going to continue guessing red until the deck at zero again, which will net you one point.

So what you've told me is that for each time the score is 0, with a nonzero number of cards drawn cards, there's a 50% chance of getting 1 card above 26 (you always guess half the cards right from the previous 0, and you have a 50% chance of geting a bonus from the first card after the previous zero).

At each stage of 2n card, there is a C(2n,n)*(26*25*...*[26-n+1])^2/(52*...*52-2n+1) chance of have a zero there. (The denominator is the way to pick 2n cards from a deck in order, for the numerator, pick the n places out of 2n where the red cards are, then pick n red cards and n black cards in order and place the red cards and black cards as appropriate.)

So the expected number of cards above 26 is 1/2*Sum n=1 to 26 [C(2n,n)*(26*25*...*[26-n+1])^2/(52*...*52-2n+1)]

I don't know if the above can be simplified at all.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year by All usersextropalopakettlelostdummyralphmerridewThokZag Oldest FirstNewest First
 All times are GMT Page 1 of 1

 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
You cannot post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum