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 Jenny Mitchell comes another great puzzle about soccer and/or football:
World Cup group play consists of eight groups, each with four teams. The four teams in a group all play each other once (for a total of six matches), earning three points for a win, one point for a draw and zero points for a loss.
After group play in a particular group, all four teams have different numbers of points. The first-place team has A points, the second-place team B points, the third place team C points and the last-place team D points. Find all possible quadruples (A, B, C, D).
Speaking of “football,” the Riddler Football Playoff (RFP) consists of four teams. Each team is assigned a random real number between 0 and 1, representing the “quality” of the team. If team A has quality a and team B has quality b, then the probability that team A will defeat team B in a game is a/(a+b).2
In the semifinal games of the playoff, the team with the highest quality (the “1 seed”) plays the team with the lowest quality (the “4 seed”), while the other two teams play each other as well. The two teams that win their respective semifinal games then play each other in the final.
On average, what is the quality of the RFP champion?
Solution to last week’s Riddler Express
Congratulations to ÑÐ±âÑÐ±Ã·âÐ±âÐ±â¤ÐÐ±â Pirmin Patel ÑÐ±âÑÐ±Ã·âÐ±âÐ±â¤ÐÐ±â of London, winner of last week’s Riddler Express.
Last week, Maryam was playing billiards on a 1 meter by 1 meter square table. She placed the ball in one of the corners, aiming to strike the ball so that it traveled as far as possible before hitting a wall for the third time. Note that the ball didn’t necessarily have to hit three different walls of the table.
You could assume that the ball traveled in a straight path and that it bounced off a wall as you’d expect.3 You could also assume that it was impossible for Maryam to hit the ball precisely in one of the corners of the table. Instead, it would have hit both sides that were adjacent to the corner.
What was the farthest the ball could have traveled before hitting a wall for the third time?
Several solvers, like David Ding and Emily Boyajian, analyzed the different directions in which the ball could be struck, then split these into cases and found the optimal path with trigonometry and coordinate geometry.
But, as noted by solver Jenny Mitchell, this puzzle was reminiscent of another one from almost a year ago, in which Amare the ant had to find the shortest path around a triangle. Unlike billiards, Amare could change direction at any point. To find the answer, a good strategy was to reflect the triangle every time Amare reached an edge. So let’s try a similar approach here.
Solver Alex Livingston reflected the square table across any wall the ball hit, as shown below:
The blue border in the bottom right of the figure were all the places the ball could hit the wall for the third time. So the question became: Which point on the blue border was farthest from the starting location in the top left?
In the diagram above, there were two such points, one of which is shown. (The other was located symmetrically across the diagonal.) To maximize the distance traveled, Maryam had to aim one-third along one of the opposing sides. The ball then ricocheted and hit a point two-thirds along the side opposite that one, and then finally hit the corner opposite from where the ball started. Yes, the precise corner itself counted as hitting two walls, but you could instead assume the ball hit very, very close to the corner and the result would have effectively been the same.
With the Pythagorean theorem, you found that the total distance traveled was √(32+12), or √10 — roughly 3.16 meters.
For extra credit, you had to find the farthest the ball could travel before hitting a wall for the Nth time. Again, by reflecting the square table every time the ball hit a wall, you could create a similar triangular diagram. Instead of going down 3 meters and across 1 meter, this time the longest path called for going down N meters and across 1 meter. By the Pythagorean theorem, this distance was √(N2+12).
By the way, a few solvers, like Ravi Fernando of Berkeley, California, made the connection between billiards and “Maryam” — in this case, Maryam Mirzakhani. Mirzakhani was Ravi’s pre-major advisor when he was a freshman at Stanford!
Solution to last week’s Riddler Classic
Congratulations to ÑÐ±âÑÐ±Ã·âÐ±âÐ±â¤ÐÐ±â Andrew Love, Jr. ÑÐ±âÑÐ±Ã·âÐ±âÐ±â¤ÐÐ±â of Columbia, Maryland, winner of last week’s Riddler Classic.
Last week, a certain hotel in Qatar was hosting 11 American fans and seven Dutch fans. Since no alcohol was available inside the stadiums, the fans spent the afternoon at the hotel bar before shuttle buses took them to a match. Then they haphazardly wrote their room numbers on a big board by the concierge desk.
To avoid any rowdiness between rival fans, shuttle bus drivers were instructed to ferry American and Dutch fans separately. To ensure this, a shuttle pulled up in front of the hotel, and its driver called out room numbers from the board, one by one at random. As long as they supported the same team, each fan climbed aboard the bus and their room number was erased. Once the driver called out the room number of a fan for the second team, the shuttle left with only the fans of the single team aboard. The next shuttle then pulled up and repeated the process.
What was the probability that the last shuttle ferried American fans?
Many readers thought the answer should have been proportional to the number of American fans. After all, if there were more American fans than Dutch fans, it made sense that it was more likely that the last fan to be picked up would have been American. If you looked at all 18 choose 7 ways the fans could have been ordered, the last fan was American in precisely 11/18 of them.
However, the answer was not 11/18. Why? Because every time a bus driver called a fan that was different from those they had previously called, that fan returned to the pool and wouldn’t necessarily have been called first by the next driver. If they had been, then the answer would indeed have been 11/18.
To find the correct answer, several solvers like Daniel Gershenson and Mike Donner used dynamic programming techniques, although these didn’t quite offer a satisfying explanation for what was going on.
Suppose there were a American fans and d Dutch fans, with both a and d greater than or equal to 1. Then one of three things could have happened when the next bus comes around:
- The bus picked up all a American fans.
- The bus picked up all d Dutch fans.
- The bus picked up less than a American fans or less than d Dutch fans, in which case there were new numbers of American or Dutch fans remaining, still both greater than 1.
While it was tempting to dig into the third case and work out all the possibilities, this wasn’t necessary. That was because only this whole transportation scenario had to end with one of the first two cases, with the penultimate bus picking up all the fans on one side, and the last bus picking up all the remaining fans on the other side.
So, how likely were these first two cases? With a+d fans, and (a+d) choose a total orderings, there was only one way to order them so that all a American fans came before all d Dutch fans. And there was also only one way to order them so that all d Dutch fans came before all a American fans. In other words, the first two cases were equally likely. That meant the penultimate bus was equally likely to transport American or Dutch fans, and the same went for the last bus. The probability that the last bus shuttled American fans was 50 percent.
For extra credit, you had to find the expected number of shuttle buses needed to ferry all 18 fans. At this point, cleverly reasoning about symmetry was a lot less helpful than dynamic programming. The answer turned out to be about 9.545 buses, which was tantalizingly close to how many buses you’d expect (9.556) if each bus instead first boarded the passenger the previous bus had refused to take.
In any case, while either group of fans was likely to board the last bus, the Dutch fans had the last laugh.
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 email@example.com.