How Good Are You At Guess Who?

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,¹ 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

A local cafe has board games on a shelf, designed to keep kids (and some adults) entertained while they wait on their food. One of the games is a tic-tac-toe board, which comes with nine pieces that you and your opponent can place: five Xs and four Os.

When I took my two-year-old with me, he wasn’t particularly interested in the game itself, but rather in the placement of the pieces.

If he randomly places all nine pieces in the nine slots on the tic-tac-toe board (with one piece in each slot), what’s the probability that X wins? That is, what’s the probability that there will be at least one occurrence of three Xs in a row at the same time there are no occurrences of three Os in a row?

Submit your answer

Riddler Classic

Sticking with the board game theme, from Andrew Lin comes a closer examination of a classic game of reasoning and elimination:

In the game of “Guess Who,” each player first randomly (and independently of their opponent) selects one of N character tiles. While it’s unlikely, both players can choose the same character. Each of the N characters is distinct in appearance — for example, characters have different skin tones, hair color, hair length and accessories like hats or glasses.

Each player also has access to a board with images of all N characters. The players alternate taking turns, and during each turn a player has two options:

• Make a specific guess as to their opponent’s selected character. If correct, the player who made the guess immediately wins. Otherwise, that player immediately loses.
• 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 is left after the question, the player must still wait until their next turn to officially guess that character.

Assume both players are highly skilled at choosing yes-or-no questions, so that they can always craft a question to potentially rule out (or in) any desired number of candidates. Also, both are playing to maximize their own probability of winning.

Let’s keep things (relatively) simple, and suppose that N = 4. How likely is it that the player who goes first will win?

Extra credit: If N is instead 24 (the number of characters in the original “Guess Who” game), now how likely is it that the player who goes first will win?

Extra extra credit: If N is instead 14, now how likely is it that the player who goes first will win?

Submit your answer

Solution to last week’s Riddler Express

Congratulations to 👏 Greg Ebersole 👏 of Strongsville, Ohio, winner of last week’s Riddler Express.

Last week, you were in a dark room and seated at a table with a deck of 52 cards stacked into a single pile. You also happened to know that exactly 13 cards in the pile were face up, while the others were all face down.

While you couldn’t see the cards, you could feel them and move them around — but you couldn’t tell by touch which were face up and which were face down.

How could you make two piles of cards that were guaranteed to have the same number of face-up cards?

While this was not an original puzzle, its cleverness made it worth sharing here.

Some solvers, like Michael Campbell, interpreted the question as asking you to make a larger number of piles, such that two of them had the same number of face-up cards. In other words, you didn’t have to know which two piles had the same number of face-up cards, just as long as two such piles existed.

With this interpretation, there are many possible solutions, one of which is to take three cards off the top of the deck and make each one its own pile. By the pigeonhole principle, at least two of these “piles” (of a single card) must have the same number of face-up cards, whether that’s zero or one.

But honestly, that wasn’t a very interesting interpretation of the problem. Instead, what if you had to split all 52 cards into exactly two piles? Could you somehow guarantee that the two piles had the same number of face-up cards?

Surprisingly, the answer turned out to be yes. And the key was the fact that you knew 13 cards in the deck were face-up to begin with.

A winning strategy was to take any 13 cards, move them to a separate pile, and flip that pile over. Let’s check this: Suppose that, among the 13 cards you took, x cards were face-up. The meant that the remaining 13−x face-up cards were left in the pile of 39 cards. So at this point, you have a pile of 39 cards, of which 13−x are face-up, and a pile of 13 cards, of which x are face-up.

And now for the pièce de résistance — if you flipped that pile of 13 cards over, how many cards would now be face-up? Well, right before the flip, x cards were face-up, and the other 13−x cards were face-down. So after the flip, those two numbers were swapped: x cards were face-down, and 13−x cards were face up. At this point, both the pile with 39 cards and the pile with 13 cards each had 13−x face-up cards. You had no way of knowing what x was, and so you didn’t know exactly how many cards were face-up in each pile. But you did know that the two piles had the same number of face-up cards.

Perhaps the coolest thing about this problem was that if you were willing to give up on the certainty you expected to have — the precise number of face-up cards in each pile — you could find the certainty the problem was asking for. Good stuff.

Solution to last week’s Riddler Classic

Congratulations to 👏 Q P Liu 👏 of Santa Cruz, California, winner of last week’s Riddler Classic.

Last week, you were at your local barbershop, where there were four barbers working simultaneously. Each haircut took exactly 15 minutes, and 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 — a quarter of the other customers held out for Tiffany, while no one held out for any of the other barbers.

One Friday morning, you arrived at the barber shop to see that all four barbers were cutting hair, and there was one customer waiting. You had no idea how far along any of the barbers were in their haircuts, and you didn’t know whether or not the customer in line would hold out for Tiffany.

What was your expected wait time for getting a haircut from Tiffany?

There were two cases to consider here: Either the customer in front of you was also waiting for Tiffany, with probability 1/4 (as stated in the problem), or they weren’t, with probability 3/4. If they were waiting for Tiffany, then your wait time was simply a matter of waiting out the current customer in her chair (which could take anywhere from zero to 15 minutes, for an average of 7.5 minutes), followed by that first customer in line (another 15 minutes). So one-fourth of the time, your average wait was 22.5 minutes.

But what about the other three-fourths of the time? Well, if Tiffany was the first of the four barbers to finish, then you were stuck waiting however long that took, plus another 15 minutes of the customer in line in front of you. But if Tiffany wasn’t the first to finish, then the customer in front of you would select a different barber, and as soon as Tiffany freed up you’d be getting your haircut.

Solver Benjamin Phillabaum reasoned (with some calculus that I’ll skip here) that if there were four barbers who were at random places within their respective 15-minute haircuts, on average, one barber would be done after three minutes, two barbers would be done after six minutes, three barbers would be done after nine minutes, and all four barbers would be done after 12 minutes. That meant that when Tiffany was the first to finish — which happened one-fourth of the time — you’d wait an average of 18 minutes (the three minutes it took her to finish, plus 15 minutes for the person in line ahead of you). And when Tiffany was not the first to finish — which happened the remaining three-fourths of the time — you’d wait an average of either six, nine or 12 minutes, which together average to nine minutes.

So when all was said and done, there was a one-in-four chance of waiting 22.5 minutes, a three-in-16 chance of waiting 18 minutes, and a nine-in-16 chance of waiting nine minutes. Rolling all these up meant, on average, you’d wait 14.0625 minutes.

Many solvers, like this week’s winner, Q P Liu and Stephen Penrice, devised creative algebraic approaches that didn’t use any calculus.

Others, meanwhile, investigated the distribution of wait times. How likely were you to wait one minute, two minutes, three minutes, etc.? Allen Gu found that you could wait anywhere from zero to 30 minutes, and the resulting distribution had a rather unusual shape:

Quoc Tran and Angela Zhou ran with this idea, looking at how this distribution changed depending on the number of barbers.

That is one funky-looking probability distribution!

And if that wasn’t enough, Angela further extended the problem by looking for the median length of time you’d be waiting for your haircut, rather than the average, when there were four barbers. Here’s the exact expression she found:

This worked out to about 13.75 minutes.

Anyway, if you’re bummed about how long you’ll have to wait for Tiffany, just think about all the riddles you could solve in 14.0625 minutes.

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.