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.
From Andrew Love comes a puzzle about planning ahead and resolving to get things done:
It’s the morning of Jan. 1, 2023, and you have a task you want to complete before the end of the year, on Dec. 31. The task is easily divisible into portions, so you always know exactly what fraction of the task is left.
Your initial plan is to do exactly 1/365 of the task every day. But then you think to yourself, “If I do 2/365 today, I can do a little less every day from now on.” And so, on Jan. 1, you would complete 2/365 of the task. On Jan. 2, 363/365 of the task remains with 364 days left to complete it, so you would do another 2/364 × 363/365 of the task.
If you continue in this fashion every day, dividing the remaining work by the remaining number of days in the year and doing twice that amount, when would you finish?
As the Royal Astronomer of Planet Xiddler, you wake up from a dream in which you measured the planet’s radius using a satellite. “How silly!” you think to yourself. “Satellites haven’t even been invented yet!” And so you and another astronomer set out to investigate the curvature of the planet.
The two of you climb two of the tallest towers on the planet, which happen to be in neighboring cities. You both travel 100 meters up each tower on a clear day. Due to the curvature of the planet, you can barely make each other out.
Next, your friend returns to the ground floor of their tower. How high up your tower must you be so that you can just barely make out your friend again?
Solution to last week’s Riddler Express
Congratulations to ÑÐ±âÑÐ±Ã·âÐ±âÐ±â¤ÐÐ±â Mike Strong ÑÐ±âÑÐ±Ã·âÐ±âÐ±â¤ÐÐ±â of Mechanicsburg, Pennsylvania, winner of last week’s Riddler Express.
Last week, I went to my local 7-Eleven and bought four items. The sum of the four prices was $7.11. A happy coincidence!
But what was even stranger was that the product of the four prices was also exactly 7.11, without any rounding. (When multiplying the prices, I dropped the dollar signs so that the units worked out and then multiplied their decimal values. For example, if the prices of two items had been $2.00 and $0.32, then their product would have been 0.64.)
What were the four prices?
The first part of this puzzle was setting up equations that represented the scenario. If the four prices were a, b, c and d, then you knew their sum was 7.11, i.e., a + b + c + d = 7.11. But what about their product? While it was true that a·b·c·d was equal to 7.11, this didn’t consider the fact that each price had to terminate in the hundredths place. For example, you couldn’t have a price of $1.234 — 7-Eleven doesn’t sell anything (other than gas) that doesn’t cost a whole number of pennies.
To get around this wrinkle, you could define the four prices as a corresponding whole number of pennies, A, B, C and D, where A = 100a, B = 100b, C = 100c and D = 100d. Adding these variables together, you now had A + B + C + D = 711. And multiplying them gave you A·B·C·D = 711,000,000. Since A, B, C and D were whole numbers, it was helpful to write their product in its prime factorization: 26·32·56·79. The problem was now splitting up these prime factors into four “bins” (one bin for each price) such that their sum wound up being 711.
From there, many solvers like Jenny Mitchell and Nicolás Villagrán used a computer to search through all the ways of splitting up the prime factors. But you could have solved this without a computer. You knew one of the four prices (let’s say A) had a prime factor of 79. Since all values had to be less than 711, A had to be 79, 158, 237, 316, 395, 474 or 632. If A was 632, the remaining three values had to have a sum of 79 and a product of 1,125,000. In other words, their arithmetic mean was about 26, and their geometric mean was about 104. However, for any set of positive real numbers,2 the arithmetic mean is always greater than the geometric mean. In other words, A could not have been 632. Nor could it have been 474 or 395. That left four possible values: 79, 158, 237 and 316.
From there, solver Gareth McCaughan looked at the factors of 5. If A had been 79, 158 or 237, then the remaining three values had to collectively contain six factors of 5 and a sum of 632, 553 or 474, respectively. Since none of these sums was a multiple of 5, at least one of the three remaining values didn’t have a factor of 5. To keep their sum at most 632, two of the values (say B and C) had to be multiples of 53, or 125. If B and C were both 125, then no values of A and D resulted in the right sum and product. The same occurred when B and C were 125 and 250, 125 and 375 or 250 and 250.
And that meant A had to be 316. The remaining three values had a sum of 395 and a product of 24·32·56. Since each value had to be a multiple of 5, dividing through by 5 gave a sum of 79 and a product of 24·32·53. One of these numbers had to be a multiple of 25, and it couldn’t be 50 or 75, which meant it was exactly 25. That meant the final two numbers (again, scaled down by a factor of 5) had a sum of 54 and a product of 720. Whether you figured this out by inspection or the quadratic formula, the two numbers were 24 and 30. Scaling everything up by a factor of 5 again gave you A = 316, B = 125, C = 120 and D = 150.
In the end, the four prices were $3.16, $1.25, $1.20 and $1.50. Getting there wound up being a fair bit of casework with some clever pruning, but again, no computer was required!
Solution to last week’s Riddler Classic
Congratulations to ÑÐ±âÑÐ±Ã·âÐ±âÐ±â¤ÐÐ±â Stephen Penrice ÑÐ±âÑÐ±Ã·âÐ±âÐ±â¤ÐÐ±â of Morristown, New Jersey, winner of last week’s Riddler Classic.
Last week, a goat tower had 10 floors, each of which could accommodate a single goat. Ten goats approached the tower, and each goat had its own (random) preference of floor. Multiple goats could prefer the same floor.
One by one, each goat walked up the tower to its preferred floor. If the floor was empty, the goat made itself at home. But if the floor was already occupied by another goat, then it kept going up until it found the next empty floor, which it occupied. But if it found no empty floors, the goat would have been stuck on the roof of the tower.
What was the probability that all 10 goats had their own floor, meaning no goat was left stranded on the roof of the tower?
First, let’s consider what could happen with fewer goats and fewer floors. With two goats and two floors, no goat would have been stranded if their preferences (in the order that they approached the tower) were 1/1, 1/2 and 2/1. But if they both preferred the second floor, then the second goat would have wound up on the roof. The probability of two goats on two floors was 3/4.
With three goats and three floors, and hence 27 possible sets of preferences, there were 16 sets that resulted in no goats on the roof: 1/1/1, 1/1/2, 1/1/3, 1/2/1, 1/2/2, 1/2/3, 1/3/1, 1/3/2, 2/1/1, 2/1/2, 2/1/3, 2/2/1, 2/3/1, 3/1/1, 3/1/2 or 3/2/1.
At this point, you probably recognized that the denominator of the probability for N goats was NN, which was all the ways they could prefer different floors. But the numerator wasn’t as clear, as noted by solver Emma Knight. When N was 2 the numerator was 3, and when N was 3 the numerator was 16. Emma computed that the numerators for the next two values of N were 125 and 1,296. It appeared the numerator was (N+1)N−1, which meant the probability of every goat having its own floor was (N+1)N−1/NN. Could this really be the case?
Indeed it was. Solvers Laurent Lessard, Mark Girard and others recognized that this puzzle was closely related to parking functions, which told you the numerator. As solver Al Shaheen wrote, “That’s no goat tower, that’s a GOAT PARKING LOT!”
Laurent discussed a proof that is credited to Henry Pollak from 1974. Suppose that instead of N floors, there were N+1, the last being the roof, and that goats could have prefered it to the other floors. That meant there were (N+1)N different ways the goats could have prefered to occupy these floors. Further suppose that if a goat unhappily wound up on the roof, it could circle back to the ground floor and start over. Under these conditions, all N+1 floors were equally likely to be unoccupied at the end, while an unoccupied roof implied that no goat had ever passed through the roof. (If you don’t believe me — or Pollak — you can check this yourself for smaller values of N like 2 or 3.) The parking function of N was then the number of ways the empty floor was never the roof, which was (N+1)N divided by N+1, or (N+1)N−1.
Finally, in the case of 10 goats and 10 floors, this probability was 119/1010, or precisely 23.57947691 percent. There was a roughly three-in-four chance that at least one goat was stranded on the roof of the tower. The poor things!
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.