Category Archives: The Riddler

How Far Would You Go To Rig A Coin Flip?

Category : The Riddler

Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. There are two types: Riddler Express for those of you who want something bite-size and Riddler Classic for those of you in the slow-puzzle movement. Submit a correct answer for either,6 and you may get a shoutout in next week’s column. If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter.

Riddler Express
From Justin Bernstein, when all you have is a coin, all you can do is flip:
Coin flips are a handy way to determine a winner — if the goal is to give two people an equal chance of winning. But sometimes it’s not. Suppose Anna and Barry aren’t interested in equity. All they have is a fair coin marked heads and tails. How can they devise a game that gives Anna a 1 in 3 chance of winning? What about a 1 in 4 chance? What about a 1 in 5 chance?
Submit your answer
Riddler Classic
From Jim Crimmins, a puzzle that may or may not be topical. There’s something happening next week, I think — I just can’t seem to remember what it is …
You are the elections analyst for Riddler Nation’s wildly successful data-driven political blog, OneHundred. The annual election is coming up, and all 100 Riddler Nation Senate seats are up for grabs. There are two parties in Riddler Nation: the Theorists and the Programmers.
Elections in Riddler Nation work a bit differently than those in other countries. Here, a virtual coin is flipped for each seat — the Programmers win on heads, while the Theorists win on tails. Remarkably, the founders of Riddler Nation allowed for a political party to write the program that does the flipping. (Conflicts of interest were not high on the founders’ list of things to worry about.) Although the Programmers do the programming of the virtual coin, the Theorists do have one recourse, though — they have the right to challenge the results if they think that something is fishy.
The Theorists can’t code and are generally suspicious of the Programmers. So they collect complete data (the flip results) for each seat after every election. Election data and challenges go to the Riddler Nation Statistical Court, composed of learned and honest statisticians. The Theorists’ challenges have no statute of limitations — a 100-year-old election can be part of their case, if need be.
Here are your questions, elections analyst:

If the Programmers don’t cheat and the virtual coin is fair, what is the probability that one party will win a simple majority in the Senate? What is the probability that one party will win a supermajority of 60 seats?
If the Programmers decide to cheat this year by weighting the virtual coin in their favor, what weighting would give them a 50 percent chance of winning a 60-seat supermajority? How often can they do this periodic, annual 50-percent weighting before the Theorists can prove to the Statistical Court that there’s at least a 99 percent chance that the coin wasn’t fair?
If the Programmers decide to cheat by weighting the coin permanently for the next 100 elections, how heavily can they weight it and escape a successful 99 percent challenge by the Theorists and detection by the court? How many 60-seat supermajorities can they expect to win over this 100-year period?
What is the optimal cheating strategy for the Programmers to perpetually escape a successful 99 percent statistical challenge and maximize the number of expected supermajorities? (Assume that if a successful challenge is made, the Programmer party is banished from Riddler Nation.)
Does changing the coin weighting on a seat-by-seat basis in an individual election help improve the Programmers’ odds in any of these scenarios?

Submit your answer
Solution to last week’s Riddler Express
Congratulations to Jon and Lisa of Columbus, Ohio, (and their trap “Boom!”). They’re the new Chief-Arch-Super-Villain Engineers Extraordinaires of Riddler Nation!
Last week brought a participatory, game theoretic and cinematic engineering game. You and your two roommates were villainous engineers with a specialty in engineering traps to catch James Bond. You each designed and named your own trap, specifically choosing its effectiveness — the percentage of the time the trap would capture Bond if he tried to get past it. Your three traps were then placed in a lair — in increasing order of effectiveness — and your goal was to be the one whose trap captured Bond. So, while a 99 percent effective trap might’ve sounded great, it was also likely to be placed last in line, and Bond might have already been captured by the time he got to it. So the engineering challenge was really a trade-off between getting to Bond as early as possible and having a better chance at nabbing 007.
I received 1,211 trap submissions over the past weekend. I then simulated 1 million groups of villainous roommate trios, properly ordering the three traps in each lair and keeping track of whose trap was the one that captured Bond as he entered and tried to get safely through the lair. Here’s how those trap submissions broke down:

Very roughly speaking, your submissions were normally distributed and centered around 50 percent. But a few rough values of effectiveness were especially popular, which you can see in the tall spikes in the distribution above: one-third, one-half, two-thirds and 100 percent.
But that’s just trivia. We have debonair spies to catch. The magic number to do that appeared to be somewhere between 45 percent and 47 percent. Here are the top 10 trappers and their traps7:

The top 10 James Bond trappers
Based on 1 million simulations using 1,211 user submissions

Trap effectiveness
Avg. Bonds trapped

Jon and Lisa
Columbus, Ohio


Aaron Zinger
Brooklyn, New York


Ib Jørgensen
Frederiksværk, Denmark


Sean Floyd
San Francisco

The Goldenface 3000



Ben Knox
Madison, Wisconsin

Mayor Humdinger’s Kittens

Adam Harter
Morristown, New Jersey


Sampsa Lahtonen
Rusko, Finland

Santa’s Ultimate Prohibitively Expensive Raptor-Balrog-Orc-Naga-Dragon-Yeti-Impossibly-Evil-Lich Dropper

Katie Fitzpatrick
Brooklyn, New York

Super Dull Somewhat Vaguely Effective Net

Chuck Coleman
Alexandria, Virginia

C’s First Feigenbaum Constant * 10 Trap

Brooklyn in the house! And Ohio, too. And Denmark and Finland. Our Ohioan winners explained their trap decision this way: They wanted to “beat 50 percent and really low [submissions], and break even with [those who submitted] 100 percent.”
Indeed, beating the many traps clustered around 50 percent seems to have been the key to successful super-villainous engineering. Traps around 46 percent, for example, were unambitious enough to come before many other traps in the lair’s trap queue, but effective enough to capture Bond pretty often when he passed by.
How do the best levels of effectiveness translate into Bonds-caught-per-lair? If all traps were calibrated to be perfectly effective, every villainous roommate would capture an average of one-third (0.333…) of a James Bond per lair — it’d just be a lottery as to whose net did the capturing.
That number can help us set a baseline for spy-capturing performance. The best-calibrated traps in this game were able to do even better (although not dramatically better) than that, with our winners nabbing about 0.35 of a Bond — or more than their “fair” share — per lair. Here is how a trap effectiveness translated into Bonds caught:

All 1,211 of these traps were constructed with the goal of being the one to nab Bond. But this villainous selfishness is very beneficial for Bond himself, of course. If you and your villain roommates were working together, laying down three maximally effective traps, Bond would never escape the lair. But given your desire that your trap, and not those of your roommates, be the decisive capturing trap and your resulting strategizing thereabout, Bond escaped your collective lairs unscathed about 11 percent of the time.
Solution to last week’s Riddler Classic
Congratulations to Linus Hamilton of Hyattsville, Maryland, winner of last week’s Riddler Classic!
Last week, you were an avid card player who had developed a very specific organizational tic at the table. Every time you were dealt a hand of cards, you wanted to sort it in a specific way using a single motion. By moving just one block of cards from one position in your randomly dealt hand to another, you wanted your hand organized such that the cards of each suit were all together and that, if possible, no suits of the same color were adjacent to each other. If you’re dealt a hand of six cards, what are the chances that you’ll be actually able to realize your organizational obsession? What if you’re dealt a hand of N cards?
With six cards, the chances are around 61 percent. As the number of cards increases, your chances decrease dramatically.
Given the enormous number of ways hands of cards can be dealt and the gnarly combinatorial math that results, this is a natural programming problem. Our winner, Linus, explained his thinking this way: “It would take forever to iterate through all possible hands of six cards (there are over 14 billion). But it’s fast to iterate through all 4,096 sequences of six suits, compute the probability of receiving that sequence, and then check whether it can be well-scrambled with one move. I used a Python program to do this.”
Solvers Matt Wade and Keith Hudson also programmed their way to 61 percent. Matt was kind enough to share his work and handy interactive animation, and Keith shared his code and explained the intuition behind his programmatic approach like so:
Step 1: Find all the different ways you could permute a hand of cards by grabbing a contiguous block of them and moving them somewhere else in the hand. For six cards, there are 36 ways; for 13 cards, there are 365.
Step 2: Figure out how to recognize an acceptable hand. I defined a hand’s “fingerprint” as the order of suited groups — for example, a hand with spade, club, diamond, diamond, club and heart in that order would have the fingerprint “scdch.” I figured out an acceptable hand would have one of the following 32 fingerprints: s, h, d, c, sh, sd, sc, hs, hd, hc, ds, dh, dc, cs, ch, cd, shc, sdc, hsd, hcd, dsh, dch, chs, cds, shcd, sdch, hsdc, hcds, dshc, dchs, chsd or cdsh.
Step 3: See if some rearrangement of a hand results in a good fingerprint. For example, for the hand mentioned above — “scddch” — taking the third through fifth cards and moving them after the first card gives one of the good fingerprints: sdch. This step is essentially just looking at each possible rearrangement and seeing if it’s in the list of “good” fingerprints.
Step 4: Figure out how likely it is for a specific arrangement of cards to appear in a deal from a real deck.
Solver Laurent Lessard graphed these chances for hands of various sizes. With one (obviously), two (obviously), three (sort of obviously) or even four cards, you can always scratch your organizational itch. Beyond that, the odds fall off sharply. If you were playing bridge, say, where you have a hand of 13 cards, you’d be able to accomplish your goal with one move only about 0.3 percent of the time.

But this problem is so contrived, dear Dr. Riddler Editor, an overly arbitrary mathematical exercise meant solely to steal away my Friday. I can practically hear you yelling that at your screen. But au contraire, mon frère ou ma sœur. To wit, solver Daniel Kunigan filed this report:
“I don’t know the answer. I just wanted to say this is word-for-word exactly what I do when I receive my hand in any card game. More than one move just makes it look like I have a lot of variety to organize, and I don’t want to give away anything. But separating by suit is just so satisfying! Anyway, I’ll guess a random number like 39 [percent].”
Not bad, Daniel. Not bad at all.
Want more riddles?
Well, aren’t you lucky? There’s a whole book full of the best of them and some never seen before, called “The Riddler,” and it’s in stores now!
Want to submit a riddle?
Email me at [email protected]

So You Want To Tether Your Goat. Now What?

Category : Animals , The Riddler

“The Riddler” book is out now! It’s chock-full of the best puzzles from this column (and, fret not, their answers) and some that have never been seen before. I hope you enjoy it, and thank you for riddling with us these past three years.
Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. There are two types: Riddler Express for those of you who want something bite-size and Riddler Classic for those of you in the slow-puzzle movement. Submit a correct answer for either,4 and you may get a shoutout in next week’s column. If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter.

Riddler Express
From Luke Robinson, a serenading stumper:
My daughter really likes to hear me sing “The Unbirthday Song” from “Alice in Wonderland” to her. She also likes to sing it to other people. Obviously, the odds of my being able to sing it to her on any random day5 are 364 in 365, because I cannot sing it on her birthday. The question is, though, how many random people would she expect to be able to sing it to on any given day before it became more likely than not that she would encounter someone whose birthday it is? In other words, what is the expected length of her singing streak?
Submit your answer
Riddler Classic
From Moritz Hesse, some grazing geometry:
A farmer owns a circular field with radius R. If he ties up his goat to the fence that runs along the edge of the field, how long does the goat’s tether need to be so that the goat can graze on exactly half of the field, by area?
(The great thing about this puzzle, Moritz notes, is that if you get sick of math, you can find the answer through trial and error with your own circular field and your favorite goat, horse, cow, kangaroo, sheep, unicorn, centaur or sphinx.)
Submit your answer
Solution to last week’s Riddler Express
Congratulations to Stefan Heidekrüger of Munich, winner of last week’s Riddler Express!
Last week’s Express brought a fill-in-the-blank challenge: What’s the next number in this series?
9, 10, 19, 24, 31, 40, 51, 64, 79, 90, ?
It’s A9.
A9?! What the … ?
The trick to filling in this blank was recognizing that these numbers aren’t in our usual base-10, or decimal, number system. Rather they are in the base-16, or hexadecimal, system. Hexadecimal is often used by computer programmers. And since we only have 10 digits that go with our usual base-10 system, base-16 uses the letters A through F to represent the values 10 through 15.
OK, back to our series. The pattern is ((N+2)^2), where (N) is the number’s position in the sequence. So the first number is (3^2), or 9. The second number is (4^2), or 16, which is represented as 10 in hexadecimal. The third number is (5^2), or 25, which is 19 in hexadecimal. And so on. Our missing number is (13^2), or 169 — or A9 in hexadecimal.
Solution to last week’s Riddler Classic
Congratulations to Eric Roshan-Eisner of San Francisco, winner of last week’s Riddler Classic!
Last week you were brought in to solve a serious problem at the Riddler Intelligence Agency, or RIA. Namely, the RIA had been infiltrated by spies, and your job was to root them out. There were N agents total, and K of them were spies. You knew the values of N and K but not, at first, the identities of the spies. You could send any number of agents on a remote island retreat as many times as you wanted. If all of the spies were on the retreat, they would assemble for a secret spy meeting; if any of the spies were not on the retreat, the meeting would not take place. The only thing you learned from each retreat was whether or not this meeting happened.
It cost $1,000 per person to send agents on these retreats. What was the least you could spend while still identifying all of the spies? Assume you knew that N = 1,024 agents and K = 17 spies.
This week’s winner, Eric Roshan-Eisner, explained that it will take at least 122 retreats to identify all the spies: The total number of possible spy configurations within those 1,024 people is N choose K, or about (4cdot 10^{36}). That number is very big — but it doesn’t mean we need that many retreats to suss out our spies.
Think of each retreat as a moment to learn one bit of information about the arrangement of spies (that is, whether or not the spy meeting occurred). I’m using “bit” there intentionally — the key to solving this puzzle is to translate that (4cdot 10^{36}) number into binary, a number that needs 122 “bits” — one digit in a binary number — to be expressed. Every retreat you organize returns to you exactly one piece of yes-or-no, 0-or-1 information — that is, whether or not the spy meeting happened. That’s your bit. Therefore, the minimum number of retreats necessary to differentiate between all four undecillion possibilities is 122. The exact strategy you should use to do this, Eric wrote, is left as an exercise to the reader.
Others picked up the baton there. Tim Black, a grad student at the University of Chicago (Go Maroons!), found a strategy to identify the spies in 131 retreats, and also proved that it is impossible to do so in fewer than 122.
Thomas Swayze also found a 131-retreat strategy, which cost about $93 million. Thomas wrote that his strategy to find the spies was to use a form of binary search to single them out one by one: Start with some subset, S, of the agents that we know contains at least one spy. Then pick a subset, T, of S, and keep the agents in T at home while sending the entire rest of the agency on the retreat. If there’s a meeting, we know that T contains no spy — so leave all the agents in T out of all future retreats. If there is no meeting, there is some spy in T. Either way, we now have a smaller set that we know has a spy. Once we’ve outed one spy, we send him on all future retreats and repeat the process to find all the remaining spies, one by one. The tricky part is deciding how big to make the set T. It depends on the number of agents left, the number of spies we’ve caught, and the size of the set S. Thomas was kind enough to share the Python code he used.
Finally, Laurent Lessard described a strategy that used more retreats (191) but cost less (about $66 million).
But hey, if identifying spies were easy — or cheap — everybody would do it.
Want to submit a riddle?
Email me at [email protected]