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 the next column. Please wait until Monday to publicly share your answers! If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter or send me an email.
This past Wednesday I competed on “Jeopardy!” (No, this is not part of a fictional riddle. This really happened.) It was an incredible experience and a decade-long dream come true — even though I’m still haunted by the timing of that dang buzzer.
Heading into the Final Jeopardy! round, challenger Karen Morris was leading the way with $11,400. Returning champion Melissa Klapper had $8,700. Meanwhile, I was running in a not-too-distant third with $7,200. The Final Jeopardy! category was revealed as being “American Novelists,” and it was now time for all three of us to wager anywhere from $0 to the total amount we had for this one final clue.
Despite the dramatic swings in the match, my assessment was that all three of us were somewhat evenly matched in terms of knowledge. Having studied my opponents, I was also confident that Karen would wager enough money to cover the most aggressive wager from Melissa, and that Melissa would wager enough to cover my most aggressive wager.
With these assumptions, it was logical for me to keep my own wager small, since my only chance at winning was if both Karen and Melissa guessed incorrectly. Not particularly liking the category, I chose to wager $0. What was the maximum dollar amount I could have wagered without affecting my chances of winning? (Again, assume Karen wagered enough to cover Melissa and Melissa wagered enough to cover me.)
Extra credit: In the end, Karen wagered $6,001, Melissa wagered $8,000 and I wagered $0 (as I already said). Suppose all three of us had the same probability p of getting Final Jeopardy! correct, and that these three events were independent of one another. If the value of p is random and uniformly distributed between 0 and 1, what was my probability of winning the match?
We’ve had a number of combinatorial puzzles in recent weeks, but this submission from Jeremy Bailin was too timely to pass up:
It feels like there’s more parity in college basketball’s March Madness than ever, with lower-seeded teams advancing further in the tournaments at the expense of the favorites. This year’s Sweet 16 on the men’s side consists of two 1 seeds, two 2 seeds, two 3 seeds, two 4 seeds, a 5 seed, a 6 seed, a 7 seed, an 8 seed, a 9 seed and a 15 seed. This got Jeremy wondering about the likelihood that the Sweet 16 consists of exactly one of each seed: one 1 seed, one 2 seed, etc., up to one 16 seed.
Suppose each team is equally likely to win any given game. What are the chances that the Sweet 16 does indeed consist of one of each seed?
Extra credit: Looking at historical data on the men’s side, Jeremy estimates that the probability that seed A will defeat seed B is 0.5 + 0.033·(B−A). Using these probabilities, what are the chances that the Sweet 16 consists of one of each seed?
Solution to the last Riddler Express
Congratulations to ÑÐ±âÑÐ±Ã·âÐ±âÐ±â¤ÐÐ±â Henry Hannon ÑÐ±âÑÐ±Ã·âÐ±âÐ±â¤ÐÐ±â of Arlington, Massachusetts, winner of last week’s Riddler Express.
Last week, you were asked to analyze part of a musical composition. At one point in the piece, there was an improvisational passage where musicians were instructed to repeatedly play a sequence of eight notes, labeled 1 through 8. The shortest such sequence was 12345678.
However, musicians could also revert to previous notes, replaying certain subsequences for additional flair. More specifically:
- They always had to play the next note (i.e., adding 1 to the previous note), unless they reverted to a previous note.
- At no point could they play the same note twice in a row.
- Notes 1 and 8 — the first and last notes — could be played only once.
- They could only revert to a given note at most once.
- Once they reverted to a specific note, they couldn’t then revert to an earlier note in the sequence.
The following were examples of valid sequences:
- 12345678 (This was the shortest sequence.)
- 1234567-234567-34567-4567-567-678 (This was the longest sequence.)
I also offered examples of invalid sequences, for various reasons:
- 1245678 (This skipped note 3.)
- 12437568 (Some notes were out of order.)
- 12345-34678 (This skipped a note within a reversion, even though that note occurred earlier.)
- 1234-3456-345678 (This reverted to the same note twice.)
- 12345-456-2345678 (This reverted to an earlier note after reverting to a later one.)
- 12345-567-678 (This repeated a note twice in a row.)
- 123-1234567-5678 (This repeated note 1.)
- 1234-23456-5678-78 (This repeated note 8.)
How many different sequences of the eight notes were possible under these conditions?
At first, you might have been tempted to list out the valid sequences by hand. But after a hundred or two, that temptation probably wore off. (Shout out to Paige Kester, who listed all the sequences in a spreadsheet!)
The key to this puzzle was finding some way of uniquely identifying a sequence, using fewer digits to encode the entire sequence. Ideally, those fewer digits would make the task of counting the sequences more combinatorial and less manual.
For starters, you could ask whether the sequence reverts back to a given note. Does it revert back to 2, does it revert to 3, and so on, up to 7. The digits from 2 to 7 comprise six numbers, each of which could either have been reverted to or not. So you might have thought the answer was 26, or 64.
But it wasn’t. To see why, consider all the sequences that reverted back to 4 and only 4. Here were all three:
While they all reverted back to 4, you could distinguish them based on which number came immediately before the reversion to 4. This number had to be greater than 4 but less than 8, leaving three possibilities: 5, 6 and 7.
Looking across all the digits, there were five digits that could have immediately preceded a reversion to 2, four digits that could have preceded a 3, three digits that could have preceded a 4 (as we just said), two digits that could have preceded a 5 and one digit that could have preceded a 6. So there weren’t simply two possibilities for each digit (i.e., revert vs. don’t revert) — there were different amounts of possibilities for each digit. For example, the digit 2 had six possibilities for reversion: one case in which the sequence never reverted to 2 at all, and five cases where it did and had different preceding digits.
That meant the total number of valid sequences was 6·5·4·3·2, or 6!, which was 720. For the record, I accepted this answer.
But as it turned out, there was another interpretation of the puzzle that allowed for even more sequences. In the solution above, we assumed that the number before the reversion had to be greater than the number that was reverted to. But was that necessarily the case? Consider the sequence 1234567-23-5678. I admit this is a less aesthetically pleasing sequence — it feels like there should be a 4 between the second 3 and the second 5. But if you label that second 5 as a reversion, then technically this sequence satisfies all the criteria. (I never said that you had to revert to a note from the most recent subsequence.) Including these sorts of sequences as well, a few solvers counted up a grand total of 1,245 valid sequences — an answer I also accepted.
Solution to the last Riddler Classic
Congratulations to ÑÐ±âÑÐ±Ã·âÐ±âÐ±â¤ÐÐ±âAlex Klapheke ÑÐ±âÑÐ±Ã·âÐ±âÐ±â¤ÐÐ±â of Cambridge, Massachusetts, winner of last week’s Riddler Classic.
Brett plays poker with a large group of friends. With so many friends playing at the same time, Brett needs more than the 52 cards in a standard deck. This got Brett and his friends wondering about a deck with more than four suits.
Suppose you have a deck with more than four suits, but still 13 cards per suit. And further suppose that you’re playing a game of five-card stud — that is, each participant is dealt five cards that they can’t trade.
As the number of suits increases, the probability of each hand changes. With four suits, a straight is more likely than a full house (a three-of-a-kind and a different two-of-a-kind in the same hand). How many suits would the deck need so that a straight (not including a straight flush) is less likely than a full house?
For a standard deck with four suits, the probabilities for a straight and a full house aren’t exactly common knowledge, but they are readily available. Let’s briefly work through the calculations for four suits anyway, since they will be helpful when generalizing the number of suits.
To make a straight, you first had to choose the lowest card in the hand, which could have been anywhere from an ace to a 10. Then you had to assign one of the four suits to each of the five cards. In total, this gave you 10·45, or 10,240 hands. However, this also included the straight (and royal) flushes, of which there were 10 for each suit. That meant there were 10,200 straight hands with four suits. Generalizing to N suits, the 10·45 became 10·N5, and instead of subtracting 10·4 for straight flushes you had to subtract 10·N. This gave you a total of 10·(N5−N) straight hands with N suits. You could factor this polynomial a little further to get 10·N·(N2+1)·(N+1)·(N−1).
Meanwhile, to make a full house, you first had to choose among the 13 numbers for the three-of-a-kind and then among the 12 remaining numbers for the two-of-a-kind. Then you had to pick the three suits represented by the three-of-a-kind (4 choose 3 such ways) and the two suits represented by the two-of-a-kind (4 choose 2 such ways). So with four suits, there were 13·12·4·6, or 3,744 full house hands. Sure enough, with four suits, a full house was much less likely than a straight, since there were almost three times fewer hands resulting in a full house. Generalizing to N suits again, the 13 and the 12 stayed the same, but the 4 choose 3 became N choose 3 and the 4 choose 2 became N choose 2. This gave you a total of 13·N2·(N−1)2·(N−2).
From there, to find when the probability of a full house exceeded that of a straight, you had to solve the polynomial inequality 13·N2·(N−1)2·(N−2) > 10·N·(N2+1)·(N+1)·(N−1). This immediately reduced to 13·N·(N−1)·(N−2) > 10·(N2+1)·(N+1). Expanding and simplifying this inequality gave you 3N3−49N2+16−10 > 0, which turned out to be true when N was at least 17. In other words, you needed at least 17 suits for a full house to be more likely than a straight. (That’s a deck with 221 cards!)
Alex, this week’s winner, went further and plotted how these probabilities changed with the number of suits. Interestingly, there’s a nonzero asymptotic limit for both a straight and full house. Can you figure out what they are?
For extra credit, instead of five-card stud, you were asked to analyze seven-card stud. This time, you were dealt seven cards, among which you had to pick the best five-card hand. Again, how many suits would the deck have needed so that a straight (not including a straight flush) was less likely than a full house?
I’ll spare you the details, as this was a rather brutal exercise in combinatorial casework. For example, when determining the probability of a straight, you had to consider whether the two extra cards were duplicates of one of the other cards, of two of the other cards, or of none of the other cards. For each case, you had to exclude flushes. Anyway, in the end, a full house was more likely than a straight when you had at least eight suits in the deck.
Want more puzzles?
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 firstname.lastname@example.org.