What The Heck Are These Dang Bits?

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,10 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 James Anderson, in which you unwrap your presents and they are promptly eaten:

For Christmas, you received a 20-volume encyclopedia (thanks, Mom) that now sits on your shelf in numerical order. Each volume is 2 centimeters thick and bound with a 2-millimeter thick hardcover. If an ambitious bookworm wriggles into Volume 1 and eats straight from Page 1 of that book to the last page of Volume 20, how far has it traveled?

Submit your answer

Riddler Classic

From Jordan Ellenberg, an author and mathematician at the University of Wisconsin, so simple yet so hard:

What are these bits?

Jordan shared this puzzle previously with some folks, and has this preliminary report for Riddler Nation: “To my amazement, three people figured it out — all mathematicians, but that partially reflects who’s on my feed, and the solution is actually in some sense elementary.”

I’ve got a hunch Riddler Nation will add significantly to that total.

Submit your answer

Solution to the previous Riddler Express

Congratulations to 👏 Tracy Hall 👏 of Provo, Utah, winner of the previous Riddler Express!

Two weeks ago, we learned that Santa Claus’ memory was faltering. It was faltering so much, in fact, that he’d forgotten the order in which his eight reindeer were meant to be harnessed to his sleigh. The reindeers themselves remembered where they were supposed to go, but, being animals, could only give out a grunt of approval if they were harnessed in the right position. Santa decided on the following strategy to get everybody hooked up correctly: He created a list of all eight reindeer in random order. He then went to the first location, harnessing the reindeer one by one off his list until one grunted, then moving on to the next location and starting over at the top of his list. Each harnessing took one minute. How long on average would we expect it to take before all the reindeer are correctly harnessed and Santa can get to work delivering presents?

It would take 22 minutes on average.

Because the initial list of reindeer is random, it is equally likely that any of Santa’s attempts to harness the reindeer in the first location is correct. Therefore, to harness the first animal would take an average of (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8) / 8 = 4.5 minutes. Similarly, to harness the second would take an average of (1 + 2 + 3 + 4 + 5 + 6 + 7) / 7 = 4 minutes, and so on. That’s a total of 4.5 + 4 + 3.5 + 3 + 2.5 + 2 + 1.5 + 1 = 22 minutes.

Santa could, of course, get really lucky with his random list, and get each one right on the first try for a total of eight minutes of harnessing. Or he could get really unlucky, taking the maximum amount of time with each reindeer for a total of 36 minutes of harnessing. More likely, it would be somewhere in between. This puzzle’s submitter, Taylor Firman, provided the following chart of the distribution of possible reindeer-harnessing times that Santa could face:

Good luck with your draw from that probability distribution, big jolly guy. We’re counting on you.

Solution to the previous Riddler Classic

Congratulations to 👏 David Mattingly 👏 of Old Forge, Pennsylvania, winner of the previous Riddler Classic!

Two weeks ago, we also traveled to Santa’s workshop in which elves worked shifts building toys. During these shifts, Christmas music played on an overhead speaker, with songs chosen by a program at random from a large playlist. Every time he heard a song twice, a cranky elf named Cranky started throwing snowballs at everyone. This happened during about half of all shifts. During a shift, the elves hear 100 total songs. How large is Santa’s playlist?

It contains 7,175 songs.

This puzzle is quite similar to the birthday problem — which is concerned with the chances that some two people in a group share a birthday — with an unknown number of days in a year, or songs on the playlist, in our case. So instead of 365 days and a 50 percent chance of a birthday match in a group of 23 people, we have an unknown number of songs and a 50 percent chance of a match in a group of 100 songs.

Let’s say there are X songs on the playlist. The chance of there not being a repeated song during a 100-song shift, a familiar equation from the birthday problem, is:\(\)

\begin{equation*}\frac{X!}{X^{100}(X-100)!}\end{equation*}

So the chance of there being a match is 1 minus that. That expression equals 0.5 right around when X = 7,175. Solver Hernando Cortina created the chart below using many elf shift simulations, and it shows how the probability of hearing a repeat song decreases as the playlist becomes larger. The probability hits our 50 percent mark very near 7,175 songs.

One of the founders of the music service Pandora, Joe Kennedy, wrote in to say the “situation the problem highlights is actually very real.” [Editor’s note: Ah yes, The Riddler, that staunch bastion of realism!] “For the many people whose favorite Christmas song is ‘All I Want for Christmas Is You,’ there just aren’t 7,174 other Christmas songs like it. And 100 Christmas songs typically only represent five to six hours of listening — less than a day’s effort in Santa’s workshop!”

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]

Santa Needs Some Help With Math

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.

Programming note: The Riddler will be taking next week off for the holidays. If you’re jonesing for more puzzles as you snuggle around the fire roasting chestnuts and stuff, might I humbly suggest “The Riddler” book? It makes a great gift, too. Also good kindling for that fire, in a pinch, I imagine. (The publisher only cares that you buy it, not what you do with it.)

Riddler Express

From Taylor Firman, dash away, dash away, dash away all:

Santa Claus is getting up there in age, and his memory has begun to falter. (After all, why do you think he keeps a list?) It’s gotten so bad that this year Santa forgot what order to put the reindeer in. Obviously, he remembers that Rudolph goes first because of the red organic light bulb in the middle of his face, but big guy just can’t remember what to do with the other eight.

If he doesn’t get the right order, the aerodynamics of his sleigh will be all wrong and he won’t be able to get all of his deliveries done in time. Yes, Santa has Moneyballed Christmas Eve. Luckily, the reindeer know where they should each be, but since they’re just animals they can only grunt in approval if they are put in the right spot.

Determined to get it right, Santa first creates a list of the reindeer in some random order. He then goes to the first position and harnesses each reindeer one by one, starting at the top of his list. When a reindeer grunts, Santa leaves it in that correct position, moves onto the next position, and works down that same list once again.

If harnessing a reindeer into any spot takes one minute, how long on average would it take Santa to get the correct reindeer placement?

Extra credit: Is there a strategy that Santa could use that does better?

Submit your answer

Riddler Classic

From Steven Pratt, the best way to spread Christmas cheer is singing loud for all to hear:

In Santa’s workshop, elves make toys during a shift each day. On the overhead radio, Christmas music plays, with a program randomly selecting songs from a large playlist.

During any given shift, the elves hear 100 songs. A cranky elf named Cranky has taken to throwing snowballs at everyone if he hears the same song twice. This has happened during about half of the shifts. One day, a mathematically inclined elf named Mathy tires of Cranky’s sodden outbursts. So Mathy decides to use what he knows to figure out how large Santa’s playlist actually is.

Help Mathy out: How large is Santa’s playlist?

Submit your answer

Solution to the previous Riddler Express

Congratulations to 👏 David Kravitz 👏 of Santa Monica, California, winner of last week’s Riddler Express!

Last week we returned to that timeless classic, tic-tac-toe. The Express challenge was straightforward, but far from trivial: Chess buffs, for example, like to point out that there are more possible chess games than there are atoms in the universe. Big whoop. How many possible games of tic-tac-toe are there?

There are 255,168 — it may not be the number of atoms in the universe, but it’s more than enough to keep you occupied with your families over the holidays. Warning (mostly to my editor): Lots of very specific counting ahead.

How do we get there? Let’s start with a deep breath. And then let’s establish an upper bound on the number we’re looking for. There are nine squares from which the first player can choose, then eight for the second player, then seven for the first, then six for the second and so on. Multiplying those possible moves means that there are at most 9!, or 362,880, possible games. It’s a decent approximation, but it’s overcounting. Some of those “games,” for example, would have ended with a win for one player before all nine moves were made. So let’s begin a more careful accounting by looking at how many possibilities there are for a game to end after each move.

The soonest a game could end is after the fifth move — three moves for one player and two for the other. There are eight places in which the first player could win: the three rows, the three columns and the two diagonals. There are six places and then five places where the second player could play — those places not in the winning locations. So there are 8*3!*6*5 = 1,440 ways the game could end this quickly.

What about after the sixth move? The second player wins in this case, and there are again eight places to do that — and six, five and four places the first player could go that wouldn’t interrupt that win. So that’s 8*3!*6*5*4 = 5,760 possibilities. However, we need to subtract off a few of those in which the first player would have won before the second player could. That is, we need to exclude the cases where there are three Os and three Xs in a row. That can only happen horizontally or vertically (i.e., not diagonally). So the first player could take one of six “winning” locations, leaving one of two “winning” locations for the second player. That’s 6*3!*2*3! = 432 possibilities we need to omit, leaving 5,760 – 432 = 5,328 games that end after the sixth move.

And the seventh? The first player wins in this case, of course. Again, there are eight winning locations, but there’s a wrinkle here: The first player can’t win too soon. That is, one of his plays must not be on the winning line. It must go in one of the six non-winning locations during one of three turns in the game. The second player, meanwhile, has five then four then three spots in which to play fruitlessly. That gives 8*3!*3*6*5*4*3 = 51,840 possibilities. But, again, we have to subtract off those in which both players would have already lined up three in a row by the seventh move. (Accounting is hard!) Just as before, this can’t happen in a diagonal, leaving six winning lines for the first player. The first player’s “wasted” move, which happens at one of three points in the game and in one of six squares, will take out another of those, leaving just one winning line for the second player. So there are 6*3!*1*3!*3*6 = 3,888 ways that might happen, leaving 51,840 – 3,888 = 47,952 games ending on this turn.

And the eighth? (We’re nearly there, I promise.) Here, the second player wins and, once again, there are possible eight winning lines. Similar to before, the first (losing) player can go in five then four then three then two spots, while the second (winning) player fills in his winning line in some order, and “wastes” a move in one of six squares at one of three points. That’s 5*4*3*2*8*3!*6*3 = 103,680 possibilities. But — you guessed it — we have to toss out some of those wherein both players would have lined up their three marks. That can’t happen in a diagonal, so there are six places for one player and two left over for the other, one of which will be taken by that first players “wasted” move, which he can “waste” at one of four points in the game. That’s 3!*2*4*6*3!*6*3 = 31,104 games to toss out, leaving 103,680 – 31,104 = 72,576 games that end on Move 8.

And the ninth? Well, we don’t really need to do this one in full — phew! Rather, because we already calculated the total number of ways to fill in all the boxes over nine moves at the very top of this solution, we can subtract off all the games we just calculated, which end before that. Say the game ended after the fifth move. Then there would be 4! ways to fill in the rest of the boxes for no reason after that. If it ended after six moves, there’d be 3! Ways, and so on, so we have to account for those too. That gives us 362,880 – 4!*(1,440) – 3!*(5,328) – 2!*(47,952) – 1!*(72,576) = 127,872 games that end only after the ninth and last possible move.

Aaaaaand: 1,440 + 5,328 + 47,952 + 72,576 + 127,872 = 255,168. I’ll spare you the details, but, despite real-world experience, only about 18 percent of the possible tic-tac-toe games are draws.

Our winner David wrote: “I wrote a brute force program to find all of them, ran in less than a second.” Damn it, David. That was a really good idea.

And if you’re bored with boring old vanilla tic-tac-toe but have also read this far, might I suggest the fantastically interesting (I’m serious) Ultimate Tic-Tac-Toe, instead? Just bring a paper and a pen and you’re sure to be the hit of your office party.

Solution to the previous Riddler Classic

Congratulations to 👏 Josh Degler 👏 of Lighthouse Point, Florida, winner of last week’s Riddler Classic!

Last week’s Classic tic-tac-toe challenge was less accounting and more strategy. You were playing a game of tic-tac-toe with one advantage (you went first) and one disadvantage (you were blindfolded). The squares on the board were numbered 1 to 9, and you made your move by calling out a number, unaware of what moves your opponent had chosen to make. (If a numbered square you chose was taken, you were told so and could then pick a different number.) Could you develop a strategy that would guarantee you’d never lose a game, despite the blindfold?

Yes, indeed you could! And there was more than one strategy that did the trick.

As a reminder, the game squares were labeled like so:\(\)

\begin{matrix}\nonumber 1&2&3\\4& 5 &6\\7 &8& 9\end{matrix}

Solver Justin submitted the following diagrammatic solution where you start with 5 (the center square) and keep trying to move down the left-most branch. If you can’t move down that branch because that square is already taken, you try the square on the next branch to the right, and so on. Green circles mean you won, and blue circles mean you tied. (Cat’s game, we used to call it.) You never lose!

Solver Barry King submitted another solution, in which you start with a corner square. Same rules (go down the left branch whenever possible) apply:

Finally, solver Kenny Long submitted a solution where you start with a non-corner, non-center square. Start with 2 and then move right, if you can, or else move down.

Another cool party trick. Boy, you’re really gonna win friends and influence people with these tic-tac-toe skills!

Have a great holiday — see you in 2019.

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! Consider your holiday shopping done.

Want to submit a riddle?

Email me at [email protected]

Can You Win Tic-Tac-Toe Blindfolded?

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

Chess fans like to crow that there are more possible games of chess than there are atoms in the universe. Well la di da. What about us tic-tac-toe devotees? How many possible games of tic-tac-toe are there for us?

Submit your answer

Riddler Classic

From Tom Hanrahan, a twist on the classic:

You are about to play a game of tic-tac-toe, with one advantage and one big disadvantage. The advantage is you get to go first. The disadvantage is you are blindfolded and therefore not informed of your opponent’s moves.

It works as follows. The squares of the board are numbered 1 through 9, like so:

\begin{matrix}\nonumber 1&2&3\\4& 5 &6\\7 &8& 9\end{matrix}

You go first, calling out a number corresponding to the square in which you would like your “X” to be placed. Your opponent then chooses a square for her “O,” but you don’t know which. You continue like this, alternating turns. Whenever you choose a square that is already occupied by your opponent, you are informed that the square is occupied, and you must then choose another one until you find an empty square.

Can you devise a strategy where (just like in regular tic-tac-toe!) you are guaranteed never to lose?

Submit your answer

Solution to the previous Riddler Express

Congratulations to 👏 Harry Posner 👏 of Boston, winner of last week’s Riddler Express!

Last week we met Louie, who lived in a town that had a 50 percent chance of rain each morning and an independent 40 percent chance each evening. Louie walked to and from work each day, bringing an umbrella with him if it was raining and not bringing one if it wasn’t. On Sunday night, two of his three umbrellas were with him at home and one was at his office. What were the chances that he made it through the work week without getting wet?

The chances of Louie staying nice and dry were exactly 69.27 percent.

This puzzle’s submitter, Josh Vandenham, suggested three ways to get to the answer. The first is to proceed by brute force through all of the possible weather patterns, keeping track of Louie’s umbrellas in each case. There are two relevant times of day, for five days, and two things can happen at each of those points (rain or shine), therefore there are \(2^{10}=1,024\) possible weather patterns. That’s a lot, sure, but not totally impossible.

The second is to pare down the possibilities and just keep track of the different “states” of Louie’s umbrellas. He could have three at home and zero at work, two at home and one at work, one at home and two at work, or zero at home and three at work. Just four states, which isn’t too complicated. We can see the probability of each state in this glimpse of the spreadsheet of solver Nate Langhinrichs.

By the the time Louie arrives home on Friday night, there is a 30.73 percent chance he has gotten caught out in the rain, sans umbrella, or a 69.27 percent he’s stayed dry.

The third way to solve is to generate some computer-simulated meteorology and commutes. Solver Lowell Vaughn, for example, took this approach and was kind enough to share his Python code.

Finally, yet another way to approach this problem would be with something called Markov chains — models of random events, which use some fancy linear algebra stuff like matrices. In this approach, the state of affairs (the umbrellas) depends on the state of affairs that came before. This approach was used to great effect by solver Aaron Cote. The movement through the random states (the work week) is described by a transition matrix, which contains the probabilities of umbrellas moving from one place to another on any given day. In our particular case, the matrix looks like this:

\begin{pmatrix}\nonumber 0.3 &0.2 &0.0 &0.0 &0.5\\
0.3 &0.5 &0.2 &0.0& 0.0\\
0.0 &0.3 &0.5 &0.2& 0.0\\
0.0 &0.0 &0.3 &0.5 &0.2\\
0.0 &0.0 &0.0 &0.0 &1.0\end{pmatrix}

In this solution, there are five states: zero, one, two or three umbrellas at home plus the state in which Louie has already gotten wet. The rows of the matrix are Louie’s current state, and the columns are his destination. For example, he starts in the third row (two umbrellas at home). There is no chance he’ll end up with zero umbrellas at home, there’s a 0.3 chance he’ll end the day with just one at home, a 0.5 chance with two at home, a 0.2 chance with three at home, and no chance he’ll get wet on this first day. To get the probabilities for the entire work week, we simply multiply this matrix by itself five times, representing the meteorological randomness unfolding over the five days, which gives us the following:

\begin{pmatrix}\nonumber 0.04791 &0.07634 &0.04976 &0.01776 &0.80823\\
0.11451 &0.19889 &0.15274 &0.06752 &0.46634\\
0.11196 &0.22911 &0.22553 &0.12610 &0.3073\\
0.05994 &0.15192 &0.18915 &0.12425 &0.47474\\
0 &0 &0 &0 &1\end{pmatrix}

Last, we take a look at the third row (the state in which he began) and the final column: That’s the chance he gets wet during the week. Subtract from 1 to find the chance that he didn’t get wet and you get 69.27 percent.

All in all, given the extremely precipitous climate in which Louie lives, his haphazard umbrella scheme doesn’t work too badly. TGIF.

Solution to the previous Riddler Classic

Congratulations to 👏 Steve Altschuld 👏 of New Albany, Ohio, winner of last week’s Riddler Classic!

Last week, seven antisocial settlers were moving to a circular prairie with a radius of 1 mile, where they would temporarily overcome their anxieties to work together to build houses that were far apart from each other. Specifically, they wanted to maximize the average distance between each settler and his or her nearest neighbor. With seven houses to build, this was pretty straightforward: One would build his house in the center of the circle, while the other six would form a regular hexagon along its circumference. Every settler would be exactly 1 mile from his nearest neighbor, so the average distance is 1 mile. But at the last minute, one especially antisocial settler canceled his move to the prairie altogether, leaving just six settlers with houses to build. With fewer people, could they find a better arrangement? Could they increase the average distance to more than 1 mile?

Yes, indeed they could. Specifically, they could increase the average nearest-neighbor distance to about a whopping 1.0023 miles! Ah, wide-open spaces.

Here’s what the optimal antisocial prairie neighborhood looks like, courtesy of this puzzle’s submitters, Randi Goldman and Zach Wissner-Gross.

Notice that the “center” house is just a little bit off-center. That’s the key.

The particular case of six settlers turns out to be an unusually tricky one, as Randi and Zach explained: If there are two settlers, they’ll simply build houses at diametrically opposite points on the circumference. If there are three, four or five settlers, they will arrange their houses as a regular polygon. If there are seven settlers, they’ll form a regular hexagon plus one settler in the center of the circle. But six is different.

Our winner this week, Steve, explained how he got started with his solving: With six settlers, you can place five houses on the circle and one in the middle. (If all six are on the circle, the best you can do is 1 mile apart.) I placed the five outer houses where they would go if I were creating a hexagon without the bottom vertex. I then realized that I could move the center house north and south a bit and slide two pairs of houses — the two pairs opposite each other east-west on the circumference, one pair above the other pair — around the edge of the circle a bit, in tandem. So now I have a formula with three variables: the distance from the center house to the top house, the angle of the top pair from the top vertex, and the angle of the bottom pair from top vertex. This would be a fairly horrendous equation, so I did what many of us do: I spreadsheeted it and toggled until I got my answer.

Solver Laurent Lessard presented his “modeling and optimization” approach, in which he considers various methods for solving such optimization problems, including hill-climbing, interior points, simulated annealing and the very cool-sounding particle swarms. He illustrated the optimal arrangements for this problem not only for six settlers but also for all numbers from two to 21 — from the simple east-west separation all the way to the intricate Ritz cracker.

This excellent solution sparked an interesting discussion on Twitter, in which mathematical collaborations were proposed, additional optimization techniques were suggested, and it was pointed out that a whole field of academic research was devoted to questions like this as they relate to electron crystals. Not only that, I was alerted to what has become my new favorite website: packomania.com. It is what you think it is.

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! Consider your holiday shopping done.

Want to submit a riddle?

Email me at [email protected]

The Little, Mathematically Determined House On The Prairie

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 Josh Vandenham, precipitation permutations:

Louie walks to and from work every day. In his city, there is a 50 percent chance of rain each morning and an independent 40 percent chance each evening. His habit is to bring (and use) an umbrella if it’s raining when he leaves the house or office, but to leave them all behind if not. Louie owns three umbrellas.

On Sunday night, two are with him at home and one is at his office. Assuming it never starts raining during his walk to his home or office, what is the probability that he makes it through the work week without getting wet?

Submit your answer

Riddler Classic

From Randi Goldman and Zach Wissner-Gross, little misanthropic houses on the prairie:

Antisocial settlers are building houses on a prairie that’s a perfect circle with a radius of 1 mile. Each settler wants to live as far apart from his or her nearest neighbor as possible. To accomplish that, the settlers will overcome their antisocial behavior and work together so that the average distance between each settler and his or her nearest neighbor is as large as possible.

At first, there were slated to be seven settlers. Arranging that was easy enough: One will build his house in the center of the circle, while the other six will form a regular hexagon along its circumference. Every settler will be exactly 1 mile from his nearest neighbor, so the average distance is 1 mile.

However, at the last minute, one settler cancels his move to the prairie altogether (he’s really antisocial). That leaves six settlers. Does that mean the settlers can live further away from each other than they would have if there were seven settlers? Where will the six settlers ultimately build their houses, and what’s the maximum average distance between nearest neighbors?

Submit your answer

Solution to the previous Riddler Express

Congratulations to 👏 Brenda Holloway 👏 of Manchester, Connecticut, winner of last week’s Riddler Express!

Last week, Alice and Bob were facing off in a footrace. The route was a straight path out followed by the same straight path back. But Alice literally wanted to face off — she wanted to run faster than Bob such as to maximize the amount of time they spent facing each other after she made the U-turn but before the two passed each other going in opposite directions. Assuming the turnaround time is negligible and the two each commit to running the race at a constant speed, how much faster than Bob should Alice run?

If Bob runs at speed \(B\), Alice should run at speed \((1+\sqrt{2})B\), or about 2.4 times his speed.

This (obviously) is a maximization problem, meaning we’re trying to find the value of a variable that maximizes some larger expression. That means we need a mathematical expression to maximize. Let’s try to piece that together.

Suppose the distance to the U-turn — that is, the halfway point of the race — is \(D\). (It won’t matter exactly what that distance is.) Suppose Alice’s speed, which we’re trying to calculate, is \(A\). The time it takes Alice to get there is \(D/A\). In that amount of time, Bob will have run a distance of \(B\cdot (D/A)\). So the distance between the two runners at the moment Alice turns around is \(D-B\cdot (D/A)\).

Now the two are running toward each other, so we must combine their speeds. They will, combined, cover that distance and pass each other after a time of \((D-B\cdot (D/A))/(A+B)\). That’s the amount of time we want to maximize.

A handy mathematical way to maximize things is to take derivatives. Specifically, we want to take the derivative of the expression above with respect to \(A\), set it equal to zero, and solve that for \(A\). That will give us a set of extremes, be they maxima or minima. The derivative of the expression that we’ll set to zero looks like:

\begin{equation*}\frac{D(-A^2+2AB+B^2)}{A^2(A+B)^2}=0\end{equation*}

That equation equals zero for two values of \(A\): \((1+\sqrt{2})B\) and \((1-\sqrt{2})B\). The latter of these doesn’t make sense for the case of our footrace (it’s negative), so we know the first must be the value we’re after. If Bob runs at speed \(B\), Alice should run at speed \((1+\sqrt{2})B\), or about 2.4 times his speed.

Solution to the previous Riddler Classic

Congratulations to 👏 Peter Ingraham 👏 of Brooklyn, New York, winner of last week’s Riddler Classic!

Last week, after facing each other down for so long in that footrace, Alice and Bob fell in love, got married and wanted to have kids. Potentially lots of kids. They figured out that the amount of work involved in having a child is equal to 1 divided by the age of that child. So if a child is 0, the work is infinite. If the child is 1, the work is 1; if a child is 2, the work is ½; and so on. They decided that they only wanted to have another kid if and when the total work involved for all of their other kids was equal to 1 or less. Ignoring real-world technicalities such as death, twins and the inability to decide precisely when one has a child: Will Alice and Bob have an infinite number of children? Can we predict, with an equation, when they will have their Nth child?

First, yes, Alice and Bob would have infinity children if they could. But they would have them very, very slowly. After about 10,000 kids, they’ll have to wait more than 10 years to have the next one, and the gap between children keeps increasing forever. Solver Scott Wu plotted how long they will wait to have their next child, based on how many children they’ve had so far, for their first 50,000 children. That looks like this:

Our winner this week, Peter, provided the following proof-by-contradiction of why the number of children the couple will eventually have is infinite: Suppose for the sake of argument that there was some point where Alice and Bob stopped having more kids, and that at this point they have \(k\) kids and \(n\) years have passed. Let’s examine the amount of work required at time \(2n\). All the kids are now age \(n\) or more. As an upper bound, each kid is worth at most \(1/n\) work, the amount required for the youngest child. Therefore the total work is at most \(k\cdot (1/n) = k/n\). But the number \(k\) is always less than \(n\): The gaps start at 1 year and always get longer. So Alice and Bob should have had another kid by this time since their total work \(k/n\) is less than 1. This is a contradiction. Therefore they never stop having kids.

There does not appear to be an exact, elegant formula for when Alice and Bob have their Nth child. But the Nth child does come at approximately N log N, a fact that we could ascertain by generating lots of simulated child data and running a regression. So, for example, the 1,000th child would be born approximately 1,000 log 1,000 — or 6,908 — years after the first child. Solver Laurent Lessard plotted the birthdates by the ordinal childbirths:

“Meet my brother, Bob Smith CMXLVII. Yeah, he’s my big brother, can’t you tell? He was born about 5,000 years ago.”

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! Consider your holiday shopping done.

Want to submit a riddle?

Email me at [email protected]

Alice And Bob Fall In Love

Welcome back to The Riddler — I hope you had a wonderful Thanksgiving. 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,14 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 Graydon Snider, road race intimidation tactics:

Two runners, Alice and Bob, are participating in a footrace. The route is a straight line out some distance and the same straight line back — the starting point and the finish line are the same. As the starting gun is about to go off, Alice hatches a race plan: Her legs feel good and she wants to run fast enough compared to Bob that after the U-turn, they are staring face-to-face for as long as possible. How much faster than Bob should Alice run to spend the maximum amount of time facing Bob before they pass each other going in opposite directions? Assume that, on the advice of their coaches, they’ve each committed to running at a constant speed the whole time, and that the turn-around time at the halfway point is negligible.

Submit your answer

Riddler Classic

From Dan Johnston, in which Alice and Bob then fall in love:

After their Riddler Express footrace, Alice and Bob fell in love and got married. Now they want lots of kids. However, as you may know, having one child, let alone many, is a lot of work. But Alice and Bob realized children require less of their parents’ time as they grow older. Alice and Bob, romantics that they are, decided to calculate how this relationship worked. They figured out that the work involved in having a child equals one divided by the age of the child in years. (Yes, that means the work is infinite for a child right after they are born. That may be true.)

Anyhow, since having a new child is a lot of work, Alice and Bob don’t want to have another child until the total work required by all their other children is 1 or less. Suppose they have their first child at time T=0. When T=1, their only child is turns 1, so the work involved is 1, and so they have their second child. After roughly another 1.61 years, their children are roughly 1.61 and 2.61, the work required has dropped back down to 1, and so they have their third child. And so on.

(Feel free to ignore twins, deaths, the real-world inability to decide exactly when you have a child, and so on.)

Five questions: Does it make sense for Alice and Bob to have an infinite number of children? Does the time between kids increase as they have more and more kids? What can we say about when they have their Nth child — can we predict it with a formula? Does the size of their brood over time show asymptotic behavior? If so, what are its bounds?

Submit your answer

Solution to the previous Riddler Express

Congratulations to 👏 Chris Sears 👏 of Maysville, Kentucky, winner of the previous Riddler Express!

The World Chess Championship ended this week after 12 straight draws followed by a series of speedier tie-breaking games. That’s fitting, because two weeks ago we posed this question: What are the chances that the better player wins a 12-game match? Specifically, suppose one of the players is better than his opponent to the degree that he wins 20 percent of all games and loses 15 percent of games; the other 65 percent end in draws.15 What are the chances the better player wins a 12-game match? How many games would a match have to be in order to give the better player a 75 percent chance of winning the match outright? A 90 percent chance? A 99 percent chance?

That better player wins a 12-game match about 52 percent of the time. The number of games required for those larger thresholds are, in order, 82, 248 and 773. (Call me crazy, but I’m totally game for a two-year-long World Chess Championship.)

So how do we get there? Solver Dan Swenson suggested this tidy approach. Consider the following expression:

\begin{equation*}\left(0.2x + 0.65 + 0.15x^{-1}\right)^{12}\end{equation*}

The coefficients 0.2, 0.65 and 0.15 are the probabilities of the three outcomes of an individual chess game, and the whole thing is raised to the 12th power because of the 12 games of the match. Expand that expression, multiplying it all out and grouping its like terms. Then, the coefficient on \(x^r\), where the exponent \(r\) is some integer, is the probability that the better player wins the match by \(r\) games. Finally, add the coefficients on all the positive powers of \(x\), which gives the probability that the better player wins the match. The result is about 0.5198, or about 52 percent.

For the second part of the problem, we can use that same approach, and just change the “12” in the exponent of the expression, and then, the same as before, expand it and sum the coefficients on the positive powers of \(x\). The smallest exponent that gives a 75 percent chance or better is 82, the smallest that gives a 90 percent chance or better is 248, and the smallest that gives a 99 percent chance or better is 773.

Solver Chris Sears illustrated how the probability that the better player wins the match increases as the number of games increases.

Somebody get FIDE on the phone!

Solution to the previous Riddler Classic

Congratulations to 👏 Scott Wu 👏 of Baton Rouge, Louisiana, winner of the previous Riddler Classic!

Two weeks ago, we presented you with a sort of Riddlerified version of beer pong. You had an infinite supply of ping-pong balls, each labeled with some number 1 through N. There was also a group of N cups, labeled 1 through N, each of which could hold an unlimited number of ping-pong balls. The game was played in rounds that had two phases: throwing and pruning. During the throwing phase, you draw balls randomly, one at a time, from the supply and toss them at the cups. The phase ends when every cup contains at least one ball. Next comes the pruning phase, in which you go through all the cups and remove any ball whose number does not match the number on its cup. Every ball drawn had a uniformly random number, every ball landed in a uniformly random cup, and every throw landed in some cup. The game was over when, after a round was completed, there were no empty cups.

How many balls would you expect to need to draw and throw to finish this game? How many rounds would you expect to need before finishing this game?

The first question — how many throws would you expect to need — is like a “coupon collector’s problem,” and versions of it have appeared in this column before, for example in a problem about collecting Riddler League football cards. In this case, we’re filling cups instead of collecting coupons.The solution to this problem is well-known and stems from the fact that as we collect coupons — or fill cups — it becomes more and more difficult to collect or fill the ones that remain. The specific solution is quite mathy and involves something called the Euler-Mascheroni constant, but the main takeaway is that the more coupons or cups there are, the more and more time we can expect to spend collecting coupons or throwing balls.

Solver Laurent Lessard illustrated how the expected number of throws increases roughly quadratically as the number of cups (and numbers on the balls) increases:

The second question — how many rounds would you expect to play — turns out to be much trickier. Lessard also illustrated his mathematical approach when playing with three cups. The cups in his diagram are either empty (white), filled with a correct ball (green), or filled with an incorrect ball (red). The arrows and the numbers next to them represent transition probabilities — the chances a cup goes from empty to correctly filled, for example, are 1/N. Our goal, of course, appears in the bottom right of the diagram, where all three cups are correctly filled and the game is over.

From there, Laurent describes how to turn this diagrammatic approach into an answer. He uses a Markov chain, which describes probabilistic sequences of events that depend on the current state of events — such as the balls currently in our cups. And from there he invokes a holy Riddler trinity: absorbing states and limiting distributions and nilpotent matrices.

The result of all this is that while the number of throws required grows roughly quadratically, the number of rounds required grows roughly linearly.

Of course, this is also a problem that admits programmatic, simulation-based approaches. Solver Robert Chin shared Python code for a Monte Carlo simulation, and Michael Branicky shared his code as well. Finally, solver Tim Book shared the results of his computer simulations, which illustrate how the expected number of rounds increases as the number of cups (and the number of numbers on the balls) increases — roughly linearly:

Happy tossing!

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! Consider your holiday shopping done.

Want to submit a riddle?

Email me at [email protected]

CORRECTION (Nov. 30, 2018, 11:50 a.m.): An earlier version of this article misstated the name of one of the solvers. It is Robert Chin, not Robin Chin.

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]