So Your Archipelago Is Exploding. How Doomed Is Your Island?

🚨🚨🚨 “The Riddler” book is out now! It’s chock-full of the best puzzles from this column (and, fret not, their answers) and some riddles 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,30 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 Philip Ruo, a puzzle of pondering playing perfection:

The NFL season is in full swing, and only one undefeated team remains — the 6-0 Los Angeles Rams. In theory, though, given the current NFL scheduling scheme — or at least what Wikipedia says it is — what is the largest number of teams that could finish a regular season 16-0?

Submit your answer

Riddler Classic

From Ricky Jacobson and Ben Holtz, geological disaster looms beneath:

You live on the volcanic archipelago of Riddleria. The Riddlerian Islands are a 30-minute boat ride off the shores of the nearby mainland. Your archipelago is connected via a network of bridges, forming one unified community. In an effort to conserve resources, the ancient Riddlerians who built this network opted not to build bridges between any two islands that were already connected to the community otherwise. Hence, there is exactly one path from any one island to any other island.

One day, you feel the ground start to rumble — the islands’ volcanoes are stirring. You’re not sure whether any volcano is going to blow, but you and the rest of the Riddlerians flee the archipelago in rowboats bound for the mainland just to be safe. But as you leave, you look back and wonder what will become of your home.

Each island contains exactly one volcano. You know that if a volcano erupts, the subterranean pressure change will be so great that the volcano will collapse in on itself, causing its island — and any connected bridges — to crumble into the ocean. Remarkably, other islands will be spared unless their own volcanoes erupt. But if enough bridges go down, your once-unified archipelagic community could split into several smaller, disjointed communities.

If there were N islands in the archipelago originally and each volcano erupts independently with probability p, how many disjointed communities can you expect to find when you return? What value of p maximizes this number?

Submit your answer

Solution to last week’s Riddler Express

Congratulations to 👏 Sarry Al-Turk 👏 of Toronto, winner of last week’s Riddler Express!

Last week, you learned about a girl who loves to sing “The Unbirthday Song” to people — as one does. But she can only do that, of course, if it’s not the person’s actual birthday. If she kept singing it to random people until it happened to be someone’s birthday, how long would her singing streak go before it became more likely than not that she would encounter someone whose birthday it is?

Care for those vocal cords, child: It’s 252 people.

The probability that it’s not an individual person’s birthday is 364/365. The probability that you sing to N people in a row without it having been anyone’s birthday is \((364/365)^N\) — since the birthdays are independent events, we can multiply that fraction over and over to match the number of people. We want to find the number N such that that probability is larger than 0.5.

We could just stick that straight into a computer solver, but it’s Friday, so let’s have some fun and do a little algebra.31 First, we can take the logarithm of both sides, to get N out of the exponent, and then we can rearrange things a little bit:

\begin{equation*}(364/365)^N > 0.5\end{equation*}

\begin{equation*}N\log(364/365) > \log(0.5)\end{equation*}

\begin{equation*}N > \log(0.5)/\log(364/365)\end{equation*}

That numerator, log(0.5), equals about -0.3, and that denominator, log(364/365), equals about -0.001. That fraction equals about 253. So the singing streak is expected to go 252 people before it became more likely than not that a birthday boy or girl would be encountered.

And a very merry unbirthday to you, dear reader — unless, of course, it is the big day.

Solution to last week’s Riddler Classic

Congratulations to 👏 Clemens Fiedler 👏 of Krems, Austria, winner of last week’s Riddler Classic!

Last week, a farmer wanted to tether a goat — as one does. Specifically, the farmer wanted to tether the goat to the fence that surrounded his circular field such that the goat could graze on exactly half the field, by area. The field had a radius R. How long should the goat’s tether be?

The tether should be a bit longer than the radius — specifically, it should have a length of about 1.159R.

Solver Russell No-last-name-given showed us what this looks like, pictured below. The field is green with radius R; the goat’s would-be grazing area is gray, with radius r.

The picture is all fine and good, but what about that math? It looks a little nasty. And it is a little nasty, I’m afraid. But, hey, it’s nearly Halloween, so let’s surrender to the nastiness and fear.

The area on the field available to the goat is the intersection between two circles. And there just happens to be a whole body of knowledge about such circle-circle intersections. One way to think about it is to consider the two different shapes that the goat’s tether allows it to graze in. The first is the big “pizza slice”, defined in the image above by the two diagonal green radii and the bottom arc of the gray circle, and the second are the narrower areas between the pizza slice and the fence.

Hector Pefo broke this math down a little bit more for us in his diagram (this time, the goat is on the southern end of the field):

And finally, Laurent Lessard showed us a way to get to this same solution with calculus.

Either way, I hope you enjoy it, goat. Nom nom nom.

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?

🚨🚨🚨 “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 \(4\cdot 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 \(4\cdot 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]