Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. Two puzzles are presented each week: the Riddler Express for those of you who want something bite-size and the Riddler Classic for those of you in the slow-puzzle movement. Submit a correct answer for either,1 and you may get a shoutout in next week’s column. If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter.
Riddler Express
Most people will tell you that a kilobyte is 1,000 bytes, that a megabyte is 1,000,000 bytes and that a gigabyte is 1,000,000,000 bytes. But that’s not quite right — a kilobyte is in fact 1,024, or 210, bytes. A megabyte is 1,048,576, or 220, bytes. A gigabyte is 1,073,741,824, or 230, bytes.
While these aren’t whole number powers of 10, they’re all pretty close. And that’s thanks to the happy coincidence that there’s a power of two that’s very close to 1,000. Working through the numbers, 210 is a mere 2.4 percent more than 103.
But surely there are other, higher powers of 2 that are even closer to a power of 10. After 210, what’s the next (whole number) power of 2 that comes closer to a power of 10? (To be clear, “closer” doesn’t refer to the absolute difference — it means your power of 2 should differ from a power of 10 by less than 2.4 percent.)
Riddler Classic
This week’s Riddler Classic is a new take on a recent puzzle. Two weeks ago, you were waiting in line at a barbershop. There were four barbers working simultaneously, and each haircut took exactly 15 minutes. There were almost always one or more customers waiting their turn on a first-come, first-served basis.
Being a regular, you preferred to get your hair cut by the owner, Tiffany. If one of the other three chairs opened up, and it was your turn, you would have said, “No thanks, I’m waiting for Tiffany.” The person behind you in line would then be offered the open chair, and you’d remain at the front of the line until Tiffany became available.
Unfortunately, you weren’t alone in requesting Tiffany. In general, a quarter of the other customers were expected to hold out for Tiffany, while no one held out for any of the other barbers. The question was then, if you had one person in line ahead of you, and the four barbers were independently at random places in their respective haircuts, how long would you expect to wait until your haircut?
While last week’s solution explored some interesting mathematics, it made a critical assumption: that the person in front of you had a 25 percent chance of waiting for Tiffany. But as it turns out, this was not a reasonable deduction to make.2 And so, for this week’s Classic, you are being asked to analyze a more specific statement of the original problem.
Suppose all of Riddler City, with its incredibly vast population (25 percent of whom will wait for Tiffany), decides to get a haircut at this barbershop one fine morning, and everyone lines up at its entrance in a random order a few minutes before the shop opens at 8 a.m. After opening, the four barbers will start cutting hair for their first customers at random times between 8 a.m. and 8:15 a.m. Each haircut then lasts exactly 15 minutes.
Sadly, you find yourself toward the back of this very, very long line. To pass the time while you wait, you spend a long time thinking about this week’s Riddler column, completely unaware of the passage of time. The next thing you know, you’re second in line, with one person waiting in front of you — the exact conditions from the original puzzle. At this point, how long should you expect to wait for your haircut from Tiffany?
(Hint: Think about the probability that the person in front of you will request Tiffany. Is it still 25 percent? Also, keep in mind that if there are multiple Tiffany requesters at the front of the line, and a barber other than Tiffany becomes available, the next non-Tiffany requester will effectively jump the line.)
Solution to last week’s Riddler Express
Congratulations to ÑÑâÐ Veronica Pillar ÑÑâÐ of Ithaca, NY, winner of last week’s Riddler Express.
Last week, you had a tic-tac-toe board with nine pieces you could place: five Xs and four Os. If you randomly placed all nine pieces in the nine slots on the board (with one piece in each slot), what was the probability that X won? That is, what was the probability that there would be at least one occurrence of three Xs in a row at the same time there were no occurrences of three Os in a row?
A good place to start was to figure out how many possible arrangements there were. If there are nine total slots, and you’re choosing where to place the five Xs (or, alternatively, the four Os), then there are 9 choose 4, or (9·8·7·6)/(4·3·2·1) = 126, possible arrangements. So among these 126 total ways to place the Xs and Os, how many resulted in three Xs in a row but not three Os in a row?
There were several different strategies for counting these up. One way was to look at different cases, depending on where the three winning Xs showed up in the grid.
- If the three winning Xs were arranged horizontally in a row, then as long as each of the other two horizontal rows had one X, there wouldn’t be three winning Os. There were three possible rows for the winning Xs, three possible columns for one of the Xs in another row and three possible columns for the X in the remaining row. This accounted for 3·3·3 = 27 winning arrangements.
- If the three winning Xs in a were arranged vertically in a column, then as long as each of the other two vertical columns had one X, there wouldn’t be three winning Os. Once again, this accounted for 3·3·3 = 27 winning arrangements.
- If the three Xs were arranged diagonally, then there was no way for there to also be three winning Os. There were two possible diagonals for the winning Xs, and then 6 choose 2, or 15 possible ways to arrange the remaining two Xs. That accounted for another 30 winning arrangements.
It would seem that there were a total of 27+27+30 = 84 winning arrangements. However, there was one slight flaw in the above reasoning — some winning arrangements were counted twice!
For example, it’s possible to arrange the five Xs so that they occupy both diagonals of the grid. This arrangement was counted once for one of the diagonals, and once again for the other diagonal. It was also possible for the five Xs to occupy both a winning row and a winning column at the same time, another arrangement that was double-counted — once for the row, and again for the column. Since there were three rows and three columns, there were 3·3, or nine arrangements like this. Finally, it was possible to have five Xs occupy both a winning diagonal as well as either a winning row or a winning column. Since there were two diagonals and six total rows and columns, there were 2·6, or twelve arrangements like this.
At the end of the day, there appeared to be 84 winning arrangements, but 1+9+12 = 22 were double-counted. That meant the actual number of winning arrangements was instead 84−22, or 62. And so the probability of placing the pieces in a winning arrangement was 62/126, or 31/63 — just a shade under 50 percent.
Solver Julian Gerez found the answer via computer simulation, and even extended the puzzle, finding the chances of having two sets of winning Xs and simultaneous winning sets of Xs and Os.
Jeff Harrison, meanwhile, took a more traditional approach. He sketched out all the arrangements:
Who needs a computer when you have graph paper?
Solution to last week’s Riddler Classic
Congratulations to ÑÑâÐ Dan Rose ÑÑâÐ of Hopkins, Minnesota, winner of last week’s Riddler Classic.
Last week, you looked at a modified version of the game “Guess Who,” in which each player first randomly (and independently of their opponent) selected one of N character tiles. (It was possible, albeit unlikely, that both players chose the same character.) Each of the four characters was distinct in appearance — for example, characters had different skin tones, hair color, hair length and accessories like hats or glasses.
Each player also had access to a board with images of all N characters. The players alternated taking turns, and during each turn a player had two options:
- Make a specific guess as to their opponent’s selected character. If correct, the player who made the guess immediately won. Otherwise, that player immediately lost.
- Ask a yes-or-no question about their opponent’s chosen character, in order to eliminate some of the candidates. Importantly, if only one possible character was left after the question, the player still had to wait until their next turn to officially guess that character.
Both players were assumed to be highly skilled at choosing yes-or-no questions, so that they could always craft a question that identified any subset of characters, who would then be ruled in or out. Also, both were playing to maximize their own probability of winning.
When N was four, how likely was it that the player who went first would win?
You might have thought that splitting the candidates in half was the way to go. While that’s not a bad strategy, was it really the best strategy?
To find out, you could play a mock game in which both players use this strategy. First, Player 1 would ask a yes-or-no question that resulted in a “yes” for two of the candidates and a “no” for the other two. Either way, Player 1 would have narrowed the field from four candidates to two. Next, Player 2 would have done the same.
At this point, Player 1 could guess Player 2’s selected character for a 50 percent chance at victory. Alternatively, Player 1 could have asked a question to narrow down the field to a single candidate. Then, to have any chance at winning, Player 2 would have to guess among their two remaining candidates. So Player 1’s chances of winning stand at 50 percent.
Surprisingly, Player 1 could improve their chances of winning by initially asking a question that would result in a “yes” for either one or three candidates. There would be a 25 percent chance of narrowing it down to a single candidate, forcing Player 2 to take a wild guess. In this case, Player 1 would win 75 percent of the time.
The other 75 percent of the time, when Player 1 was left with three candidates, keeping track of all the possibilities got pretty hairy. But it turned out that Player 1 still had a 50 percent of winning.
Putting it all together, 25 percent of the time Player 1 had a 75 percent chance of winning, while the remaining 75 percent of the time Player 1 had a 50 percent chance of winning. Player 1 would therefore win 9/16 of the time, or more than half the time. By splitting the field asymmetrically (i.e., not in half) Player 1 could better take advantage of having the first turn, and achieve better than even odds of winning.
While the case of N = 4 was certainly complicated, the extra credit problems (N = 24 and N = 14) were even more so. Fortunately, solvers turned to their computers for help, using either the technique of recursion (as written up by Liam Kirwin and Robert Sturrock) or dynamic programming. When N = 24, you might have thought splitting the field in half would be optimal, asking a question that would result in a “yes” for 12 candidates and a “no” for the other 12. However, the puzzle’s submitter, Andrew Lin, found via that as long as that first question generates a “yes” for between 8 and 16 candidates, Player 1 can still maximize their chances of winning, which turned out to be 5/9. And in the case of N = 14, Player 1 could ask a question that generated a “yes” four, six, eight or 10 times (only the evens!), achieving a winning probability of 55/98.
The extra credit may have stopped there, but Riddler Nation did not. Something was afoot — for example, notice how all those answers were slightly more than 50 percent? Will that always be the case for Player 1 for different values of N? That turns out to be the case, as shown by Angela Zhou:
Even as the number of characters get’s absurdly large (into the thousands), Player 1’s chances of winning take on a repeating pattern, bouncing between 55.5 and 56.3 percent.
Angela and Robert Spillner together also studied the optimal number of “yes” answers a player should seek, depending on how many candidates each player had left. The resulting graph is a thing of beauty:
It’s clear that the winning strategy for “Guess Who” goes far beyond splitting the field in half with every question. All that’s left is for someone to encode an AI that plays with this optimal strategy. I, for one, am ready to lose!
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 Zach Wissner-Gross at riddlercolumn@gmail.com.