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 if you have a favorite puzzle collecting dust in your attic, find me on Twitter.
This week, two puzzles that revisit War, that old chestnut of childhood card games, and actually make it interesting!
Riddler Express
From Hans Zhou, inspired by Chinese folklore, it’s the War for Riddler Nation:2
You and a random opponent are playing a simplified game of War. Both you and your opponent have 13 cards in your deck: 2, 3, 4, 5, 6, 7, 8, 9, 10, jack, queen, king and ace. You can arrange these cards in any order you want. You’ll play a one-round game, where you go through all 13 of your cards just once. Both you and your opponent draw a single card off the top of your deck and compare them. If your card outranks your opponent’s, you get a point. (No points are awarded for ties.) After all 13 cards have been shown, the player with the most points wins.
I’ll match you up against every player who submits, and the player who wins the most games overall will be this week’s Express winner.
However, to enter into this tournament, you must first beat me, the house. I have a deck that is in this order: 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A. I, being the house and all, get an additional advantage in that I also win ties. Plus I can choose to play my decks forward or backward — the order above or A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2. Your deck must be able to beat both of my decks to enter the tournament.
Riddler Classic
From Scott Davis, a puzzle that every man, woman and child has pondered on a rainy afternoon:
Consider a standard, two-player, 52-card game of War. If I start with just the four aces, and you start with all 48 other cards, randomly shuffled, what are your chances of winning?
Solution to last week’s Riddler Express
Congratulations to 👏 Nicole Wilson 👏 of Monticello, Georgia, winner of last week’s Express puzzle!
You’re hanging out with some friends, shooting the breeze and talking sports. One of them brags to the group that he once made 17 free throws in a row after years of not having touched a basketball. You think the claim sounds unlikely, but plausible. Another friend scoffs, thinking it completely impossible. Let’s give your bragging friend the benefit of the doubt and say he’s a 70 percent free-throw shooter. Who’s right? What is the number of free throws that a 70 percent shooter would be expected to take before having a streak of 17 makes in a row?
The number is about 1,430 free throws.
The odds of a 70 percent shooter hitting 17 shots in a row, starting with any given single shot, is \(0.7^{17}\approx 0.002\). So we know, on average, it’ll take 1 divided by that, or about 430, tries to get the streak. But that number of tries isn’t the number of shots. It’s the number of streaks he begins by taking a shot after missing one. Those tries could fall short after two makes, or 10, or 16.
Here’s one way to get to the answer: You know your friend will have to take the first shot on his road to 17 430 times. He’ll take the second shot 0.7*430 = 301 times. The third 0.7*301 = 210.7 times. The fourth 0.7*210.7 = 147.5 times. And so on.
Adding all that up gives us about 1,430.
If you assume each shot takes five seconds, 1,430 shots would take about two hours — a long time, but certainly doable. But this result is very sensitive to the 70 percent shooting mark. A 60 percent shooter would need on average about 10 times as many shots, and nearly a full day, to expect to complete such a streak.
Solution to last week’s Riddler Classic
Congratulations to 👏 Aaron Cohen 👏 of Manhattan Beach, California, winner of last week’s Classic puzzle!
You and six friends are on a hit game show that works as follows: Each of you is randomly given a hat to wear that is either black or white. Each of you can see the colors of the hats that your friends are wearing but cannot see your own. Each of you has a decision to make. You can either attempt to guess your own hat color or pass. If at least one of you guesses correctly and none of you guess incorrectly, then you win a fabulous, all-expenses-paid trip to see the next eclipse. If anyone guesses incorrectly or everyone passes, you all lose. No communication is possible during the game — you make your guesses or passes in separate soundproof rooms — but you are allowed to confer beforehand to develop a strategy. What is your best strategy? What are your chances of winning?
It is very tempting to guess that your chances are 50-50 — and many of you did. Someone has to guess right, she has to guess the color of a hat she cannot see, and that hat is randomly black half the time and white half the time, after all. But, remarkably, you can do a lot better as a team.
Your best chances of winning are 7/8, or 87.5 percent. You can achieve that with the optimal strategy, adapted from the puzzle’s submitter Jared Bronski, described below:
To make the problem a bit more intuitive, first consider a simpler example where it’s just you and two friends on the game show. You can win this version 75 percent of the time. The simple strategy that does it is this: Each player looks at the hats of the other two. If she sees one hat of each color, she passes. If she sees two of the same color (e.g., white), she guesses that hers is the other color (e.g., black). Essentially you are betting that the hats are not all the same color. At least one player will always see two hats of the same color, so at least one player always guesses. If the hats are WWB or BBW, then exactly one player guesses correctly. If the hats are all the same color, BBB or WWW, then everyone guesses incorrectly — these arrangements occur 25 percent of the time. This strategy “stacks” the incorrect guesses and “spreads out” the correct ones: Either one person guesses correctly or three people guess incorrectly.
Now back to our main problem, where seven of you are on the show. Things get much more complicated, but importantly the solution has the exact same flavor — either one person guesses correctly or all seven people guess incorrectly.
To keep track of everyone, let’s assign each player a number. It turns out it’s easiest if we do this in binary numbers, as we’ll see shortly. So the seven of you get numbered like so:
Anna 001
Ben 010
Clarice 011
Doug 100
Edna 101
Fred 110
Georgina 111
Each player looks around and takes note of all the players she sees wearing black hats. She then carries out a small programmatic algorithm. She “XOR”s the numbers of all the black hat wearers to get a final count. (XOR is a logical operation, short for “exclusive or,” which returns true if exactly one of its inputs is true. In binary, it’s bit-wise addition without carrying. “1 XOR 0” is 1, “1 XOR 1” is 0, and so on.) If the final count is zero, she guesses black. If the count is her own number, she guesses white. If the count is anything else, she passes.
For example, suppose Anna, Ben and Georgina have black hats and everyone else has a white hat. Anna sees two black hats — Ben’s and Georgina’s — so her count is 101 (010 XOR 111), and she passes. Similarly, Ben’s count is 110 (001 XOR 111) and he passes, and Georgina’s count is 011 (001 XOR 010) and she passes. The rest of the players — Clarice, Doug, Edna and Fred — all get a count of 100. This is Doug’s number, so three of them pass while Doug guesses white. Doug is correct!
When all’s said and done, this approach gives a result quite similar to the simple three-player example: Either one person guesses correctly or all seven people guess incorrectly. Essentially you are betting that if you XOR together the numbers of the black hat wearers, the answer is not zero. The answer can be anything from 000 to 111, and all are equally likely, so this is a one-in-eight chance. Your team wins seven times out of eight.
This solution is closely related to something called Hamming code, a type of error-correcting code developed by a mathematician at Bell Labs in 1950.
Extending this logic, if there are \(2^N-1\) of you on the game show, you can expect to win \((2^N – 1)/2^N\) of the time.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.