From rusin Mon Mar 16 16:25:17 1998 Return-Path: Received: from vesuvius.math.niu.edu.niu.edu (vesuvius.math.niu.edu [131.156.3.93]) by clinch.math.niu.edu (8.8.5/8.8.5) with SMTP id QAA10582; Mon, 16 Mar 1998 16:25:15 -0600 (CST) Date: Mon, 16 Mar 1998 16:25:15 -0600 (CST) From: Dave Rusin Message-Id: <199803162225.QAA10582@clinch.math.niu.edu> Received: by vesuvius.math.niu.edu.niu.edu (4.1/SMI-4.1) id AA26848; Mon, 16 Mar 1998 16:25:13 CST To: lew@ihgp167e.ih.lucent.com Subject: Re: Memory Game Newsgroups: sci.math In-Reply-To: <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> Organization: Northern Illinois Univ., Dept. of Mathematical Sciences Cc: rusin@math.niu.edu Status: RO In article <6eevpn$2u8@ssbunews.ih.lucent.com> you write: >Your beta combines two distinct cases. Right, sorry; I posted a retraction since I forgot how to play correctly! >This is a tricky point ( which I explained in my post, AHEM! AHEM! ) For some reason I thought you were referring to the no-match case (type gamma) and hence I just thought you had neglected to combine two cases into beta. My error. >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 This isn't quite the worst case (if I've understood your example right). Play this game, selecting cards left to right: (Pairs are Aa, Bb, ..., Rr) A B C b D c E d . . . R q r a After an odd number of moves, what will be known but unremoved are, say, A and X; then Y and x are revealed; then X and x are removed, A and Y are known, and the cycle repeats. The first two cards are removed in move 3, so 2n cards have been removed by move 2n+1. So after 31 moves 6 cards remain: A* Q* R q r a ["*"= known] after move 32: A* Q* R* q* r a after move 33: A* R* r a after move 34: A* a which are then removed in move 35. How frequently does this occur and why didn't your program find it? Well, I modified the maple script I posted (appended below) and it finds these probabilities for game-lengths 0 through 36: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1/221643095476699771875, 305672 2/228733844661196875, 8/1126767707690625, -----------------, 98028790569084375 8864 2144048728 564887696012 348471427604 --------------, -----------------, -----------------, ---------------, 11070445010625 17594911127784375 52784733383353125 685516017965625 11219044933892 1166138753493068 19035863576369432 1764805130647928 ---------------, -----------------, -----------------, ----------------, 959722425151875 10556946676670625 52784733383353125 4668037646146875 86260431706344892 665075933620216 74859206110454 ------------------, -----------------, ------------------, 686201533983590625 52784733383353125 228733844661196875 18235827159734 7050672938 262142 --------------------, --------------------, ---------------------, 0 11665426077721040625 11665426077721040625 221643095476699771875 > print(seq(evalf(A[0,18,s]),s=0..36)); -20 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, .4511757959*10 , -17 -14 -11 -9 .8743786924*10 , .7099954982*10 , .3118185976*10 , .8006904864*10 , -6 .1218561840*10 , .00001070172491, .0005083344787, .01168988516, .1104617452, .3606319926, .3780614606, .1257071391, .01259977821, -5 -9 -14 .0003272764738, .1563237128*10 , .6044076651*10 , .1182721255*10 , 0 So a 35-turn game isn't as rare as 18 cold matches, but I guess it's too rare to be detected with double precision floats. Incidentally, we always played with a standard 52-card deck, matching any pairs of like number; this is clearly a more complicated analysis than a simple 26-pair deck. Maybe grist for another day's mill. dave NN:=18: # upper bound on number of pairs in game MM:=2*NN: #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 A[0,1,1]:=1: for m from 1 to NN do #Can only use alphas and one beta or delta if k=1. for s from 2 to m+2 do A[m,1,s]:=(m/(m+2*1))*A[m-1,1,s-1] +(2/(m+2)/(m+1))*A[m,0,s-1] +(2*m/(m+2)/(m+1))*A[m,0,s-2]: od: od: for k from 2 to NN do for m from 0 to NN-k do for s from m+k to m+2*k do A[m,k,s]:=(m/(m+2*k))*A[m-1,k,s-1] +(2*k/(m+2*k)/(m+2*k-1))*A[m,k-1,s-1] +(2*k*m/(m+2*k)/(m+2*k-1))*A[m,k-1,s-2] +(4*k*(k-1)/(m+2*k)/(m+2*k-1))*A[m+2,k-2,s-1]: od: od: od: From lew@ihgp.ih.lucent.com Wed Mar 18 00:01:34 1998 Return-Path: Received: from ihgw2.lucent.com (ihgw2.lucent.com [207.19.48.2]) by clinch.math.niu.edu (8.8.5/8.8.5) with SMTP id AAA17818 for ; Wed, 18 Mar 1998 00:01:33 -0600 (CST) Received: from ihgp1.ih.lucent.com by ihig2.firewall.lucent.com (SMI-8.6/EMS-L sol2) id XAA06067; Tue, 17 Mar 1998 23:51:49 -0600 Received: by ihgp1.ih.lucent.com (SMI-8.6/EMS-1.3.1 sol2) id AAA17931; Wed, 18 Mar 1998 00:01:30 -0600 From: mammel@lucent.com Received: from ihgp167e.ih.lucent.com by ihgp1.ih.lucent.com (SMI-8.6/EMS-1.3.1 sol2) id AAA17891; Wed, 18 Mar 1998 00:01:27 -0600 Received: by ihgp167e.ih.lucent.com (SMI-8.6/EMS-L sol2) id AAA07612; Wed, 18 Mar 1998 00:01:26 -0600 Date: Wed, 18 Mar 1998 00:01:26 -0600 Original-From: lew@ihgp.ih.lucent.com Message-Id: <199803180601.AAA07612@ihgp167e.ih.lucent.com> To: rusin@math.niu.edu Subject: Re: Memory Game X-Sun-Charset: US-ASCII Status: RO Hi, You're right about the worst case, but I somewhat arbitrarily restricted the precision to allow for roundoff. Jacking in a few more digits does the trick. 18 0.0000000000000000 0.0000000000000000 19 0.0000000000000000 0.0000000000000000 20 0.0000000000000071 0.0000000000000071 21 0.0000000000031253 0.0000000000031182 22 0.0000000008038158 0.0000000008006905 23 0.0000001226599998 0.0000001218561840 24 0.0000108243849078 0.0000107017249080 25 0.0005191588635654 0.0005083344786576 26 0.0122090440218877 0.0116898851583223 27 0.1226707891844423 0.1104617451625546 28 0.4833027817365319 0.3606319925520896 29 0.8613642423386428 0.3780614606021110 30 0.9870713814725049 0.1257071391338621 31 0.9996711596847023 0.0125997782121974 32 0.9999984361584631 0.0003272764737607 33 0.9999999993955911 0.0000015632371281 34 0.9999999999999988 0.0000000006044076 35 1.0000000000000000 0.0000000000000012 It's actually fairly interesting the way the distribution falls logarithmically away from that small plateau. There's probably some theoretical reason for it. > > In article <6eevpn$2u8@ssbunews.ih.lucent.com> you write: > > >Your beta combines two distinct cases. > Right, sorry; I posted a retraction since I forgot how to play correctly! > > >This is a tricky point ( which I explained in my post, AHEM! AHEM! ) > For some reason I thought you were referring to the no-match case > (type gamma) and hence I just thought you had neglected to combine two cases > into beta. My error. > > >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 > > This isn't quite the worst case (if I've understood your example right). > Play this game, selecting cards left to right: (Pairs are Aa, Bb, ..., Rr) > A B C b D c E d . . . R q r a > After an odd number of moves, what will be known but unremoved are, say, > A and X; then Y and x are revealed; then X and x are removed, A and Y are > known, and the cycle repeats. The first two cards are removed in move 3, > so 2n cards have been removed by move 2n+1. So after 31 moves 6 cards remain: > A* Q* R q r a ["*"= known] > after move 32: A* Q* R* q* r a > after move 33: A* R* r a > after move 34: A* a > which are then removed in move 35. > > How frequently does this occur and why didn't your program find it? From rusin Wed Mar 18 00:27:09 1998 Return-Path: Received: from vesuvius.math.niu.edu.niu.edu (vesuvius.math.niu.edu [131.156.3.93]) by clinch.math.niu.edu (8.8.5/8.8.5) with SMTP id AAA17868; Wed, 18 Mar 1998 00:27:08 -0600 (CST) Date: Wed, 18 Mar 1998 00:27:08 -0600 (CST) From: Dave Rusin Message-Id: <199803180627.AAA17868@clinch.math.niu.edu> To: mammel@lucent.com Subject: Re: Memory Game Cc: rusin Status: RO >It's actually fairly interesting the way the distribution >falls logarithmically away from that small plateau. There's >probably some theoretical reason for it. Yeah, I tried to work this out without success. If you start a fresh game with k pairs of cards, the game will take k+t rounds with some probability P(k,t); P(k,t)=0 if t<0 or t>=k. I looked at this string of numbers P(k,t) for various k up to 50. The peak is at about t=.6 k, but it seems still to be drifting higher at k=50. (Or maybe not; maybe it's exactly 6/Pi^2 in the limit? Just a guess.) Shape of the curve is remarkably constant for k=10..50 or so. Some data appended below, for your amusement. Actually I did it by induction, solving the larger problem of computing the probability of stopping in m+k+t turns when starting with m known (unparied) cards and k pairs of unknown cards (in addition to the m mates of the known cards). I computed these as functions of m when k (and so also, t) was less than 10, and it seems they have the form Q*(m+k)!/(m+2k)! where Q is a polynomial in m of degree t. So I can tell you what will happen in a game with few pairs of cards still unseen; but when the cards are still _all_ unseen, this method is not producing anything of interest. dave print(seq(C[10,j],j=0..10)); -8 -6 .1527349309*10 , .5040252718*10 , .00005947498208, .002964139022, .05842190527, .3596136310, .4741390261, .1023638701, .002435886935, -5 .1560950993*10 , 0 print(seq(C[30,j],j=0..30)); -40 -36 -32 -29 .3422828153*10 , .3077122510*10 , .1247157753*10 , .3005460204*10 , -26 -23 -20 .4785431387*10 , .5295180082*10 , .4173150398*10 , -17 -15 -12 .2363893119*10 , .9604185082*10 , .2765909005*10 , -10 -8 -6 .5525576266*10 , .7410342034*10 , .6367698751*10 , .00003288520960, .0009381616782, .01339047264, .08794597277, .2586093396, .3467865286, .2177444016, .06486392181, .009092273286, .0005795336228, .00001570304821, -6 -9 -12 -16 .1613632498*10 , .5202674035*10 , .3788357560*10 , .3306146930*10 , -22 -31 .7886162014*10 , .3675233738*10 , 0 print(seq(C[50,j],j=0..50)); -78 -73 -69 -65 .3669196757*10 , .1528220449*10 , .2993478216*10 , .3662972608*10 , -61 -57 -54 .3137228566*10 , .1997291631*10 , .9799228622*10 , -50 -46 -43 .3791368793*10 , .1174263395*10 , .2939377584*10 , -40 -37 -33 .5979902688*10 , .9911695249*10 , .1338223393*10 , -30 -27 -25 .1467911004*10 , .1301693633*10 , .9263130578*10 , -22 -19 -17 .5237394683*10 , .2322555586*10 , .7946738546*10 , -14 -12 -10 -8 .2055173227*10 , .3915519146*10 , .5322762640*10 , .4963350321*10 , -6 .3027308068*10 , .00001144107855, .0002538799029, .003180926716, .02225324033, .08816339327, .2029989280, .2789836816, .2339395179, .1215714829, .03949874208, .008040118915, .001020599799, .00007985558420, -5 -6 -8 -10 .3777495052*10 , .1050107094*10 , .1649115143*10 , .1386212800*10 , -13 -15 -19 .5793364213*10 , .1086599659*10 , .7901910263*10 , -22 -27 -32 .1792035822*10 , .8984825127*10 , .5520151266*10 , -38 -48 -63 .1333566059*10 , .9302495235*10 , .4131148287*10 , 0