How Fast Can You Make The Track?
Illustration by Guillaume Kurkdjian
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.
Riddler Express
From Bowen Kerins comes an opportunity to reclaim any marbles you may have lost:
Bill has four opaque bags, each of which has three marbles inside. Three of the bags contain two white marbles and one red marble, while the last bag contains three white marbles. The bags are otherwise indistinguishable.
Ted watches as Bill randomly selects a bag and reaches in without looking to grab two marbles without replacement. It so happens that both marbles are white. Bill is about to reach in and grab the last marble in that bag.
What is the probability that this marble is red?
Riddler Classic
This week’s Classic is sure to break your brachistochrone:
While passing the time at home one evening, you decide to set up a marble race course. No Teflon is spared, resulting in a track that is effectively frictionless.
The start and end of the track are 1 meter apart, and both positions are 10 centimeters off the floor. It’s up to you to design a speedy track. But the track must always be at floor level or higher — please don’t dig a tunnel through your floorboards.
What’s the fastest track you can design, and how long will it take the marble to complete the course?
Solution to the last Riddler Express
Congratulations to ÑбâÑб÷âбâбâ¤Ðбâ Michael Joyce ÑбâÑб÷âбâбâ¤Ðбâ of New Orleans, Louisiana, winner of last week’s Riddler Express.
Last week, you were adding up whole numbers in order. You started with 1, then added 2 to get 3. Then you added 3 to get 6. Then you added 4 to get 10, and so on.
If you kept going — adding larger and larger numbers in this fashion, and looking at the resulting sums — you might have noticed a few patterns among the last two digits. One such pattern was that no sum ever ended with the digits “23.” Meanwhile, some pairs of final digits were more common than others.
Which pairs of final digits were the most common? (Here, “23” was a distinct final pair of digits from “32.”)
Solver Nate Kinast was very practical and decided to compute the first million triangular numbers. Upon sorting them by their last two digits, a pattern emerged, as shown by Nate’s histogram:
We already said that no triangular number ended with the digits 23, but there were quite a few other pairs that never occurred as well. Of the 100 total two-digit pairs, only 44 of them appeared as the last two digits of triangular numbers. Among these 44, 40 of them each occurred for two percent of triangular numbers. But the last four pairs of digits occurred more frequently, each accounting for five percent of triangular numbers. These terminal digits were 03, 28, 53 and 78, the solution to last week’s puzzle.
How could you know that the pattern in the histogram continued, rather than some new behavior starting among very large triangular numbers? You knew this because — as observed by The Hewitt School Problem Solving And Problem Posing Class — the last two digits repeated themselves every 200 sums. To see why, consider the 200th triangular number, which was 200×201/2, or 20,100. This ended with two zeros, and you were effectively starting over again with the last two digits, adding 201, 202, etc. The 400th, 600th and 800th triangular numbers similarly ended with two zeros as the cycle started over again.
Solver Justin Ahmann approached the puzzle using modular arithmetic, analyzing the last two digits of triangular numbers modulo 4 and modulo 25. Modulo 4, the cycle was 1, 3, 2, 2, 3, 1, 0 and 0, which frankly wasn’t very interesting. Each of the four possible residues occurred with the same frequency. But modulo 25, the cycle was 1, 3, 6, 10, 15, 21, 3, 11, 20, 5, 16, 3, 16, 5, 20, 11, 3, 21, 15, 10, 6, 3, 1, 0 and 0. Here, each residue occurred twice, with the exception of 3, which occurred five times.2 That meant final digits congruent to 3 (mod 25) were more likely to occur, again resulting in 03, 28, 53 and 78 and simultaneously explaining why it was that these values differed by 25.
The puzzle’s submitter, Oscar Lanzi, noted the connection between triangular numbers and p-adics, and how this particularly relates to triangular numbers ending with 3 or 8.
Finally, Tom Keith looked at triangular numbers written in different bases. Tom identified a number of interesting patterns, such as the fact that triangular numbers exhibit every possible final digital digit if and only if the base is a power of 2.
Solution to the last Riddler Classic
Congratulations to ÑбâÑб÷âбâбâ¤Ðбâ Don Barkauskas ÑбâÑб÷âбâбâ¤Ðбâ of Carlsbad, California, winner of last week’s Riddler Classic.
Last week, you considered a single-elimination tournament with four teams that held a definitive ranking — that is, one team was the best, another team was second-best and so on. In each game, the better team won. When the tournament was complete, you knew for certain which team was the best. However, you couldn’t make similar claims about the remaining teams.
Suppose the winning team was A, and it played B in the first round. Meanwhile, the team that lost in the final was C, whose opponent in the first round was D. With this bracket, there were three possible rankings of teams from best to worst: A/B/C/D, A/C/B/D and A/C/D/B.
But instead of four teams, you had to consider a single-elimination tournament with eight teams. How many possible rankings of teams were possible for a given completed bracket?
If you tried listing these out by hand, you quickly became overwhelmed by all the possibilities. That’s why a number of solvers turned to their computers for assistance. With eight teams, there were 8! (or 40,320) rankings that were possible. Solver Jake Cuppels went through those 40,320 rankings and counted how many were compatible with a completed bracket with teams A through H. The answer turned out to be 315.
A number of solvers approached this puzzle analytically. In doing so, they effectively solved the extra credit, which had a tournament with 2N teams, and then plugged in N = 3 to solve the original puzzle.
Andrea Andenna and Dan Baker both found a recursive pattern as the bracket doubled in size. Andrea let F(N) be the number of possible rankings in a bracket with 2N teams. A bracket consisted of two halves with 2N−1 teams, which meant each half had F(N−1) possible rankings among its teams. The question then became how many ways you could merge the two halves into an overall ranking of 2N teams. One team had to be the overall winner. From there, you had 2N−1 choose 2N−1 ways to merge the remaining teams. This gave you the recursive formula F(N) = F(N−1)2 · (2N−1 choose 2N−1). Since we already knew F(2) = 3, the formula implied that F(3) = F(2)2 · (7 choose 4), or 315 — this week’s answer. You could even use this formula to compute F(4) = F(3)2 · (15 choose 8), which meant a bracket with 16 teams had a whopping 638,512,875 possible rankings!
A few solvers like Starvind used this recursive relationship to derive an explicit formula for F(N): (2N)!/22^N−1, which had a corresponding sequence on OEIS. According to Starvind, when N was 6 — that is, when there were 64 teams — the number of possible rankings exceeded the total number of atoms in the observable universe.
So if you really want to know how all the teams compare at the conclusion of March Madness this year, don’t hold your breath.
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 riddlercolumn@gmail.com.
