How Many Brackets Can You Bust?
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.
From Oscar Lanzi comes a matter of tricky triangular numbers:
Suppose you are adding up whole numbers in order. You start with 1, then add 2 to get 3. Then you add 3 to get 6. Then you add 4 to get 10, and so on.
If you keep going — adding larger and larger numbers in this fashion, and looking at the resulting sums — you might notice a few patterns among the last two digits. One such pattern is that no sum ever ends with the digits “23.” Meanwhile, some pairs of final digits are more common than others.
Which pairs of final digits are the most common? (Here, “23” is a distinct final pair of digits from “32.”)
From Lucas Fagan comes a buster of brains and brackets that’s just in time for March Madness:
Consider a single-elimination tournament with four teams that hold a definitive ranking — that is, one team is the best, another team is second-best and so on. In each game, the better team wins. When the tournament is complete, you know for certain which team is the best. However, you can’t make similar claims about the remaining teams.
Suppose the winning team is A, and it plays B in the first round. Meanwhile, the team that loses in the final is C, whose opponent in the first round is D. With this bracket, there are three possible rankings of teams from best to worst: A/B/C/D, A/C/B/D and A/C/D/B.
For this week’s puzzle, instead of four teams, consider a single-elimination tournament with eight teams. How many possible rankings of teams are possible for a given completed bracket?
Extra credit: Instead of eight teams, suppose there are 2N teams. In terms of N, how many possible rankings of teams are possible for a given completed bracket?
Solution to the last Riddler Express
Congratulations to 👏 Carl Cepuran 👏 of Glen Ellyn, Illinois, winner of last week’s Riddler Express.
In long-track speed skating’s mass start competition, points awarded at three intermediate sprints (laps 4, 8 and 12) and one final sprint (lap 16). The first three skaters to finish each intermediate sprint earn 3 points, 2 points and 1 point, respectively. For the final sprint, the first six skaters to cross the line respectively earn 60, 40, 20, 10, 6 and 3 points.
In the end, competitors are ranked by how many points they accumulated during the race. When skaters with the same point total, whoever crossed the finish line first is ranked higher.
Last week, a particular skating competition consisted of two semifinal heats, with eight skaters from each heat advancing to the final.
What was the highest possible point total for a skater who fails to advance to the final?
In other words, you had to find the highest possible score for a semifinalist who came in ninth. And to do that, you wanted to spread out the points awarded among the top nine semifinalists as much as possible.
A good place to start was to look at the total number of points awarded in a race. There were 6 points awarded at each of the three intermediate sprints and then a whopping 139 points at the final sprint. In total, that amounted to 157 points. If all of these points were shared among nine individuals, then they averaged about 17.4 points each.
Now three racers had to come in first, second and third in the final sprint, each earning more than that average and altogether accounting for 120 points. That left 37 points for places four through nine, who therefore averaged about 6.2 points each. If we assume the fourth place finisher in the final sprint also earned no other points beyond their 10 at the finish line, that left 27 points for the five individuals who came in fifth through ninth overall. These five averaged 5.4 points each, which meant ninth place overall could have no more than 5 points.
But to complete the riddle, you had to show that there really was a way for ninth place to earn 5 points. Here was one such way:
- The winners of the first intermediate sprint were A, B and C, in that order.
- The winners of the second intermediate sprint were again A, B and C, in that order.
- The winners of the third intermediate sprint were C, D and B, in that order.
- The fifth-place skater in the final sprint was E, and the sixth-place skater in the final sprint was D.
Here, A and E finished with 6 points, while B, C and D all finished with 5 points. Since ties were broken by time across the finish line, B or C came in ninth place with 5 points, which was indeed the maximum score for a skater who failed to advance to the final.
Solution to the last Riddler Classic
Congratulations to 👏 Gary M. Gerken 👏 of Littleton, Colorado, winner of last week’s Riddler Classic.
Last week, I noted the recent hubbub around packing smaller squares inside larger squares. But squares were so cliche. Instead of squares, you had to pack three ellipses with a major axis of length 2 and a minor axis of length 1 into a larger ellipse with the same aspect ratio.
What was the smallest such larger ellipse you could find? Specifically, how long was its major axis?
Packing squares was hard enough. Changing the geometry to ellipses only made things harder. So let’s start with some more intuitive arrangements of the smaller ellipses and see where it gets us.
A reasonable place to start was by stacking the three ellipses together along their minor axes. Here was that arrangement:
This packing looked pretty efficient (to me at least). The major axis of the bounding ellipse was a shade longer than 4.5.
However, it was possible to do quite a bit better. Stepping away from ellipses for a moment and returning to circles, the best way to pack three unit circles was when the larger circle had a radius 1+2/√3, as shown below:
Compressing all four of these circles in the same direction by a factor of two resulted in three smaller ellipses packed into a larger ellipse with a major axis of 2+4/√3, or approximately 4.31, which was already an improvement over the stacked arrangement.
But the riddle didn’t end there. In the image above, it was possible to get an even tighter packing by symmetrically sliding the two bottom ellipses around the top one. To convince yourself this was true, you could rotate the two bottom ellipses by 15 degrees in opposite directions. This resulted in quite a bit of slack, as shown below. The three smaller ellipses could even be moved closer together, further shrinking the larger ellipse.
Solver Peter Ji specified the geometry using two parameters: the angle by which the two bottom ellipses were symmetrically rotated and the distance between the centers of these two ellipses. For any pair of these values, he deterministically nestled the third small ellipse between them. Peter found that the tightest bounding ellipse had a major axis of approximately 3.87, as shown below:
For extra credit, instead of three smaller ellipses, you considered other numbers of ellipses. Solver Laurent Lessard found excellent (but not necessarily optimal) packings when there were between two and 10 smaller ellipses:
Finally, I wanted to give a shoutout to reader Josh Silverman, who packed ellipses into a circle not with fancy optimization software but with a gravity simulator:
Given the apparent difficulty of packing curved shapes into other curved shapes in just two dimensions, I will forgo asking readers to pack Cheerios in a fishbowl. Instead, that might be a fun experiment to try at home.
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.