How Many Numbers Contain The Numbers Of Their Numbers?

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,1 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 Daz Voss, numbers of numbers with numbers of their numbers:

The number 21322314 acts as its own inventory. That is, it contains two 1s, three 2s, two 3s and one 4. Another example is 22 — it contains two 2s.

These numbers consist of alternating tallies and numerals. First comes the tally, then the numeral being tallied, then another tally, and so on.

How many numbers of this kind exist?

(Assume the numerals have to be tallied in increasing order, so you can’t create new numbers simply by rearranging: 21321423, for example, doesn’t count.)

Submit your answer

Riddler Classic

From Michael Kragh Pedersen, some shapely game theory:

You are playing a game against a single opponent. In front of you is an empty eight-by-eight grid and a pile of the 12 different pentominoes, one of each.

Taking turns, you and your opponent select a pentomino from the pile, rotate it however you like (but not flip it over) and place it anywhere within the grid. By rule, the pieces can’t overlap or extend outside the grid. The person to place the last possible piece wins.

Assume you go first. What is the optimal strategy? How does this game end with perfect play?

Submit your answer

Solution to last week’s Riddler Express

Congratulations to 👏 Ricki Heicklen 👏 of Teaneck, New Jersey, winner of last week’s Riddler Express!

Last week brought us to the virtual Wild West of the video game “Red Dead Redemption 2.” In that game, there is a quest where the main character is meant to collect 12 unique cigarette cards from each of 12 different sets. The easiest way to collect these cards is to buy packs of cigarettes from the general store at $5 a pop, each pack containing one random card from one of the sets. How much would we expect our main character to spend to complete all 12 sets?

It will cost nearly $4,000 — quite a lot in those days.

This is an example of the classic coupon collector’s problem. There are 144 different cards the character wants to collect, each of which he’ll have a 1/144 chance of receiving each time he buys a pack. So how long will this take? The main problem for this main character — and the problem we need to quantify — is that sometimes, or even oftentimes, he’ll buy a pack containing a card he already has. This becomes more and more likely the more cards he has collected.

Let’s go card by card. The first card will be collected in one purchase for sure — the character doesn’t have any cards yet and doesn’t care which one he gets. In his subsequent purchases, the second card will be collected with probability 143/144, the third card with probability 142/144, and so on. It gets less and less likely we get a new card the more cards we already have. Once we have all but one card, each purchase only gives us a 1/144 — or 0.7 percent — chance at completing our quest.

We can rewrite the expected number of purchases this will take as the following:

144 * (1/1 + 1/2 + 1/3 + … + 1/144)

That equals about 799.27 expected purchases to collect all 144 cards. At $5 a purchase, that’s about $3,996.

Collecting cigarette cards … in this economy?!

Solution to last week’s Riddler Classic

Congratulations to 👏 Michael Branicky 👏 of Lawrence, Kansas, winner of last week’s Riddler Classic!

Last week you were home alone playing a solitaire game of “Bananagrams.” You spread the game’s 144 lettered tiles on the table in front of you and wondered, “What grid of words can I create that uses all of these tiles in the fewest possible words?”

Wonder no longer: You can use them all in just nine words.

Solver Michael Branicky found the 13-word candidate solution pictured below — bonus points to Michael for the actual Bananagram tiles. It features the lovely, 28-letter ethylenediaminetetraacetates, a chemical apparently used to dissolve limescale.

Solver Laurent Lessard was able to do a bit better by modeling the puzzle as something called a mixed-integer program. He found the nine-word grid below. And, though this grid is not the only nine-word grid — at the very least, you can shift the words below around to overlap on different points — it is the one made with the fewest words possible. It features those classic pieces of kitchen-table “Bananagrams” vocabulary: keratoconjunctivitides, paraformaldehyde, magnetofluiddynamics and oxyphenbutazones. (Notably, “oxyphenbutazone” also features in the theoretically highest possible scoring “Scrabble” play.)

I also asked what completed grid used the most words. Michael is our winner for how he tackled that question, offering this grid that uses 109 words — many of which are those “Scrabble” classics re or od.

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]

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,1 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.2 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 Robin 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]

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,1 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 day2 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]