From lew@ihgp167e.ih.lucent.com Wed Mar 18 09:03:25 CST 1998 Article: 184715 of sci.math Path: gannett.math.niu.edu!corn.cso.niu.edu!vixen.cso.uiuc.edu!logbridge.uoregon.edu!ais.net!uunet!in3.uu.net!nntphub.cb.lucent.com!ssbunews.ih.lucent.com!not-for-mail From: lew@ihgp167e.ih.lucent.com (-Mammel,L.H.) Newsgroups: sci.math Subject: Re: Memory Game Date: 13 Mar 1998 03:06:59 GMT Organization: Lucent Technologies Lines: 79 Message-ID: <6ea7sj$dpg@ssbunews.ih.lucent.com> References: <3506E6E8.6D19998@forfree.at-this> NNTP-Posting-Host: ihgp167e.ih.lucent.com Xref: gannett.math.niu.edu sci.math:184715 In article <3506E6E8.6D19998@forfree.at-this>, Axxl wrote: >Consider someone playing Memory: >- the game consists of 36 cards (18 pairs) >- the player doesn't forget the position of a card => he won't turn a >card twice, unless to complete a pair > >What's the probability of the player finding all the pairs in exactly >25,27 or 29 turns? Whats the probability that he will need more than 28 >turns? /* Represent a state by (n,m) = ( unknown cards, known unmatched cards ) State transitions, with probability are: (m,n) -> (n-1,m-1) m/n "First card matches a known" (m,n) -> (n-2,m) (n-m)/m * 1/(n-1) "cold match" (m,n) -> (n-2,m+2) (n-m)/m * (n-m-2)/(n-1) "no match" (m,n) -> (n-2,m) (n-m)/n * m/(n-1) "second card matches a known" The last case requires an extra turn. This is represented in the calculation by propagating the value from two turns ago. The state tables are way bigger than they need to be. */ typedef double (*STATE)[37]; main(){ int m,n,turn; STATE a,b,c; a = (STATE)calloc( 37*37,sizeof(double) ); b = (STATE)calloc( 37*37,sizeof(double) ); turn=0; b[36][0]=1.0; while(1){ c = (STATE)calloc( 37*37, sizeof(double) ); c[0][0] = b[0][0]; for( n=1 ; n<37 ; n++ )for( m=0 ; m<37-n ; m++ ){ if( m > 0 )c[n-1][m-1] += b[n][m]*m/n; if( n>1 ){ c[n-2][m] += b[n][m]*(n-m)/(n-1)/n; c[n-2][m+2] += b[n][m]*(n-m-2)*(n-m)/(n-1)/n; c[n-2][m] += a[n][m]*m*(n-m)/(n-1)/n; } } ++turn; if( c[0][0] > 0 ) printf("%d %16.12f %16.12f\n",turn, c[0][0], c[0][0]-b[0][0] ); if( c[0][0] > 0.999999999999 ) exit(); free(a); a=b; b=c; } } 18 0.000000000000 0.000000000000 19 0.000000000000 0.000000000000 20 0.000000000000 0.000000000000 21 0.000000000003 0.000000000003 22 0.000000000804 0.000000000801 23 0.000000122660 0.000000121856 24 0.000010824385 0.000010701725 25 0.000519158864 0.000508334479 26 0.012209044022 0.011689885158 27 0.122670789184 0.110461745163 28 0.483302781737 0.360631992552 29 0.861364242339 0.378061460602 30 0.987071381473 0.125707139134 31 0.999671159685 0.012599778212 32 0.999998436158 0.000327276474 33 0.999999999396 0.000001563237 34 1.000000000000 0.000000000604 I originally terminated at 0.99999999 and stopped at 33, but I came up with a worst case of 34 turns, and sure enough it showed up with higher precision. Lew Mammel, Jr. From rusin@vesuvius.math.niu.edu Wed Mar 18 09:03:32 CST 1998 Article: 184836 of sci.math Path: gannett.math.niu.edu!rusin From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Memory Game Date: 14 Mar 1998 06:14:56 GMT Organization: Northern Illinois Univ., Dept. of Mathematical Sciences Lines: 90 Message-ID: <6ed790$cm4$1@gannett.math.niu.edu> References: <3506E6E8.6D19998@forfree.at-this> <6ea7sj$dpg@ssbunews.ih.lucent.com> NNTP-Posting-Host: vesuvius.math.niu.edu Xref: gannett.math.niu.edu sci.math:184836 In article <3506E6E8.6D19998@forfree.at-this>, Axxl wrote: >Consider someone playing Memory: >- the game consists of 36 cards (18 pairs) >- the player doesn't forget the position of a card => he won't turn a >card twice, unless to complete a pair > >What's the probability of the player finding all the pairs in exactly >25,27 or 29 turns? Whats the probability that he will need more than 28 >turns? I see that -Mammel,L.H. responded with esentially the same idea I had, but perhaps we don't agree on the rules of the game: he reports > I came up with a worst case of 34 turns, but I don't see how that can happen. There are three kinds of turns: alpha: first card uncovered matches a previously-uncovered one beta: first card is new but second matches (first or) something known gamma: no matches Every turn of type alpha or beta removes two cards from play, so there can be only (exactly) 18 of these types of turns. Yet every turn of type gamma reveals two distinct new classes of cards (of the 18 equivalence classes) so there can be only 9 such turns, 27 total. I'll mesh my response with Mammel's. At any given point in play there are m known cards whose mates have not been seen, and k pairs of cards neither of which have been seen (so Mammel's n is m+2k). The possible pairs (m,k) are the lattice points in the first quadrant. The three types of turns indicate the possible transitions, giving a diagram reminiscent of those used to illustrate decay series among radioactive elements. A decay series starting at a point (m,k) which involves c turns of type gamma will also involve m+2*c turns of type alpha and k-2*c turns of type beta, and thus is of length m+k+c, where 0 <= c <= floor(k/2). So we can compute the probabilities A[m,k,s] that the decay series has length s. (The probabilities of following paths alpha, beta, or gamma at each point are as claimed in Mammel's program): #Maple program. NN:=18: # upper bound on number of pairs in game MM:=floor(3*NN/2): #max number of turns A:=array[0..NN,0..NN,0..MM]: for m from 0 to NN do for k from 0 to NN do for s from 0 to MM do A[m,k,s]:=0:od:od:od: for m from 0 to NN do A[m,0,m]:=1:od: #Can only use moves of type alpha for m from 0 to NN do A[m,1,m+1]:=1:od: #Must be one beta, m alphas for k from 2 to NN do for m from 0 to NN-k do for s from m+k to m+k+floor(k/2) do A[m,k,s]:=(m/(m+2*k))*A[m-1,k,s-1] +(2*k*(m+1)/(m+2*k)/(m+2*k-1))*A[m,k-1,s-1] +(4*k*(k-1)/(m+2*k)/(m+2*k-1))*A[m+2,k-2,s-1]: od: od: od: Then the command print(seq(A[0,NN,s],s=NN..MM)); brings 14873902 8270483968 1/221643095476699771875, -------------------, ------------------, 5683156294274353125 169064146053928125 7155343280752 8149537160656 540900738016 7707321152 ------------------, ----------------, -------------, -----------, 228733844661196875 2970569411184375 9935014753125 25805233125 479906816 35569664 851968 ----------, ---------, --------- 1032209325 206441865 123865119 These fractions are roughly -20 -11 -7 .4511757959*10 , .2617190383*10 , .4891920706*10 , .00003128239851, .002743425934, .05444387869, .2986727969, .4649316804, .1722986953, .006878191430 i.e., nearly half the games will have 25 turns: 14 alphas, 4 betas, 7 gammas. I actually dealt myself a couple of hands just now; those distributions seem consistent with this limited observation. One can work out the vectors A[m,k,*], e.g. A[m,0,*] and A[m,1,*] are just the singleton [1] and A[m,2,*]=[(3m+4)/(3m+12), 8/(3m+12)]. If this was a homework problem, consider your penance to be the computation of the ten probabilities A[m,18,m+18], ..., A[m,18,m+27] as functions of m. dave From lew@ihgp167e.ih.lucent.com Wed Mar 18 09:03:37 CST 1998 Article: 184946 of sci.math Path: gannett.math.niu.edu!corn.cso.niu.edu!vixen.cso.uiuc.edu!howland.erols.net!Supernews73!Supernews60!supernews.com!uunet!in1.uu.net!nntphub.cb.lucent.com!ssbunews.ih.lucent.com!not-for-mail From: lew@ihgp167e.ih.lucent.com (-Mammel,L.H.) Newsgroups: sci.math Subject: Re: Memory Game Date: 14 Mar 1998 22:19:35 GMT Organization: Lucent Technologies Lines: 45 Message-ID: <6eevpn$2u8@ssbunews.ih.lucent.com> References: <3506E6E8.6D19998@forfree.at-this> <6ea7sj$dpg@ssbunews.ih.lucent.com> <6ed790$cm4$1@gannett.math.niu.edu> NNTP-Posting-Host: ihgp167e.ih.lucent.com Xref: gannett.math.niu.edu sci.math:184946 In article <6ed790$cm4$1@gannett.math.niu.edu>, Dave Rusin wrote: > >I see that -Mammel,L.H. responded with >esentially the same idea I had, but perhaps we don't agree on the rules of >the game: he reports > >> I came up with a worst case of 34 turns, > >but I don't see how that can happen. There are three kinds of turns: > alpha: first card uncovered matches a previously-uncovered one > beta: first card is new but second matches (first or) something known > gamma: no matches Your beta combines two distinct cases. A turn means turning up two cards. If this exposes a pair they are removed. If the second matches a known but face down card, another turn is required to turn them up and remove them. This is a tricky point ( which I explained in my post, AHEM! AHEM! ) and approximately doubles the number of possible states after N turns >from (n unknown, m known ) to (n unknown, m known with a match). The second type of state propagates to (n unknown, m-2 known ) with probability one. A worst case game happens this way ( matching animals with their babies ): 1 cow, pig 2 dog, calf 3 cow, calf ( 34 left ) 4 cat, puppy 5 dog, puppy ( 32 left ) . . . 33 chicken, chick ( 2 left ) 34 piglet, pig I hope you're not going to claim that you play by : 1 cow, pig 2 dog, calf - "Oh, the calf matches the cow from last turn so I'll take that pair and leave the dog" That's simply not the game. Lew Mammel, Jr. From rusin@vesuvius.math.niu.edu Wed Mar 18 09:24:34 CST 1998 Article: 185114 of sci.math Path: gannett.math.niu.edu!rusin From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Memory Game Date: 16 Mar 1998 14:38:28 GMT Organization: Northern Illinois Univ., Dept. of Mathematical Sciences Lines: 9 Message-ID: <6ejdh4$s8d$1@gannett.math.niu.edu> References: <3506E6E8.6D19998@forfree.at-this> <6ea7sj$dpg@ssbunews.ih.lucent.com> <6ed790$cm4$1@gannett.math.niu.edu> <6eevpn$2u8@ssbunews.ih.lucent.com> NNTP-Posting-Host: vesuvius.math.niu.edu Xref: gannett.math.niu.edu sci.math:185114 >Dave Rusin wrote: > perhaps we don't agree on the rules of the game Sorry. Guess I haven't played much now that my kids are teens. Lew Mammel's interpretation is the usual one. dave (I've been having a lot of trouble with my memory lately. Sometimes I start my sentences and then forget to