Category Archives: The Riddler

Can You Win A Spelling Bee If You Know 99 Percent Of The Words?

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,3 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 Tom Hanrahan, a probability puzzle; or, a mini-lesson in surprising results:
You are playing your first ever game of “Ticket to Ride,” a board game in which players compete to lay down railroad while getting so competitive they risk ruining their marriages. At the start of the game, you are randomly dealt a set of three Destination Tickets out of a deck of 30 different tickets. Each reveals the two terminals you must connect with a railroad to receive points. During the game, you eventually pick up another set of three Destination Tickets, so you have now seen six of the 30 tickets in the game.
Later, because you enjoyed it so much, you and your friends play a second game. The ticket cards are all returned and reshuffled. Again, you are dealt a set of three tickets to begin play. Which is more likely: that you had seen at least one of these three tickets before, or that they were all new to you?
Submit your answer
Riddler Classic
From Steven Pratt, ordinal bee probability:
You are competing in a spelling bee alongside nine other contestants. You can each spell words perfectly from a certain portion of the dictionary but will misspell any word not in that portion of the book. Specifically, you have 99 percent of the dictionary down cold, and your opponents have 98 percent, 97 percent, 96 percent, and so on down to 90 percent memorized. The bee’s rules are simple: The contestants take turns spelling in some fixed order, which then restarts with the first surviving speller at the end of a round. Miss a word and you’re out, and the last speller standing wins. The bee words are chosen randomly from the dictionary.
First, say the contestants go in decreasing order of their knowledge, so that you go first. What are your chances of winning the spelling bee? Second, say the contestants go in increasing order of knowledge, so that you go last. What are your chances of winning now?
Submit your answer
Solution to last week’s Riddler Express
Congratulations to Eric O’Neill of Madison, Wisconsin, winner of last week’s Riddler Express!
Last week, we broke out the dice to play a century-old baseball simulation game called Our National Ball Game, wherein each roll of the dice corresponded to some baseball outcome: 2-6 was a foul out, 1-1 was a double, 6-6 was a home run, and so on — you can find the full list here. How closely does such a list and a bunch of dice throws simulate the modern iteration national pastime? Specifically, what was the average number of runs that would be scored in nine innings of dice play? What was the distribution of the runs scored?
Typically, Our National Ball Game is much higher scoring than real baseball, with about 30 runs scored per game (compared to about nine in the real sport).
This was a problem of meta-simulation: Whereas the dice game simulated real baseball, you were meant to simulate the dice game (probably using a computer to save time). Solvers Julian Gerez and Ricky Martinez did just that and blogged about their approach, finding, after 10,000 innings of play, that each “baseball team” scored about 15 runs per game, for a total of about 30 runs per game, according to the simulated distribution shown below.

The computer scientist Peter Norvig was also kind enough to share his code — after a million computer-simulated dice-simulated innings, he found an average of just over 15.1 runs per team, and was able to smooth out the distribution as shown below.

A million innings! Perhaps we’ve finally found a solution to baseball’s pace-of-play problem.
Solution to last week’s Riddler Classic
Congratulations to Tyler James Burch of Naperville, Illinois, winner of last week’s Riddler Classic!
High scoring baseball is fun and all, but let’s say you wanted your game to be more faithful to real baseball than raw excitement. How could you tweak the list of rules — the correspondence between dice rolls and baseball outcomes — to create a game that more closely matched the run distribution in real baseball?
Our winner this week, Tyler James Burch, proposed the following list of rules, which I propose to call Burchball.
(1, 1): triple
(2, 2): base on error
(3, 3): double play
(4, 4): home run
(5, 5): double
(6, 6): strike out
(1, 2): strike out
(1, 3): strike out
(1, 4): base on balls
(1, 5): single
(1, 6): single
(2, 3): fly out
(2, 4): fly out
(2, 5): fly out
(2, 6): fly out
(3, 4): fly out
(3, 5): fly out
(3, 6): strike out
(4, 5): single
(4, 6): base on balls
(5, 6): single
Again, the fidelity of this tweaked game can be measured with computer simulations. In this case, Burch says his game’s simulated scoring outcomes match real baseball quite closely, as shown his chart below, in which Burchball scores are compared to MLB data from last season.

Finally, solver Douglas Harris thought outside the cubes — and got a little theoretical. “There are approximately (6times 10^{23}) hydrogens in a pair of dice,” he wrote (and we, I hope understandably, did not verify). “The proton in the center of each hydrogen can be aligned either up or down relative to the Earth’s magnetic field. Hence, I actually have a (6times 10^{23}) bit random-number generator every time I roll the dice, allowing me to have an outcome table with more than (10^{{10}^{23}}) possibilities. I mapped a tiny fraction of this outcome table to every femtosecond of every baseball game ever played. After extensive simulations, I was able to conclusively conclude that Pedro was left in one pitch too long.”
Want more riddles?
Well, aren’t you lucky? There’s a whole book full of the best puzzles from this column and some never-before-seen head-scratchers. It’s called “The Riddler,” and it’s in stores now!
Want to submit a riddle?
Email me at [email protected]

Time For Some Abstract Math. Drink Up.

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,7 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.

Last weekend, hundreds of expert puzzle solvers descended on Cambridge, Massachusetts, for the 2019 MIT Mystery Hunt, and hundreds more solved remotely across the country. I attended and wrote about the Hunt last year; it’s one of the oldest and most complex puzzle competitions in the world — and basically a Riddler column come to life. I loved it so much that I’ve decided to make it an annual tradition to reprint a couple of the Hunt’s most Riddlery puzzles. This year’s were written by members of a puzzling superteam called Setec Astronomy, and they are set within the theme of this year’s Hunt: holidays. (There’s always a theme.)
Fair warning: These are very hard! And their setups are more arcane than those of the typical Riddler — in some cases you may go down a few dead ends before you even know what it is you’re trying to solve. When I finally solved a couple of Hunt puzzles last weekend, I felt like I was levitating out of my chair. The answer to each puzzle is an English word or phrase — you’ll know it when you’ve found it, I promise. The language preceding the puzzles is a very lightly edited version of what Hunt teams saw. It’s known in Hunt-speak as “flavor text” — it both describes the puzzles and offers clues as to how to begin solving. You can also find some solving resources on the Hunt’s website. If you need another hint, find me on Twitter.
Puzzle 1: Bubbly
Puzzle by Sami Casanova, art by Jesse Gelles
Ray and Blanche sit down with their jug of champagne to play a game of Bubbly. Blanche, as she always does, goes first. Blanche surveys the opening state with a smile …

… and pops bubble S.

Now it’s Ray’s turn, and he chooses to pop bubble H. Since it’s impossible to pop H without popping both A and E (which surround H), A and E are popped as a consequence.

It is Blanche’s turn again, and her move is to pop bubble T.

“You’ve got me — I resign,” says Ray. “If I pop I, you win with N as the last possible move. And if I pop N, you win with I.”
“Don’t worry,” says Blanche. “You never had a chance! I was guaranteed to win, as long as I started with bubbles E, N or S.”
“Congratulations!” says Ray. “Shall we play again?”
“I would, but it looks like we’re running low on champagne,” Blanche replies. “How about our new friend here sits in for me, and you two start while I get us a remedy for our champagne situation?”
What are your winning starting moves?

Submit your answer
Puzzle 2: State Machine
By Matt Gruskin
In Presidents Day Town, you come across an inscription commemorating our nation’s history:
Our Founding Fathers started this nation from nothing. Our values change over time, and after a number of generations we have finally eliminated all negativity.
-9 – ◐ + – ◳ + ▥ + ◉
-9 – ◪ + ◰
-8 – ▦ – ◔
-7 + ▲ + ▣ – ◫ + ◲ – △ – ⌘
-6 – ◭ + ◩ + ▩ + ◈ + ◆ – ◑ – ◲ – △
-6 + ◵ – ◇
-6 – ◴ + ◆ – ▼ – ◒ +
-5 – ◵ – ◇ + ■ + ◒ – ◷
-5 – ◵ + ◁ – ● + ○ – ◷
-5 + ▩ + ◍ + ◶ – ◑ + ◓ – ▧
-4 + ◭ + ▣ – ⌘
-3 + ◕ + ▽ – ◔ + ◮ + △
-3 + + ◫ – ◑ – ◲
-3 + ▤ – ◒ + □ +
-3 + ◁
-1 – ◭ + ▲ + ▥ + ◲
-1 + ◩ – ◆ + ▼ – ▷
-1 – ◆ + ◨ – ▷ + ◒ + □
+0 + ◕ + ◭ + ▦ – ◆ + ▣ + ◫ + ◔ + □
+0 + ◧ + – ◪ – ◳ – ▥ – ▧
+0 + ▽ + ▦ + ▣ + △
+0 + ▦ + ◮ – △ – □
+0 – ◩ + ◴ – ◫ – ▷ + △ + □ –
+0 – ◴ – ▷ – ▨
+0 + ◶ – ◳ – ◰ – ◉ + ✮ + ▧
+1 + ◕ – ◭ – ▲ + △
+1 – – ▩ + ◈ – ◫ + ◱ + ▧
+1 – ◩ + ▩ + ▼ – ◍
+2 + ◴ – ▩ – ◆ – ◫ – ▨
+2 – ◇ – ◁ + ●
+3 – ◧ – ◐ + ◪ – ◰ + ◉
+3 + ◧ + + ◲ + ⌘ + ◉
+3 + ◪ – ◓ – ◱ – ▧
+3 – ◆ – ◨ + ◔ – △ +
+3 + ◇ + ● – ○
+3 – ◍ + ◶ + ◱
+4 + ◧ – ◳ – ◰
+4 – ▩ + ◓ – ◱ – ▨
+4 + ◬ – ◇ + ◷
+4 + ◨ – ■ – ◒
+5 + ▤ + ◨ – ■ + ● – ▷ –
+6 + ▤ + ● – ◒
+8 – ◭ – + ◈ – ◫ – ▥ + ⌘
+8 + ◐ – ◪ – ◳ + ✮
+8 – – ◪ – ◶ + ◑ + ◱ + ◉
+9 – ◕ + ▦
+9 – ◧ + ◈ + ◑ – ▥ – ◲ – ◉ – ▧
+9 – ◩ – ◍ + ◫ + ◑ + ◱ – ▨
Submit your answer
Solution to the previous Riddler Express
Congratulations to Chuck Culman of Audubon, Pennsylvania, winner of last week’s Riddler Express!
Last week, you were staring at a two-character, seven-segment display, like the kind you might find on a microwave. You wondered, as one does: How many numbers can this screen show in a way that is not ambiguous if the display happens to be upside down? The number 81, for example, would not fit this criterion — if the display were upside down, the number would look like 18. The number 71, however, would be fine. It’d look something like 1L — not a number.
There are 100 total numbers the display could show — 00 through 99. Of those, 58 can be safely turned upside down without being ambiguous.
We could go through the list of two-digit numbers one by one — 100 isn’t that many. But we could also look for patterns. For starters, any two-digit number with a 3, 4 or 7 in it is safe — those digits don’t look like a digit anymore when they’re turned over. There are 51 numbers containing these digits, which solver Angelos Tzelepis helpfully illustrated.

Further, some digits look like themselves when turned upside down on such a display: 0, 1, 2, 5 and 8. So we can add “00,” “11,” “22,” “55” and “88” to our total, bringing us to 56. Finally, there are two digits that do look like other digits when turned upside down, but they look like each other: 6 and 9. Thus “69” and “96” still look like “69” and “96” when flipped. Adding those two to our total brings us to 58, our answer.
This puzzle’s submitter, Tyler Barron, plotted the share of numbers that were potentially confusing, both for our two-digit case and for larger displays.

This chart will prove very helpful in my daily life: For some reason, my microwave keeps flipping upside down, and there seems to be nothing I can do to stop it.
Solution to the previous Riddler Classic
Congratulations to Jim Ferry of Leesburg, Virginia, winner of last week’s Riddler Classic!
Last week took us to the world of crossword puzzles and their grids’ rules and conventions. Crossword grids are typically rotationally symmetric, meaning they look exactly the same if turned upside down. All words in the grid must be at least three letters long. All letters must appear in a “down” word and an “across” word. And there can be no “islands” of white squares — the grid must be completely interconnected. Given that a weekday puzzle is usually 15-by-15, how many possible crossword puzzle grids are there?
For starters, solver Laurent Lessard drew the 7-by-7 grids — all 397 of them.

Beautiful! But the numbers get very big very quickly from there as we approach a standard 15-by-15 puzzle. Tyler Barron shared his approach and code, which he used to generate about a thousand 10-by-10 grids. Our winner this week, Jim Ferry, found 40,575,832,476 valid 13-by-13 grids using a dynamic programming approach.
But the programmatic approaches ground to a halt after that and no one — myself included — was able to pin down the exact number of valid 15-by-15 crossword puzzle grids. “This turned out to be very difficult,” Tyler wrote. So it remains an open question! If you make progress, let me know, and we’ll be sure to feature your solution in a future column.
The good news for constructors — and for solvers like me — is that there are still many, many, many puzzles left to go. The XWord Info database, which collects New York Times crosswords and data about them, contains only about 25,000 puzzles. We have at least, oh, tens of trillions to go. Happy solving.
Want more riddles?
Well, aren’t you lucky? There’s a whole book full of the best puzzles from this column and some never-before-seen head-scratchers. It’s called “The Riddler,” and it’s in stores now!
Want to submit a riddle?
Email me at [email protected]

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]