# Coin Flipper Club Puzzle **URL:** \ **Category:** The Game Room\ **Created:** [August 30, 2022, 3:50pm UTC](https://boards.straightdope.com/t/coin-flipper-club-puzzle/970613 "2022-08-30T15:50:12Z")\ **Posts on this page:** 12\ **Page:** 1
**Author:** ![Biotop](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/biotop/32/321_2.png) [@Biotop](https://boards.straightdope.com/u/Biotop)\ **Post date:** [August 30, 2022, 3:50pm UTC](https://boards.straightdope.com/t/coin-flipper-club-puzzle/970613/1 "2022-08-30T15:50:12Z")
I came across this riddle on the internet… You have been selected to be a member of the prestigious “Supreme Coin Flipper Club.” Congratulations! What an honor! There are annual dues, however. These dues, appropriately enough, are determined by coin flips. You are to select a sequence of any five consecutive coin flip outcomes to determine your dues. (Example: you could pick all tails T-T-T-T-T). Once you do, the Club president begins flipping a coin, and after each flip the result is noted. When your predicted sequence finally appears in the string of flips, the flipping stops and your dues are equal to the exact final number of flips that were needed to achieve this outcome. So in the example, if it took 35 flips to get a consecutive string of five tails, then your annual dues are $35.00. You want to pay the lowest dues possible, of course. Does it matter what sequence you pick? ---
**Author:** ![Great\_Antibob](https://avatars.discourse-cdn.com/v4/letter/g/e47c2d/32.png) [@Great\_Antibob](https://boards.straightdope.com/u/Great_Antibob)\ **Post date:** [August 30, 2022, 6:15pm UTC](https://boards.straightdope.com/t/coin-flipper-club-puzzle/970613/2 "2022-08-30T18:15:16Z")
It does matter. Let’s take the all tails example. You have a 1/32 chance of hitting it after 5 flips (all 5 tails in a row). Failing that, you can hit it on 6 flips if you have H-T-T-T-T-T with 1/64 overall chance (1/32 for the first 5 times 1/2 for the 6th). You can hit it on 7 flips in 2 different ways (H-H-T-T-T-T-T, T-H-T-T-T-T-T) or 2/128 chance. Now, let’s say you chose H-T-H-T-H. You again have a 1/32 chance of hitting it after 5 flips. But failing that, you can now hit it on 6 flips in 2 different ways rather than just 1 (H-H-T-H-T-H OR T-H-T-H-T-H). And in 7 flips now in 3 different ways rather than 2 (T-H-H-T-H-T-H, H-H-H-T-H-T-H, T-T-H-T-H-T-H) You will always have a higher chance of hitting H-T-H-T-H than T-T-T-T-T for a given number of flips, so your expected dues will be lower for the former than the latter. What is the ‘optimal’ choice of sequence? I suspect either H-T-H-T-H or T-H-T-H-T, but that’s purely based on intuition at the moment. This sounds a lot like a stopping problem, so I’ll take a look and refresh my admittedly very old knowledge on the subject. ---
**Author:** ![Pasta](https://avatars.discourse-cdn.com/v4/letter/p/ecccb3/32.png) [@Pasta](https://boards.straightdope.com/u/Pasta)\ **Post date:** [August 30, 2022, 6:16pm UTC](https://boards.straightdope.com/t/coin-flipper-club-puzzle/970613/3 "2022-08-30T18:16:08Z")
At first glance it seems like I… …would want to pick a sequence whose first and last coin choices were opposite. That should given me the best fee since a last-coin failure in the sequence would set me up with the start of the next attempt already in hand. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [August 30, 2022, 6:22pm UTC](https://boards.straightdope.com/t/coin-flipper-club-puzzle/970613/4 "2022-08-30T18:22:25Z")
Multiply ninjaed here—yes, it matters; there is not a unique solution but you want to avoid sequences like `TTTTT` and even `HTHTH` over “optimal” sequences like `TTHTH` or `TTHHH`. Then again, I should re-check my calculations. > [@Pasta](#): > > At first glance it seems like I… That’s true, but there could be other “inefficiencies” ---
**Author:** ![Great\_Antibob](https://avatars.discourse-cdn.com/v4/letter/g/e47c2d/32.png) [@Great\_Antibob](https://boards.straightdope.com/u/Great_Antibob)\ **Post date:** [August 30, 2022, 6:33pm UTC](https://boards.straightdope.com/t/coin-flipper-club-puzzle/970613/5 "2022-08-30T18:33:57Z")
Ok, did some digging, and as confirmed, the more overlaps within the sequence, the worse off you are. So, the constant T or H sequences are absolutely the worst. The least subsequent overlaps, the better. So, something like T-H-H-H-H is about as good as you can do. And certainly not unique. There are several that are equally good. ---
**Author:** ![Cheesesteak](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/cheesesteak/32/3694_2.png) [@Cheesesteak](https://boards.straightdope.com/u/Cheesesteak)\ **Post date:** [August 30, 2022, 6:34pm UTC](https://boards.straightdope.com/t/coin-flipper-club-puzzle/970613/6 "2022-08-30T18:34:53Z")
I would think that THHHH would be the best, as it essentially takes the 5 flip requirement and turns it into a 4 flip once you get a single Tails throw. After that first Tails, anytime you fail, the requirement is 4 Heads in a row. I found that THTTH has the situation if you miss on the 4th flip, you have TH locked in, so it’s only 3 left to get, but that’s only if you miss on the 4th. ---
**Author:** ![Biotop](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/biotop/32/321_2.png) [@Biotop](https://boards.straightdope.com/u/Biotop)\ **Post date:** [August 30, 2022, 6:51pm UTC](https://boards.straightdope.com/t/coin-flipper-club-puzzle/970613/7 "2022-08-30T18:51:28Z")
It’s an interesting puzzle because intuitively it seems like any sequence is just as likely as any other sequence to appear. You folks have done a good job explaining it because I was having problems wrapping my head around the solution. According to the puzzle author there are 10 optimal solutions. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [August 30, 2022, 7:48pm UTC](https://boards.straightdope.com/t/coin-flipper-club-puzzle/970613/8 "2022-08-30T19:48:36Z")
> [@Biotop](#): > > According to the puzzle author there are 10 optimal solutions. Is that right? We are looking for strings that do not match shifted copies of themselves. I started listing them, but may have screwed up: ```x HHHHT HHHTT HHTHT HHTTT HTHTT HTTTT THHHH THTHH TTHHH TTHTH TTTHH TTTTH ``` ---
**Author:** ![Pasta](https://avatars.discourse-cdn.com/v4/letter/p/ecccb3/32.png) [@Pasta](https://boards.straightdope.com/u/Pasta)\ **Post date:** [August 30, 2022, 8:31pm UTC](https://boards.straightdope.com/t/coin-flipper-club-puzzle/970613/9 "2022-08-30T20:31:45Z")
Here’s the output from a quick sim. Shown is the average number of flips needed, taken over 1M trials for each target string. I’ve grouped them into apparent blocks of equivalence. ```auto avg = 32 HTTTT 31.989 THTHH 31.993 TTHHH 31.994 TTTHH 31.998 TTHTH 32.000 HHTTT 32.001 HHHHT 32.002 THHHH 32.002 HHTHT 32.002 HHHTT 32.004 TTTTH 32.004 HTHTT 32.017 avg = 34 HHTTH 33.983 HHHTH 33.984 THHTT 33.988 HTTTH 33.991 TTHHT 34.001 THHHT 34.002 THTTT 34.003 TTTHT 34.004 HTHHH 34.005 HTTHH 34.013 avg = 36 THHTH 35.984 HTTHT 35.985 HTHHT 35.998 THTTH 36.005 avg=38 HHTHH 37.978 TTHTT 37.994 avg=42 THTHT 42.001 HTHTH 42.002 avg=62 HHHHH 61.997 TTTTT 62.000 ``` ---
**Author:** ![Hoopy\_Frood](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hoopy_frood/32/8452_2.png) [@Hoopy\_Frood](https://boards.straightdope.com/u/Hoopy_Frood)\ **Post date:** [August 31, 2022, 3:42am UTC](https://boards.straightdope.com/t/coin-flipper-club-puzzle/970613/10 "2022-08-31T03:42:20Z")
Peter Winkler of Dartmouth originated this puzzle. > **[Dues Process - Futility Closet](https://www.futilitycloset.com/2022/08/18/dues-process/)** > > A curious puzzle by Dartmouth mathematician Peter Winkler: You’ve just joined the Coin Flippers of America, and fittingly the amount of your dues will be decided by chance. You’ll name a head-tail sequence of length 5, and then a coin will be flipped... ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [August 31, 2022, 10:04am UTC](https://boards.straightdope.com/t/coin-flipper-club-puzzle/970613/11 "2022-08-31T10:04:30Z")
I clicked on that _Communications of the ACM_ link > **[Puzzled: Coin Flipping](https://cacm.acm.org/magazines/2013/11/169037-puzzled-coin-flipping/abstract)** > > Each of these puzzles involves coin flipping. Simple stuff, right? Not necessarily . . . though solutions will indeed be provided in next month's column. and it does not say anything about there being 10 solutions. Which makes sense; why would the guy not know how to solve his own puzzle which is a thin veneer over well-known simple combinatorics? ---
**Author:** ![Great\_Antibob](https://avatars.discourse-cdn.com/v4/letter/g/e47c2d/32.png) [@Great\_Antibob](https://boards.straightdope.com/u/Great_Antibob)\ **Post date:** [August 31, 2022, 12:23pm UTC](https://boards.straightdope.com/t/coin-flipper-club-puzzle/970613/12 "2022-08-31T12:23:46Z")
Looks like the solutions are given the following month where the part about 10 solutions was printed. But it seems like there should be 12, so that’s something to puzzle out. I’m guessing that part was an error.