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

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?

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]

You’re Home Alone. You Can Buy Zillions Of Video Game Cigarettes Or Beat Yourself At Bananagrams

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,9 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 Gerald Dorrer, I reckon this here’s a math puzzle:

In the video game “Red Dead Redemption 2,” there is a side quest where the main character is supposed to collect 12 sets of cigarette cards, each consisting of 12 unique cards.

Some cards can be found lying around in the open world, but the easiest way to collect the cards is to buy cigarettes at the store and collect the single random card included in each pack. Suppose Arthur is too lazy to look for cards in the open world and tries to complete the set only by buying packs at the store.

At $5 a pack, how much money do we expect Arthur to spend to complete all 12 sets? Riddler Classic From Chadwick Matlin, the deputy editor of some website called FiveThirtyEight, a puzzle perfect for the polar vortex: You’re snowed in alone with nothing to do but play a solitaire game of Bananagrams. As you spread its 144 lettered tiles out on the table in front of you, you begin to wonder: What grid of words can you create that uses all of these tiles in the fewest possible words? What grid uses all of the tiles in the most possible words? (To test if a word is allowed, use the ENABLE word list, a variant of which is used in games such as Words With Friends, for the purposes of this problem. The letters in Bananagrams are distributed as shown here.) Extra credit: How many completed grids are there, period, that use all 144 tiles? Solution to the last week’s Riddler Express Congratulations to Erin Seligsohn of Atlanta, winner of last week’s Riddler Express! Last week, we found ourselves on an island with a curious property: All of its young people told the truth and all of its old people lied. Specifically, there was an age limit L — a positive integer — and all islanders who were younger than age L only told the truth, while islanders who were at least L years old only told lies. We met five of them, and they had this to say. A: “B is more than 20 years old.” B: “C is more than 18 years old.” C: “D is less than 22 years old.” D: “E is not 17 years old.” E: “A is more than 21 years old.” A: “D is more than 16 years old.” B: “E is less than 20 years old.” C: “A is 19 years old.” D: “B is 20 years old.” E: “C is less than 18 years old.” What was L, and what could we learn about the ages of the islanders? L was 19 years old. Islander A was 19 years old, B was 20, C was 18, D was at most 16 and E was at least 20. The key is to ferret out the liars. Notice first that there are a few direct contradictions in the islanders’ statements: A and D contradict each other over B’s age, B and E contradict each other over C’s age, and E and C contradict each other over A’s age. So at least one member of the three pairs (A, D), (B, E) and (E, C) must be a liar. We also know that D and B aren’t both liars — that would make E both exactly 17 years old and more than 20 years old, which is impossible. Given those facts, we have a few possibilities we can test. Let’s guess that A, B and E are liars and that C and D are truth-tellers, then check the consistency of their statements. There are two statements about each islander, which we can translate into true facts given our guess about the truthfulness of each of their speakers. The statements about A check out: A is less than or equal to 21 and A is 19. That means A is 19. The statements about B also check out: B is less than or equal to 20 and B is 20. That means B is 20. The same goes for C: C is less than or equal to 18 and C is greater than or equal to 18. That means C is 18. And D: D is less than 22 and D is less than or equal to 16. That means D is at most 16 years old. And finally E: E is not 17 and E is greater than or equal to 20. That means E is at least 20. Because all these statements check out, that means our guess worked! Since A, B and E are liars and C and D tell the truth, that means both of our truth-tellers are at most 18 and all of our liars are 19 or older. Therefore, L must equal 19. And we’re done! And I don’t know about you, but I’m ready to get off this island. Solution to last week’s Riddler Classic Congratulations to Onufry Wojtaszczyk of Warsaw, Poland, winner of last week’s Riddler Classic! Once we got off that island, we headed straight for some rest and relaxation at the card table, where we sat down to play a game of bridge. The game begins with an auction. There are four players, each sitting across from his or her partner. Simply put, the auction goes like this: Beginning with the dealer and orbiting around the table, players can place a bid or pass. Players who’ve passed can re-enter the bidding later. A bid is comprised of a number (one through seven) and a suit. Every legal bid must be higher than the one that came before, meaning either that its number is higher or that its number is the same and its suit is higher (from high to low, the suits go no-trump, spades, hearts, diamonds, clubs). The auction ends if the other three players pass after a bid, or if all four players pass right away. But the R&R came to an abrupt end with this question: How many different legal bridge auctions are there? There are 1,574,122,160,956,548,404,565, or more than a thousand billion billion, or more than the estimated number of grains of sand on the planet. To get there, let’s start with a much smaller number: 35. A bid is made up of one of seven numbers and one of five “suits” (the four suits plus no-trump); multiplying numbers and suits gives us 35 possible bids, each with a unique rank. From there, let’s build up to our final calculation. We know now that in every auction, the players will make somewhere between one and 35 bids. We will proceed by counting all the auctions with one bid, with two bids, with three bids and so on, and add up all of their possibilities in a big sum. If an auction comprises $$N$$ bids, say, then there are “35 choose $$N$$” choices for what specific bids those could be. And between those bids will be some number of passes. Before the first bid there could be zero, one, two or three passes (four possibilities), and between all subsequent bids there can be zero, one or two passes (three possibilities chosen at $$N-1$$ points in the auction). We can account for passes by multiplying by those numbers of possibilities. That leads us to our final, big sum: \begin{equation*}1+\sum_{N=1}^{35} {35 \choose N}\cdot 4\cdot 3^{N-1}\end{equation*} An online calculator can turn this into our numerical final answer. That lone “1+” at the front of the equation is the possibility that the auction ends immediately with all four players passing. For extra credit, I asked how many different auctions there would be if we incorporated the bridge tactics known as doubling and redoubling. The calculation process is very similar, and the new formula — taking into account that there are now 21 intra-bid combinations of passes, doubles and redoubles, plus seven ways the auction ends with passes, doubles and redoubles — looks like this: \begin{equation*}1+\sum_{N=1}^{35} {35 \choose N}\cdot 4\cdot 21^{N-1}\cdot 7\end{equation*} And the final answer is, of course, bigger. Much, much bigger: 128,745,650,347,030,683,120,231,926,111,609,371,363,122,697,557. But in the grand scale of gnarly game math, the number of possible bridge auctions isn’t all that enormous: It is only about 0.25 percent of the number of possible chess positions. 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] Don’t Trust Anyone Older Than L 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,8 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 Dominic van der Zypen, a shipwreck demands deduction: We are marooned on an island that has the following curious property: Everyone over a certain age lies all the time. More specifically, there is an age limit L — a positive integer — and all islanders who are younger than age L only tell the truth, while islanders who are at least L years old only tell lies. We are greeted by five islanders who make the following statements: A: “B is more than 20 years old.” B: “C is more than 18 years old.” C: “D is less than 22 years old.” D: “E is not 17 years old.” E: “A is more than 21 years old.” A: “D is more than 16 years old.” B: “E is less than 20 years old.” C: “A is 19 years old.” D: “B is 20 years old.” E: “C is less than 18 years old.” What is L? And what did we just learn about the ages of the islanders? Riddler Classic From Mark Whelan, shuffle up and deal. And count very, very high: Bridge, that venerable card game, begins with an auction. There are four players around a table, each sitting across from his or her partner. At its simplest, the auction goes like this: Beginning with the dealer and orbiting around the table, players can place a bid or pass. Players who’ve passed can re-enter the bidding later. A bid is comprised of a number (one through seven) and a suit. Every legal bid must be higher than the one that came before, meaning either that its number is higher or that its number is the same and its suit is higher (from high to low, the suits go no-trump, spades, hearts, diamonds, clubs). The auction ends if the other three players pass after a bid, or if all four players pass right away. How many different legal bridge auctions are there? Extra credit for you bridge nerds out there: What if we incorporate the possibility of doubling into this accounting exercise? Specifically, if the last bid was made by one of the opposing partners, a player may, while bidding, also double, which increases the stakes for the hand. If a player has been doubled before, they may redouble. Including these variations on bids, how many legal bridge auctions are there now? Solution to the last week’s Riddler Express Congratulations to Alana Christie of Dallas, winner of last week’s Riddler Express! Last week brought another maze that the enemies of Riddler Nation had crafted to entrap you. It looked like this: Your goal was to get to the star in the middle, and you could start your journey in any square around the perimeter. You then moved through the squares — up, down, left or right — by following the squares’ arrows. If a square had a two-headed arrow, you could choose whichever of its directions that you liked. If you arrived in a square containing a number, you could exit in any direction you liked, but you had to add that number to your score. Your challenge was to solve the maze with the lowest possible score, which was the total of all numbered squares you crossed. What was the score? The lowest possible score was 1. You can achieve it by entering via the green square on the middle of the maze’s right-hand edge, traveling left, then up to a “0,” then left some more, then up, left to another “0,” left, down, left through a “1,” left, down, and you’re there! That path looks like this, as illustrated by solver Matthew Modlin: You could solve this maze simply by playing around a bit — by “following your nose,” as my high school calculus teacher used to say. (My nose, as it turned out, wasn’t especially good at calculus.) Or you could work backward, starting at the star and working toward the perimeter. Or you could employ the computational services of an algorithm. Solver Laurent Lessard, for example, used something called the Bellman-Ford algorithm, which calculates the shortest route and is used in applications such as routing data. His solution looks like this: Solution to last week’s Riddler Classic Congratulations to Shailesh Ingale of Chicago, winner of last week’s Riddler Classic! Last week you came on down to play a game on “The Price Is Right” called Cover Up. You were trying to win a car by guessing its five-digit price. You had two numbers to choose from for the first digit, three numbers for the second digit, and so on, ending with six options for the fifth and final digit. To begin, you locked in a guess at the entire price of the car. If you got at least one digit correct on the first guess, the correct digit(s) were highlighted and you got to replace incorrect digits on a second guess. That process continued on subsequent guesses until the price was guessed correctly. However, if none of the new numbers you swapped in were correct, you lost. You could conceivably have won the car on the first guess or with up to five guesses. What were the chances you won the car if all of your guesses were random selections, not based on any knowledge of cars? They were 231/720, or about 32.1 percent. Why? In total, the car could have any one of 2*3*4*5*6 = 720 different prices, each of which is equally likely, as far as you’re concerned. There are also 720 guessing “paths” you could take, each of which is equally likely. The bulk of the solving comes in figuring out which of these paths lead you to driving home in a new car and which do not. To figure that out, let’s denote your guess as ABCDE — or abCDe or ABcde, etc. — where the letters are capitalized if that particular digit is correct and lowercase if it is incorrect. There is only one way to guess all the digits correctly on the first try: ABCDE. There are five ways to go from four correct digits and one incorrect digit to winning the car: ABCDe → ABCDE, ABCdE → ABCDE, ABcDE → ABCDE, AbCDE → ABCDE, aBCDE → ABCDE. And so on. Once we’ve counted up all these paths — solver Ryan Lafitte wrote a handy list of them — we arrive at a total of 231. We divide that by the total number of paths, 720, and we’re done! Now suppose that you knew a little something about cars. Specifically, you knew the ten-thousands place of the car’s price for sure, therefore guaranteeing you at least one correct guess. How much does that knowledge improve your chances of winning the car? Not much, it turns out. Locking in the first digit means you have half as many possible prices and half as many routes for getting to the right price, so your chances of winning in this case are 116/360, or only about 32.2 percent. A little knowledge goes a little way. 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] Come On Down And Escape The Maze 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 Andy Reigle, once more into the maze, dear friends: Those pesky enemies of Riddler Nation are at it again! A couple of weeks ago, they trapped you in a maze without walls. Most of you escaped, but the enemies remain undeterred. They’ve been hard at work building a new maze without walls, shown below. Before banishing you to the maze, they hand you a list of rules. 1. You can enter via any perimeter square. The goal is to reach the yellow star in the center with the lowest possible score, which is calculated by adding up all the numbers that appeared in any squares you crossed. 2. You can only move horizontally or vertically (not diagonally) to bordering squares. 3. If you enter a square with an arrow (↑), you have to exit that square in the direction the arrow indicates. Some squares have double arrows (), giving you a choice of two directions. 4. If you enter a square with a number, you must add it to your score, but you can exit in the direction of your choice. 5. If an arrow leads you to a square with a skull, you die. But you knew that already. What is the lowest score you can achieve while solving the maze and saving Riddler Nation? Riddler Classic From Josh Berry, come on down! You’re playing a “Price Is Right” game called Cover Up, which has contestants try to guess all five digits of the price of a brand new car. You have two numbers to choose from for the first digit, three numbers to choose from for the second digit, and so on, ending with six options for the fifth and final digit. You’re not winning any$100,000 cars in this game.

First, you lock in a guess at the entire price of the car. If you get at least one digit correct on the first guess, the correct digit(s) are highlighted and you get to replace incorrect digits on a second guess. This continues on subsequent guesses until the price is guessed correctly. But if none of the new numbers you swapped in are correct, you lose. A contestant could conceivably win the car on the first guess or with five guesses, getting one additional correct digit highlighted on each guess.

First question: If you’re guessing entirely by chance, what’s the likelihood of winning the car?

Second question: Suppose you know a little bit about cars. Specifically, you are 100 percent certain about the digit in the ten-thousands place, but have to guess the remaining four digits by chance. What’s the best strategy, and what’s the likelihood of winning the car now?

Solution to the last week’s Riddler Express

Congratulations to Derek Truesdale of San Jose, California, winner of last week’s Riddler Express!

Last week took us to Broadway. The song “Seasons of Love” from the musical “Rent” states that a year has 525,600 minutes and, indeed, 365×24×60 = 525,600. (Leap years need not apply.) That, naturally, raised a question: Given any three random integers — X, Y and Z — what are the chances that their product is divisible by 100?

The chances are exactly 12.43 percent.

To get there, we want to figure out the chances that XYZ contains at least two factors of 2 and at least two factors of 5 — 2×2×5×5 = 100.

To get started with this calculation, brush off that elementary school lesson on factors. As solver Hector Pefo explained, note that the probability that this number has at least two factors of 2 is 1 minus the probability that it has zero factors of 2 minus the probability that it has one factor of 2. Half of all integers are divisible by 2. So the probability that XYZ has zero factors of 2 equals $$(1/2)^3 = 1/8$$. For XYZ to have exactly one factor of 2, one of its elements has to have exactly one factor of 2 and the other two have to be odd. Half of all even numbers, or a quarter of all numbers, have exactly one factor of 2 — that is, they are not divisible by 4. So the probability that XYZ has one factor of 2 equals $$3\cdot (1/4)(1/2)(1/2)$$. So the probability that we’ll successfully get our factors of 2 into our mystery number is $$1 – 1/8 – 3/16 = 11/16$$.

Now for the factors of 5. The logic is the same: The probability that it has at least two factors of 5 is 1 minus the probability that it has zero factors of 5 minus the probability that it has one factor of 5. That probability is given by $$1 – (4/5)^3 – 3\cdot (1/5 – 1/25)(4/5)^2 = 113/625$$.

We can multiply those two probabilities together to find the chance that XYZ is divisible by 4 and 25, or, as we’ve wanted all along, 100. $$(11/16)(113/625) = 0.1243$$, or 12.43 percent.

“Seasons of Love,” you got lucky.

Solution to last week’s Riddler Classic

Congratulations to Andrew Petersen of Cedar Rapids, Iowa, winner of last week’s Riddler Classic!

Last week, you and I were playing a game. Spread out on a table in front of us, face up, were nine index cards with the numbers 1 through 9 on them. We took turns picking up cards and putting them in our hands. (There was no discarding.) The game ended in one of two ways. If we ran out of cards to pick up, the game was a draw. But if one player had a set of three cards in his or her hand that added up to exactly 15 before we ran out of cards, that player won. (For example, if you had 2, 4, 6 and 7, you would win with the 2, 6 and 7. However, if you had 1, 2, 3, 7 and 8, you hadn’t won because no set of three cards added up to 15.) Let’s say you went first. With perfect play, who would win and why?

No one will win — the game will be a draw. Why? This is really tic-tac-toe in disguise.

Specifically, it’s tic-tac-toe played on top of a magic square. Consider arranging the nine index cards in the following way:

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

The cards in every row, column and diagonal add to 15 — exactly what one of us needs to win. If picking up a card and putting it in one’s hand is akin to marking that card with an X or an O, then this game is just tic-tac-toe on this specific sort of board. With perfect play, it’s well known that tic-tac-toe is a guaranteed draw. So this game is, too! (But it’s still fun, I promise.)

If you’re in the mood to take it to the next level, here’s an article from 2018 about how something called “ultimate tic-tac-toe” has plenty to tell us about modern politics.

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]

525,600 Minutes Of 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,23 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 Gary Anwyl, some Broadway math:

The song “Seasons of Love” from the musical “Rent” states that a year has 525,600 minutes. And, indeed, 365×24×60 = 525,600.

This, naturally, raises an abstract mathematical question: Given any three random integers — X, Y and Z — what are the chances that their product is divisible by 100?

Riddler Classic

From John Hanna, a different kind of “card” game:

You and I are playing a game. It’s a simple one: Spread out on a table in front of us, face up, are nine index cards with the numbers 1 through 9 on them. We take turns picking up cards and putting them in our hands. There is no discarding.

The game ends in one of two ways. If we run out of cards to pick up, the game is a draw. But if one player has a set of three cards in his or her hand that add up to exactly 15 before we run out of cards, that player wins. (For example, if you had 2, 4, 6 and 7, you would win with the 2, 6 and 7. However, if you had 1, 2, 3, 7 and 8, you haven’t won because no set of three cards adds up to 15.)

Let’s say you go first. With perfect play, who wins and why?

Solution to the last week’s Riddler Express

Congratulations to Gwen Katz of Altadena, California, winner of last week’s Riddler Express!

Last week, the pesky enemies of Riddler Nation sent you into a maze. You had to reach the “” to escape. The maze looked like this:

You were, however, allowed to enter the maze anywhere on its perimeter. You could travel in straight lines up, down, left and right, but never diagonally. The letters in the boxes indicated your next move, relative to your direction of travel: “L” meant you turned left, “R” you turned right, “S” you continued straight and “?” you could choose any direction. If you hit an “X” or exited the maze, you lost. Could you reach the “,” and if so, how many moves did it take?

Yes, indeed you could. There was more than one way to solve the maze, but the quickest path took 34 moves.

Here’s that path, from this week’s winner, Gwen:

Beautiful, isn’t it? Here’s a slightly longer, 42-move path from solver Ken Marley, entering the maze at a different spot.

One useful way to solve the puzzle is to work backwards. That way, for example, we know that we’ll need to arrive in the “L” below the smiley face — none of the other squares will work. We also know then that we’ll need to arrive in the “L” below that “L,” and therefore the “S” to the left of that “L,” and so on, eventually leading us to one of the squares around the perimeter.

This navigational puzzle also generated some lovely visualizations. Solver Chris Clements, inspired by his fond memories of the text-based adventure game Hunt the Wumpus, redrew the maze into something a bit more intuitive for us human travelers.

And solver Dan Larremore recast this puzzle as an exercise in network visualization. Each square in the maze is a node in a network, and each node is connected to other nodes as a result of the letter in that square. In this approach, a solution looks like this:

Solution to last week’s Riddler Classic

Congratulations to Grant Alpert of Ann Arbor, Michigan, winner of last week’s Riddler Classic!

Last week, after escaping that maze, you found yourself on the street corner talking to a man who said his name was Three Deck Monte. On a table in front of him were three decks of cards, which you were allowed to inspect.

• Red Deck: four aces, four 9s, four 7s
• Blue Deck: four kings, four jacks, four 6s
• Black Deck: four queens, four 10s, four 8s

Monte offered you a bet: You pick any one of the decks, and he then picks a different one. You both shuffle your decks and compete in a short game similar to War. You each turn over cards one at a time, the one with a higher card wins that turn, and the first to win five turns wins the bet.

Should you take it? What are your chances of winning if you do?

No, you probably shouldn’t take this bet, and not just because his name is Three Deck Monte. Monte will win this game about 70 percent of the time — 1,274/1,815 to be exact.

This game is sort of like rock-paper-scissors in disguise. While it’s true that you can pick any deck you want, Monte will observe your choice, and there will always be a deck that Monte can pick that has the advantage over yours. Just as rock beats scissors beats paper beats rock, so too does the Red Deck have the edge over the Blue Deck, which has the edge over the Black Deck, which has the edge over the Red Deck.

Once we’ve noticed this fact about the game, all that’s left is to calculate our chances of winning given our choices of deck. A little computer program is helpful here. Our winner Grant explained what his program did for each deck matchup:

1. Reset the deck and loop 12 times over the following:
1. Pick a random number, from one to the number of cards remaining.
2. Remove that card from the deck.
3. Compare the cards and add to the win total of the winning player.
4. Check the win totals for each player; if either is five, go back to Step 1.

Solvers Aaron Rudkin, Ed Tang and Zach Bogart were also kind enough to share their code.

Finally, solver Josh Starkey shared the visual results of his simulations, showing the advantages that accrue with each set of decks.

It’s a trap!

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]

Can You Escape A Maze Without Walls?

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,9 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 new kind of maze:

Bad news: the enemies of Riddler Nation have forced you into a maze. And this maze is weird. The rules are as follows.

• You move between boxes in a grid: up, down, left or right, but never diagonally.
• Your goal is to arrive in the finish square, designated here by a “.”
• Your movement is dictated by the symbol inside the square you have just moved to, and each direction is relative to where you’d be facing if you were physically walking the maze. “S” means you continue straight, “R” means you turn right, “L” means you turn left, “U” means you make a U-turn, and “?” gives you the option of any of those four directions.
• An “X” ends your game in failure — think hot lava. (But hey, you can always start over!)
• If you are forced to exit the maze’s grid, you lose — more hot lava.

Your maze is below. You may enter the maze anywhere along the perimeter, giving you 32 options. Some of these, however, immediately fail. If you enter at a “U” on the top of the maze, for example, you must immediately U-turn out of the maze, so you lose.

Can you reach the smiley face? If so, how many moves does it take?

Riddler Classic

From Jordan Miller and William Rucklidge, three-deck monte:

You meet someone on a street corner who’s standing at a table on which there are three decks of playing cards. He tells you his name is “Three Deck Monte.” Knowing this will surely end well, you inspect the decks. Each deck contains 12 cards …

• Red Deck: four aces, four 9s, four 7s
• Blue Deck: four kings, four jacks, four 6s
• Black Deck: four queens, four 10s, four 8s

The man offers you a bet: You pick one of the decks, he then picks a different one. You both shuffle your decks, and you compete in a short game similar to War. You each turn over cards one at a time, the one with a higher card wins that turn (aces are high), and the first to win five turns wins the bet. (There can’t be ties, as no deck contains any of the same cards as any other deck.)

Should you take the bet? After all, you can pick any of the decks, which seems like it should give you an advantage against the dealer. If you take the bet, and the dealer picks the best possible counter deck each time, how often will you win?

Solution to the previous Puzzle 1: Bubbly

Congratulations to Brian Leebrick of Lynn Haven, Florida, winner of last week’s Puzzle 1!

Last week brought two puzzles from the 2019 MIT Mystery Hunt. They were constructed by members of a puzzling superteam called Setec Astronomy. The answer to each puzzle was an English word or phrase.

In the first puzzle — by Sami Casanova with art by Jesse Gelles — you were presented with a series of images of arrangements of bubbles, some of which were inside of others. You and another player took turns popping the bubbles, and the player who popped the last bubble won. Your job was to identify the winning first moves in each image, and from there extract the word or phrase that was the answer.

This game is a variant of Nim, and for each game, the first player can guarantee themselves a win — the goal of the puzzle is to find all possible winning moves for the starting player.

In the images below, the winning first moves (sometimes there are multiple options) for each game are colored in (using a different color for each game). Proper strategies in Nim can be found using a mathematical idea called the Nim sum.

In the final image, all winning first moves for all games are shown superimposed together.

If you read the letters assigned to each bubble from left to right, top to bottom, they spell ANSWER RELIEF PITCHER.

You can also find a Python program that solves this puzzle on the official Hunt solution page.

Solution to the previous Puzzle 2: State Machine

There were … no winners of last week’s Puzzle 2! So congratulations to my editor, I guess? He predicted that this puzzle was too hard. (He says the same thing at least every other week, so he was bound to be right one of these times.)

The second Hunt puzzle, by Matt Gruskin, began with the following cryptic introduction, known in Hunt-speak as “flavor text.” It’s meant to provide hints as to how to begin solving.

“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.”

What followed were a series of mathematical expressions, beginning with -9 – ◐ + – ◳ + ▥ + ◉ and ending with +9 – ◩ – ◍ + ◫ + ◑ + ◱ – ▨. And that was it. So what gives? Here’s a lightly edited version of the solution from from the official Mystery Hunt page:

This puzzle consists of a set of 48 algebraic expressions, containing 48 unique symbols, as well as one numerical constant per expression. Each of the 48 continental states has its own symbol and its own expression. Each state’s expression uses exactly the symbols of the states geographically adjacent to that state, and the solver may eventually realize that within each expression, the states are referenced in alphabetical order — using these facts, we can uniquely match symbols and expressions to states.

States are considered adjacent when they share a land border. The puzzle’s creators considered the Four Corners states to be adjacent to one another. The algebraic expressions will provide confirmation that you’ve picked the correct bordering states.

The next step is to assign an initial value to each state. The flavor text, “Our Founding Fathers started this nation from nothing” is intended as a clue to solvers that the initial value assigned to each state should be zero.

We can now treat the algebraic expressions as transition functions from one “state” of state values to the next. During each transition, we replace a state’s value with a value computed from its geographically adjacent states, according to that state’s algebraic expression.

After repeating this process several times (it turns out that three iterations are needed to solve the puzzle), we reach a state where all values are either zero or positive. Indexing into state names using the positive values — so that a 2 for Idaho gives its second letter, D, or a 5 for Maine gives its fifth letter, E — and writing these letters in the locations of their states on the map, we can read a word from each cluster of states on the map and extract the answer phrase KATIE BAR THE DOOR.

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 Many Crossword Puzzles Can You Make?

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.

Riddler Express

From Tyler Barron, you spin me right round, numbers, right round:

Given a two-character, seven-segment display, like you might find on a microwave clock, how many numbers can you make that are not ambiguous if the display happens to be upside down?

For example, the number 81 on that display would not fit this criterion — if the display were upside down it’d appear like 18. The number 71, however, would be OK. It’d appear something like 1L — not a number.

Riddler Classic

Crossword puzzle grids typically obey a few rules and conventions.

1. They are 15-by-15.
2. They are rotationally symmetric — that is, if you turn the grid upside down it appears exactly the same.
3. All the words — that is, all the horizontal and vertical sequences of white squares — must be at least three letters long. All the letters must appear in an “across” word and a “down” word.
4. The grid must be entirely connected — that is, there can be no “islands” of white squares separated from the rest by black squares.

First question: How many such crossword grids are there?

Second question: Crossword constructors do well to avoid using “cheater squares,” black squares whose addition makes some words shorter but does not change the puzzle’s total word count. How many grids are there without cheater squares?

Extra credit: The Sunday “New York Times” puzzle is 21-by-21. How many of those are there, with and without cheater squares?

Solution to the previous Riddler Express

Congratulations to Grace Lyden of Minneapolis, winner of last week’s Riddler Express!

Last week, you multiplied together some of the integers from 1 to 99 and got this monstrosity as a result:

530,131,801,762,787,739,802,889,792,754,109,70_,139,358,547,710,066,257,652,050,346,294,484,433,323,974,747,960,297,803,292,989,236,183,040,000,000,000.

What was the missing digit?

It was 6.

The puzzle’s submitter, Max Weinreich, explains the logic: Hopefully, this number is divisible by 9. If it is, then we know that its digits add up to a multiple of 9, which, upon adding all the digits up, would force the missing digit to be a 6. How can I be sure that my number really is divisible by 9? The largest number that is a product of integers from 1 to 99 but that is not divisible by 3 is 1 * 2 * 4 * 5 * 7 * 8 * 10 * 11 * … * 97 * 98. And so any two extra numbers I throw into this calculation will force the answer to be a multiple of 3 twice over — that is, a multiple of 9. So the largest non-multiple of 9 that I could get by my calculation is 96 * (1 * 2 * 4 * 5 * … * 97 * 98) which, if you put it into the calculator, turns out to have fewer digits than the enormous number in our problem. Therefore, the number is divisible by 9 and the missing digit is a 6.

Solution to the previous Riddler Classic

Congratulations to Viviana Acquaviva of Brooklyn, New York, winner of last week’s Riddler Classic!

Last week you were selected for the first manned mission to Mars: five Earth-years, or 1,825 Earth-days, on the red planet. Conditions would be brutal. So brutal that it was known exactly one vital piece of equipment would break each day. Therefore, you and the rest of the international team were sent with three 3D printers to print replacement parts for critical equipment. Each printer was manufactured in a different country, however, and parts from one printer were not compatible with any of the other printers (that meant no scavenging allowed).

If something broke on a 3D printer, you had to use one of the other 3D printers to print a replacement part. Any part could be printed effectively instantly, though any given printer only had the power to print one piece per day. The Riddler Aeronautics and Space Administration tested all three printers and found that, in addition to the daily breakage of the vital life-support equipment, one had a 10 percent chance of something breaking on any given day, the second a 7.5 percent chance and the last a 5 percent chance. If you couldn’t quickly print a replacement part for any piece of vital equipment, you’d die. What were the chances you made it home alive?

If you were judicious in your use of the printers, you’d have about a 50-50 shot at survival. Let’s walk through some interplanetary disaster scenarios.

If zero printers break on some day, you’re clearly fine. You have more than enough hardware to fix your vital life-support equipment. You could even create some Martian art with your extra 3D printers.

If one printer breaks on some day, you’re also fine. You can print a part to fix it with one of the printers, and you can print a part to fix the vital equipment with the other printer. No sweat. (After all, it is about -80 degrees Fahrenheit up there.)

If two printers break on some day, you may begin to worry. However, you can science your way out of this scenario, too. Call the printers A, B and C, and suppose it was A and B that broke. Fix A using C. Then fix B using A. Then fix the vital equipment using B. Phew! Close one.

If three printers break on some day, you’re toast. Or an icicle. In any case, you’re dead — you have no way to fix the vital equipment that breaks. The chances of all three printers breaking on a given day are $$0.1\times 0.075 \times 0.05 = 0.000375$$, or 0.0375 percent. Not bad, but you’re going to be on Mars for a while — 1,825 days to be precise. The chance that this deadly state of affairs never comes to pass is $$(1-0.000375)^{1,825}$$, or about 0.5043, or about 50.43 percent.

Would you flip a life-and-death coin for five years on Mars? (I would.) Or would you just find a way to decommission Riddler Nation’s space agency for putting you in such unnecessary peril in the first place?

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]

CORRECTION (Jan. 18, 2018, 10:40 a.m.): An earlier version of this article contained a logically incomplete Riddler Express solution. That solution has been replaced.

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?

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.

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?

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?

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?

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?

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]