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.
The Riddler Cheese Company is producing what are called “craft triples” — triangular slices of cheese whose side lengths are Pythagorean triples, when measured in inches.
However, the company’s slicing machine recently malfunctioned and produced a stock of square slices with side lengths of 5 inches. To salvage this situation, what is the greatest number of whole Pythagorean slices that can be made from each 5-inch square? (Note: You can only cut pieces out of the square. No melting or gluing pieces together!)
Extra credit: What is the smallest square of cheese such that 100 percent of the square can be partitioned into craft triples?
The solution to this Riddler Express can be found in the following column.
This week’s Classic is being served up by Jordan Ellenberg, whose new book, “Shape,” goes on sale on May 25.
One of the many geometers who appears in “Shape” is the great Paul ErdÐâs. In 1946, ErdÐâs himself posed a riddle about what are called “isosceles sets”: How many points can you place in d-dimensional space such that any three of them form an isosceles triangle?
In two dimensions, the largest isosceles set has exactly six points, with five forming the vertices of a regular pentagon and the sixth point in the middle. In three dimensions, the largest isosceles set has eight points; in four dimensions, the largest set has 11 points. And in dimensions higher than eight, no one knows what the largest isosceles sets might be!
But this week, Jordan is asking about what he calls anti-isosceles sets. Consider a N×N grid of points. What is the greatest subset of these N2 points such that no three of them form an isosceles triangle? (Note: Degenerate triangles, or triangles with zero area, do count as triangles here, as long as their three vertices are distinct.)
As shown below, the largest anti-isosceles set in a 2×2 grid has two points; for a 3×3 grid, the largest anti-isosceles set has four points. (Note: For both grids, there are multiple sets with these maximum numbers of points.)
How many points are in the largest anti-isosceles set for a 4×4 grid?
Extra credit: What about a 5×5 grid, a 6×6 grid, or even larger square grids? Can you find an expression (or bounds) for the size of the largest anti-isosceles set for the general N×N grid? (If you figure out anything about the general case, Jordan would love to hear about it!)
The solution to this Riddler Classic can be found in the following column.
Solution to last week’s Riddler Express
Congratulations to ÑÑâÐ Erik Voigt ÑÑâÐ of New York, winner of last week’s Riddler Express.
Last week, you and your infinitely many friends were sharing a cake, and you came up with two rather bizarre ways of splitting it.
For the first method, Friend 1 took half of the cake, Friend 2 took a third of what remained, Friend 3 took a quarter of what remained after Friend 2, Friend 4 took a fifth of what remained after Friend 3, and so on. After your infinitely many friends took their respective pieces, you got whatever was left.
For the second method, your friends decided to save you a little more of the take. This time around, Friend 1 took 1/22 (or one-quarter) of the cake, Friend 2 took 1/32 (or one-ninth) of what remained, Friend 3 took 1/42 of what remained after Friend 3, and so on. Again, after your infinitely many friends took their respective pieces, you got whatever is left.
How much of the cake did you get using each of these methods?
For both of these problems, a clever math move looked at how much of the cake remained after each friend took their portion. So for the first method, 1/2 remained after Friend 1. Friend 2 took 1/3 of what was left, meaning they left behind 2/3 of the 1/2, or 2/3 × 1/2 of the original cake. Similarly, after Friend 3, there was 3/4 · 2/3 · 1/2 of the cake left.
Reversing the order of the fractions in these products, the amount left after N friends took their pieces was 1/2 × 2/3 × 3/4 × 4/5 × 5/6 × 6/7 × … × N/(N+1). The denominator of each fraction canceled out with the numerator of the next fraction, so that the overall product was just 1/(N+1). In the limit of infinitely many friends, this product went to zero, meaning you got no cake using the first method!
The second method looked more promising. This time, after N friends took their respective pieces, the amount left was (22−1)/22 × (32−1)/32 × (42−1)/42 × … × [(N+1)2−1]/(N+1)2. At first, this might have seemed rather tricky to evaluate. However, as noted by solver Elaine H. of Tampa, Florida, differences of squares like a2−1 can always be factored as (a+1)(a−1).
Using this identity, we can rewrite that heftier product as (1×3)/(2×2) × (2×4)/(3×3) × (3×5)/(4×4) × (4×6)/(5×5) × … × [N×(N+2)]/[(N+1)×(N+1)]. This time around, the two factors in each denominator canceled out with factors in the numerators in both the preceding and following fractions. All that was left at the end was 1/2 × (N+2)/(N+1). In the limit of infinitely many friends, the fraction (N+2)/(N+1) approached 1, which meant you got exactly half the cake using the second method. That’s a half-decent portion right there!
For extra credit, you removed every other term from the second method’s product, leaving you with (22−1)/22 × (42−1)/42 × (62−1)/62 × (82−1)/82, and so on. Because terms were removed from the second product, this new product had to be greater than a half. It turned out this was the reciprocal of the Wallis product, which meant you got 2/ÑÑÑâ¹, or about 63.7 percent of the cake. For more on the Wallis product, and a way to prove it using complex analysis, check out Laurent Lessard’s write-up.
Solution to last week’s Riddler Classic
Congratulations to ÑÑâÐ Dallas Trinkle ÑÑâÐ of Urbana, Illinois, winner of last week’s Riddler Classic.
Last week, three students in puzzle submitter Matt Yeager’s fourth-grade class — Players A, B and C — were engaged in a game of veinte. In each round, players took turns saying numbers in order (Player A, then B, then C, then A again, etc.). The first player to go said the number “1.” Each number had to be either one, two, three or four more than the number said by the previous player. When someone said “20,” the round was over and the next person was eliminated, with the following person beginning the subsequent round. For example, if Player A said “20,” then Player B was eliminated, while Player C began the next round by saying “1.” At no point could anyone say a number greater than 20.
All three players wanted to be the winner (i.e., the only player remaining) after the two rounds. But if they realized they couldn’t win, they then prioritized making it to the second round.
Player A started things off by saying “1.” Which player won?
Solver Madeline Argent of Launceston, Tasmania, Australia, worked backwards, starting from what would happen after one of the players was eliminated. In the two-player variation, the second player could always win by saying the next multiple of 5. So the first player would say 1, after which the second player would say 5. Then, no matter what numbers the first player said next, the second player would say 10, followed by 15, followed by 20, at which point the second player would be victorious.
So knowing that the second player to say a number would always win between two players, what happened with three players?
Again, working backwards was key — this time, with higher numbers. Suppose Player A was the first to say 20. That would eliminate Player B, after which Player C would say 1 in a two-player game with A. In other words, A would win, followed by C in second place and B in third! Similarly, if B or C said 20, then they would win, respectively.
Next, what if A was the first to say 19? Then B would have no choice but to say 20, and so B would win. In fact, if A said any number between 16 and 19 (inclusive), then B would say 20 next and win.
You could continue working backwards in the following way: Suppose a player said a number k. That meant the next player could say k+1, k+2, k+3 or k+4. This next player would pick the optimal result for themselves among those four numbers so that they won (or if not, so that they made it to the next round of play). And so that was exactly the result that would happen if the original player said k. Proceeding backwards in this fashion gave you the resulting table:
|Number||When A says number||When B says number||When C says number|
For example, if Player B said the number 8, then the final result would be that C came in first, B came in second and A came in third.
Since you were told in the puzzle that Player A said 1, then to determine the eventual winner we need only look at the first cell in the table. Player B was the eventual winner, followed by A, who made it to the second round, and finally C, who was eliminated in the first round.
For extra credit, you looked at the four-player variation of the game, with Players A, B, C and D, all of whom wanted to make it through as many rounds of the game as possible. Again, Player A started things off by saying “1.” Now which player won?
Again, suppose Player A said 20 in the first round. Then Player B would be eliminated, and C would kick off a three-way contest among C, D and A. Based on the above analysis, we already know what happens in the three-player variation: The person who goes first comes in second, the person who goes second comes in first and the person who goes third comes in last. So if A said 20, the final results would be that D came in first, C came in second, A came in third and B came in fourth.
Filling out a table just as we did in the three-person variation yielded the following:
|Number||When A says number||When B says number||When C says number||When D says number|
Since A went first and said 1, the eventual winner of the four-player game was Player C, followed by B, D and A.
Solver Stefano Perfetti of Zurich, Switzerland, looked at variations with increasing numbers of players. I don’t know about you, but I don’t see much of a pattern in these results as the number of players increases.
But what I do see is that poor Player A doesn’t win when there are anywhere from two to 30 players. Player A’s best option is to play on their own. My sympathies to that fourth grader.
Want more riddles?
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.