52 card pickup

This is a fun little puzzle. You have a deck of 52 playing cards, and you hand them all to your young niece. Your niece, thinking it hilarious, throws the entire deck high into the air and the cards flutter down and scatter over the floor in a random mix of face-up and face-down cards.
(Because they got thrown high into the air, we are going to assume that each card, individually, has a 50:50 chance of landing face-up or face-down).
You collect them all together back into a stack but discard all the cards that landed face-up.
You hand this, shorter, stack back to your niece, and she repeats her trick of throwing them up into the air and scattering them. Again, you collect them and discard the face-up cards, handing those that remain back to her.
You repeat this process until all the cards have been discarded. What is the expected number of rounds this game will take?
How long will this fun game take?

Monte-Carlo

This is one of those great problems that is fun to model. In just a few minutes you can write a few lines of code to simulate the tosses with random numbers, and count the number of throws required. Then, Monte-Carlo style, you can run your simulation a few million times to get a really good approximation for the expected number of throws. I have to admit, this is how I first approached the problem, and I obtained the answers which I used to confirm that my mathematical analysis was correct.

Canonical Forms

I can think of some canonical variants of this puzzle. If, instead of cards, you had a bucket of coins and flipped them in rounds, and on each round you discarded all those that landed tails. How many rounds would it take you to empty your bucket? Maybe you have a birthday cake adorned with ‘trick’ candles, and after blowing them out, each candle has a 50:50 chance of re-lighting. What is the expected number of blows to extinguish all the candles?

Analysis

This is a recursive problem. A large number of cards reduces to a smaller set, then to a smaller set, all the way down. We can solve this by starting at the base case and working our way up. (A 52 card game reducing to a 32 card game, is no different from that point onwards as a game that started with 32 cards).
The base case is when we have one card. If we only have one card, what is the expected number of trials? There are only two things that can happen when we throw one card. Either it lands face-up (game over), or it lands face-down, and we are back to where we started. We can write a formula for this.
If we say that E(x) is the expected number of turns when there are x cards remaining, then here is the formula for E(1).
There is a probability of ½ that it will land face-up (game over), and this takes one move. Or, there is a probability of ½ that is will land face-down and this will have taken us one move and we’re back to where we started. The formula is self-referential. With a little algebra we can re-arrange and see that the expected number of turns when there is only one card left is 2 (from here on out, I’ve used E1 instead of E(1) as the nomenclature to described the expected number of moves as it is easier to read!)
Next let’s consider what happens when there are two cards left. One of three things could happen:
• Both cards land face-up (chance ½ × ½ = ¼), and it’s game over, taking just that one round.
• Both cards land face-down (chance ½ × ½ = ¼), wasting a round and we’re back to where we started with two cards face-down.
• One card landing face-up and one card landing face-down (chance ½), and this has taken one round, but now we’ve reduced the problem to only one card left, which we already solved and know the expected number of moves from that point.
Writing this as a self-referential formula for E2, we can substitute in the value for E1 = 2 that we already calculated and obtain the solution for E2 = 8/3.
Similarly, when we have three cards left, we can have all three land face-up, have two land face-up, one land face-up, or none land face up.
Again we can write a formula, and substitute, as appropriate, the solutions we already know for E2 and E1.
This gives a result for E3.
And so for E4
And E5
If you are familiar with the binomial theorem, you’ve probably spotted the pattern by now, with the parameters representing the binomial coefficients for the number of combinations. In no surprise to anyone, these can also be found in Pascal’s Triangle
Generically, there is a formula for the expected number of trials it will take to finish the game starting with n cards:
Cutting to the chase, here are all the results in tabular form. On the left is the number of cards. In the middle is the expected number of turns (in rounded decimal form), and on the right is the exact answer if you want to do the division.
NExpectedRatio
122
22.6666666678 / 3
33.14285714322 / 7
43.504761905368 / 105
53.7941628262470 / 651
64.0348182287880 / 1953
74.240848926150266 / 35433
84.42107772613315424 / 3011805
94.5813101922350261538 / 513010785
104.7255593241777792792 / 376207909
114.85672201340013628538 / 70008871793
124.976966144203832594062416 / 40955189998905
135.087961539131294440969788022 / 25804920098540835
145.191024016822860039794822168 / 158515937748179415
155.287209474177175812995012739374 / 33510269239965128331
165.377377902231553634961214157747264 / 43060695973355189905335
175.4622385541813465925343969651214825522 / 332000498936684593887186105
185.54238277614983458468103810854318443432 / 2703432634198717407367086855
195.618308422419118293202270652551058824971246 / 74598662394007523860856203470915
205.690438361957245448296134815166548035810677744 / 168219983698486966306230738826913325
215.75913470115997819920041381172996946639598567853322 / 2777816590813115274614788190248819735725
225.8247098571004629398962208518335718632944853920778216 / 172477157411396157505627303085449443590925
235.887435255370356305063039431249700901265882284780644902994 / 62906221304406073331513379741466208724040808325
245.94754822319926952553863277281649067043965751602546940593375904 / 3350448252893971871709734118410231742851137492197825
256.0052575174355647554571850124152619507048246830952512482053380184314 / 725305707876137609582097583900270649738762814538483595565
266.060747764923476084609715412475893251255716866736272968716013010867368 / 152369991400748600905285269356279934187427788192661438422155
276.1141830734797960683843138105983901203020953803581431625690850487123547946 / 784726369242086769960382607712008209291514128692546577091136585
286.165709998269542159343895657509952303227407839058359990344908292442274298664656 / 43716321304107411867722954693028265331420960595333077263170128013765
296.2154599685030240603353911185019649911663910424320080679721904259748482335225032852254 / 809311077382926008664711523505441729559644415148674880645225288784021934135
306.2635513156152272295229061448667491550002707202162123303490067362560058343899776476596616 / 982233877583744532516071552361104445775555105185441746809755092154207954061845
316.310090961429357150728754480560662348879788829530404391182876716173286881137001622838684482265362 / 68042941601306169567868497528302452779419445830100033991776241305681922051133527875765
326.3551758451889321865157655935212321410354950581504203995260966246373219791333722288719259466941179520 / 297288684248320162331293181500823856520320814757817728514602635096698408364342534426267387
336.3988941287153419320484531952473738619667018781510703214740098858786348849530426741122690054452173677515782 / 1117914936088219259909080914141121322102112065273084106452925240261292990472862834134307266864067
346.44132621824003398681250390133286948336914405521560656088511043048333946198412852958186847249633454369530312 / 3726468411736506270289742444475450651099670271141093896012417538128950335450511183807279987530171
356.482545658398317377316604212780871552525168440178841328095156085843678866116423181775506919057170701564984069705974742 / 1295527687900007543723673530264953456458053115692465187399843086483116374812796357616951808724924661663152935
366.522619844227278160621192938936250648813873556860714544804436068433294929205519796977548453870540820210476226481493553310585552 / 34844612449390571196572789992868018566311943869754452000125609441967557216925831419785072352754845519291109402535995
376.56161076336925499797732758842174956307878778802577836896431020231866023597051742995077975584827964243403972376601741431973438536612702 / 5627505369150197481776592806691471240398720777422733034830042916862629108141715156476886519283950307867971349094142451477895
386.5995754797856979944159715313072278959756522767448939001702324609812732453456583520639998243151177036534749502331364768108184301398176695432 / 1190528083108542480930401149449678764888075668535198376179898114549066524684311737657974354300067535581073493067369010352395861545
396.6365666745827397172205445293639704236120962448643291034117615361161427118598995698536151445281360081693548222071543304266716417554573961101704974 / 878074079275788822851946670115160530710797508410879295828282022070134365209108328595157266396657449334554261048260557229179594789888715
406.672633077337902510094510736525670256499889776984957775193708928611681316621640961772682147508153168262579843878556807472085008246994041731992405139264224 / 50640055610362284907479412593013957609612475543732501865995286282092940524732915113032832150952433303798339686296105067473579858129842650970525
416.70781984418218873878277805235602500862421320459916017065238677505841120887774607512406872264623551152821004032367366109642877686753095472495680641019296704765876214 / 2716064876819086686043716358775578040533481363455683295786613092265079732357385200649463114774077115830824867096278659181631709714757739044014051103503275
426.742168999233639167261065056160413546786758551878469701526039592821531883710784980903797092110584834022369397300973746593333441093682846967650625345156963589009581816 / 14718355567482630751670898948204857401650935508566347779867656346984467069644670402319440618960723890687239954794734054105262234944272187879512142929884247225
436.77571923920400276346676396531883380183447924375883847222405738938192420384140449925410956508553064359706844939827366188919297442941154535671357342865072696566422128240003559942434 / 3010791272220826001475439852194599109289424432298005036762612048084574102267815302994149093410788570117850976655391030844269245290075033332770094885601871531861195421525
446.8085071871563255147218453018818614077479104584228295421285565580335292508391581055316100139626942882755105424161934261292988540363398146258344939180512686971864647192199350166220298224 / 229603216127857665493062631804710327583421442609266982103974682297115810545680164807724991149787955519784598920737997775004958488479784776050986778711897414098964932045080275
456.84056664523102570759834218693908461758875860792345792168661782946449239780543695897351515877774381924386247203751090409572609958538076886235675307847678789053988439853581503857461169803908774 / 3377289040399745215434842079309749143613493603907376873110050659806710062226751053076545556545098136637791933613475107130011710602044877899064992815886968631258473035999708629321275
466.8719292932821550153361745541848913038990129594470771701398426083340199669101915017912804285360809519809664415062167351517354285230563307141400026159024122181087028175620914491169061145942619867864 / 410590684636212555244980509856180803679107898075070388466127955874065308527331651081121561515133610650478422528078258042706962400894334509391270874207025623810036351247021446453653787775
476.9026247878486630560567079345224854302687910433640039177826588989723769285021826304402891341324576244839811170578419738509837138196499706031354129978915350027923203357198792691079783827228769950208598334578774 / 1229478759527546916148325110290453557644382129466634340323990585506269022275439144662568220722958711400133184178869998850656123488367115346936618514509210301404623384994473456075832596110128694653775
486.9326809217233565080841646748303518698632566039487692375493151907582665590007438523009999668673731375292937136786729265213485034816234533465039794821363895242440031237039887089514078549370060662247674153426883767232 / 1043400837709331273030024549823324283055577827318247632818975582361651724561118256435322508221201079305857227152950561134605871166773217540523802112193784849917937849545714881919123560186649047104010115075
496.9621237864600033011954980440233977994246560790358679502835095869284656466018690600628699170359441798623381140662058001058784734357587654689905019075237019939931191366931240273084532361921590080824495355486666392531544669140618 / 660722669278093271259660917754149872396525097069829213659259606332097737822745014414258770843632646186686216618553269326306811821193444503083285770142199662366581389384091763169545377530365150236776802111848646869925
506.99097790310332746687276762385115122228406199608676601608975702653299579220748965954694430427169775808642837349873661051181533428302893625974702475381462183345692300813338871306635904226681345426995007475142461048909987112232071510664 / 1478011635858195935882207857833342157685850053496538711411487419351783286214990897483152011395668340205591209836715482169367803646522894241195093719605989269566805111275694555541625200720156193276990756161085595169170541835
517.0192663491497772249973675756466110919374375764082689785442534651428290884370874091748529864511891032821788511509790621418730088221404303691704048311320979366161494368911287684624358418073287441234079354047377231282951694335709056204614056882 / 213380170452880643647165432935329728842116289448184863955124392413579022105729816605153043772669319440494289225476579089963174656930998825379122101596386399915100454541053328252593459853529075509065906412051049230297040900858229005
527.0470108661552478290980420733245193348826831177831323149183061446434572784088228160401230114640429230026056684661322287527900242543852201557116584192380766505499925751512704422475300156017883634203799277213607704864374861066993527416290576835817328 / 220303093116913168855857425715747638513110590505833269695504752441383057866545199831230367982756246891907796752360958566310177584975441761346555060531510452303669044080525919438522775341436961567887849069368742090836277349464204222086605
We can see from this that the expected number of turns to complete 52 card pick is, mercifully, just a hair over seven tosses.
Here is the data plotted in graph format.
On average, the game will take seven tosses!