Can You Keep Your Marbles?
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.
You and your team of cyclists are climbing a mountain with a constant gradient in the Tour de FiveThirtyEight. You make the climb single file, with one rider in front of the other. The first rider sets the tempo for the rest to follow — that is, until that first rider runs out of energy, or “cracks.” Upon cracking, a rider can no longer maintain the tempo and falls well behind any riders who still have some remaining energy.
When you begin the climb, there are eight riders on your team, and you start at the very back. The seven riders in front of you have exactly enough energy to make it up the entire climb, as long as they are not the first rider. Setting the tempo is hard work, and riding first in line is twice as exhausting as being one of the other riders.
At some point up the mountain, the first rider cracks. Then the next rider cracks, then the next. Eventually, the last rider in front of you cracks, leaving you to contend with the remaining portion of the mountain all on your own. What fraction of the mountain do you climb alone?
From Alec Stein, inspired by conversations with Jesse Zymet and Adam Greenberg, comes a puzzle that is sure to make you lose your marbles:
At the Riddler Marble Shop, there are four enormous bags of marbles for you to acquire. They are labeled “red,” “green,” “blue” and “assorted.” Being the purist that you are, you want to select two bags of marbles that are not assorted, and you’d settle for some combination of red, green or blue.
However, noticing your interest in the bags, the shopkeeper alerts you. “Buyer beware,” she warns. “Some jerk switched around the labels on all four bags. Right now, every single bag is incorrectly labeled.” To give you a chance of properly identifying the bags you would like, she has kindly allowed you to take two — and only two — marbles out of any of the bags, one at a time.
How can you guarantee that neither of the two bags you take is assorted?
Solution to last week’s Riddler Express
Congratulations to 👏 Steve Schaefer 👏 of Carlsbad, California, winner of last week’s Riddler Express.
Last week, you explored five-by-five Latin squares, grids with five rows and five columns where each row and column contains each number from 1 to 5 exactly once. It turned out that there were quite a few five-by-five Latin squares.
If you picked one of these squares at random, what was the probability that no corner contained a 1?
There were four corners to consider: two in the top row and two in the bottom row. So first, what was the probability that neither corner in the top row contained a 1? Of the five spaces in that row, two were corners. Since the 1 was equally likely to be in any of them, the probability it wasn’t in a corner was 3/5.
Next, what was the probability that the 1 wasn’t in a corner in the bottom row? Since this had to be a Latin square, you couldn’t have a 1 in the same column as the 1 in the top row. That left four remaining places, two of which were corners. So the probability there wasn’t a 1 in a corner was 2/4, or 1/2.
Putting this all together, the probability that no corner contained a 1 was (3/5)·(1/2), or 3/10.
Many solvers generalized this to the case of an N-by-N Latin square. The probability of not having a corner 1 in the top row was (N−2)/N. From there, the probability of not having a corner 1 in the bottom row was (N−3)/(N−1). Multiplying these together gave a total probability of [(N−2)(N−3)]/[(N)/(N−1)].
For extra credit, you had to find the probability that two of the four corners in the randomly chosen five-by-five Latin square had the same number. The probability of either pair of corners matching was 1/4. Then, to find the probability that at least one pair matched, you could add the probabilities of either pair matching and subtract the probability they both matched (since this had been double counted). Naively, you might have expected this to be 1/4 + 1/4 ﹣1/16, or 7/16. But this being the extra credit, and therefore trickier, this answer was wrong.
Why? As it turned out the probabilities of each pair matching weren’t independent. In other words, the probability that both corners had matching numbers wasn’t (1/4)·(1/4), or 1/16, but rather 1/28. Having one pair of matching corners meant the other pair of corners was less likely to match, since there were fewer possible overall arrangements. Solvers like Peter Ji confirmed this by writing code that checked every five-by-five Latin square.
When working with “Latin” squares, remember: Felicem solvendum!
Solution to last week’s Riddler Classic
Congratulations to 👏 Peter Ji 👏 of Madison, Wisconsin (already cited in last week’s Express), winner of last week’s Riddler Classic.
Last week, I had an unlabeled, six-sided die. I made a single mark on the middle of each face that was parallel to one pair of that face’s four edges.
How many unique ways were there for me to mark the die? (Note: If two ways could be rotated so that they appeared the same, then they were considered to be the same marking.)
The three-dimensional cube, as well as its many rotations, was rather hard to visualize. Nevertheless, a few solvers were able to do so. Q. P. Liu carefully counted up the number of unique ways you could mark the die, organized by whether the markings on opposite faces were parallel or perpendicular.
If the markings on opposite faces are all parallel to each other, then there was one way to mark it so that two pairs were parallel to each other and another way to mark it so that each pair was perpendicular to the two other pairs.
Next, if the two markings of each pair of opposite faces were perpendicular to each other, then there were two ways to mark the cube that were mirror images of each other. (Remember, while a rotation from one set of markings to another meant they were equivalent, the same was not true for reflections.)
When one pair of markings on opposite faces were parallel and the other two were perpendicular, there was one unique configuration. And when one pair was perpendicular and the other two were parallel, there were three unique configurations: (1) the parallel pairs were both also parallel to the faces with the perpendicular marks; (2) the parallel pairs were both perpendicular to the faces with the perpendicular marks; and (3) one parallel pair was parallel to and one parallel pair was perpendicular to the faces with the perpendicular marks.
In total, that meant there were eight unique ways to mark the die. In the (likely) event the descriptions of the eight configurations aren’t totally clear, here’s an animation showing all of them:
A few solvers, including Emma Knight, recalled their days of studying group theory, the study of algebraic groups along with their symmetries and operators. A particular theorem from group theory known as Burnside’s lemma was especially useful in solving this problem. Let G represent the group of rotations on the unit cube, while X is the set of 26, or 64, markings on the cube (many of which are equivalent by rotation).
Burnside’s lemma provides a formula for calculating the number of “orbits” — that is, the number of distinct sets of elements within X that can be reached via the elements of G (i.e., rotations). This number of orbits can be found by averaging (over all the elements of G) the number of elements of X that are unchanged by that particular element of G. For this particular problem, Burnside’s lemma confirmed that the number of orbits was indeed eight.
For extra credit, you had to consider the case where the markings on each face could not only be parallel to the edges of that face, but also along either of the face’s two diagonals. For this version of the puzzle, the rotation group G was the same, but X went from having 26 elements to now having 46, or 4,096, elements, since each face could now be marked in one of four ways. Applying Burnside’s lemma once more, Emma and others found that there were 224 unique ways to mark the die.
(I have a truly marvelous animation of these 224 unique markings which this column is too narrow to contain.)
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.