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-sized 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 (chosen at random) in next week’s column. If you need a hint, you can try asking me nicely on Twitter.
Riddler Express
Like last week’s, this week’s Riddler Express, from Brian Leary, stems from the world’s most puzzling dinner party:
Five couples attend a party. They’ve hugged each other and said their goodbyes, but before they leave, the 10 people arrange themselves in a straight line at random to take a photograph. (All possible lineups are equally likely.) What is the probability that no person in the line is standing next to his or her partner?
Riddler Classic
A coronation probability puzzle from Charles Steinhardt:
The childless King of Solitaria lives alone in his castle. Overly lonely, the king one day offers one lucky subject the chance to be prince or princess for a day. The loyal subjects leap at the opportunity, having heard tales of the opulent castle and decadent meals that will be lavished upon them. The subjects assemble on the village green, hoping to be chosen.
The winner is chosen through the following game. In the first round, every subject simultaneously chooses a random other subject on the green. (It’s possible, of course, that some subjects will be chosen by more than one other subject.) Everybody chosen is eliminated. (Not killed or anything, just sent back to their hovels.) In each successive round, the subjects who are still in contention simultaneously choose a random remaining subject, and again everybody chosen is eliminated. If there is eventually exactly one subject remaining at the end of a round, he or she wins and heads straight to the castle for fêting. However, it’s also possible that everybody could be eliminated in the last round, in which case nobody wins and the king remains alone. If the kingdom has a population of 56,000 (not including the king), is it more likely that a prince or princess will be crowned or that nobody will win?
Extra credit: How does the answer change for a kingdom of arbitrary size?
Solution to last week’s Riddler Express
Congratulations to ÑÑâÐ Leon Joseph ÑÑâÐ of Mesquite, Texas, winner of last week’s Express puzzle!
Last week’s problem asked about hugs at a dinner party. (The pregame party for this week’s Riddler Express!) A musician and her partner attend a party with four other couples. We know three things: Some of the attendees hugged one another, no attendees hugged themselves or their partners, and everyone who is not the musician hugged a different number of times. Because we know all that, we also know the musician’s partner must have engaged in four hugs.
Why? The nine partygoers who aren’t the musician hugged a different number of times, so they must have hugged zero, one, two … seven and eight times. We can start to pair people off from there. The person who hugged zero times must be in a couple with the person who hugged eight times, because otherwise the eight-hugger wouldn’t have had eight people to hug. With the eight-hugger and zero-hugger off the board, the same dynamic applies to the other couples. The seven-hugger must be in a relationship with the one-hugger, the six-hugger with the two-hugger, and so on. Therefore, the musician’s partner must have engaged in four hugs. (The musician herself must also have engaged in four hugs.)
Solution to last week’s Riddler Classic
Congratulations to ÑÑâÐ Neal Stangis ÑÑâÐ of Longmont, Colorado, winner of last week’s Classic puzzle!
Last week’s Classic asked you to find optimal strategies in a competitive map-coloring game, wherein two players take turns. One player, Allison, draws a new “country” with a simple closed curve on every turn, and the other player, Bob, follows by coloring in each new country, with the stipulation that bordering countries must be different colors. How many countries will Allison have to create to force Bob to use a sixth color? If they both play optimally, Allison will need to create eight countries.
Here’s an explanation, from the puzzle’s submitter, Dave Moran:
Allison will win by move eight if she plays optimally. The winning strategy is to draw the countries in a straight line, because it sets a nice trap for Bob later on. She should just keep drawing new countries going east, with each new country bordering only the one before, until Bob repeats a color. (If Allison were to draw five in a row and Bob were to color all five differently, then she would win by drawing Country 6 bordering the previous five. But he wouldn’t do that if he is playing optimally.) Once Bob repeats a color, Allison can force additional colors by drawing new countries that partially surround the existing countries, and having a repeated color means she can wrap all the way around one of those repeats while keeping the other country of that color in the exterior.
Dave provided this illustration of these cartographic contingencies:
Seth Cohen also arrived at an answer of eight, using the following configurations.
Laurent Lessard provides an excellent explanation of this problem and its relation to graph theory. Each map can be represented by a planar graph, which goes a long way toward simplifying the map drawings. He also arrived at an answer of eight countries and provided this graphical explanation:
Elsewhere in the puzzling world
- Fight the darkness with some daylight saving puzzles [Expii]
- A celestial problem from John Urschel [The Players’ Tribune]
- A fascinating marathon puzzle [The Guardian]
- From elsewhere in the world of intellectual pursuits: I’m covering the ongoing World Chess Championship here in New York. Come follow along! [FiveThirtyEight]
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.