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.
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 oliver.roeder@fivethirtyeight.com.