Can You Make Room For Goats?
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 Matt Enlow comes a puzzle he has seen making the rounds over the years, especially in convenience stores:
I went to my local 7-Eleven and bought four items (not gas). 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 were $2.00 and $0.32, then their product would have been 0.64.)
What were the four prices?
From Quoc Tran comes a caprine conundrum:
A goat tower has 10 floors, each of which can accommodate a single goat. Ten goats approach the tower, and each goat has its own (random) preference of floor. Multiple goats can prefer the same floor.
One by one, each goat walks up the tower to its preferred room. If the floor is empty, the goat will make itself at home. But if the floor is already occupied by another goat, then it will keep going up until it finds the next empty floor, which it will occupy. But if it does not find any empty floors, the goat will be stuck on the roof of the tower.
What is the probability that all 10 goats will have their own floor, meaning no goat is left stranded on the roof of the tower?
Solution to last week’s Riddler Express
Congratulations to 👏 Anders Skjäl 👏 of Vaasa, Finland, winner of last week’s Riddler Express.
Last week, Anna and Jane were flipping through the yellow pages (remember those?), which was full of 10-digit numbers. They noticed that every 10-digit number seemed to have an interesting property: It was either a multiple of 11, or it could be made a multiple of 11 by changing a single digit. For example, there were several ways to make the 10-digit number 5,551,234,567 into a multiple of 11, such as changing the first digit to 4.
This got the two friends wondering: Did every counting number have this property? You had to either prove it was true for every number, or find the smallest counting number that was not a multiple of 11 and couldn’t be made a multiple of 11 by changing one digit.
While hunting for such numbers, many solvers started small. For example, every one-digit number could be made a multiple of 11 by simply changing its one digit to zero. Meanwhile, every two-digit number could be made a multiple of 11 by changing one of the digits so that it matched the other.
But when it came to three-digit numbers, things got more challenging. Solver Sanandan Swaminathan’s approach made use of the divisibility rule for 11: A number is a multiple of 11 if and only if the difference between the sums of alternating digits is a multiple of 11. (That sounds more complicated than it is.) For example, consider the number 3,190. Adding up the first and third digits gives you 3+9, or 12, while adding up the second and fourth digits gives you 1+0, or 1. The difference between these sums is 11 (i.e., a multiple of 11), which means 3,190 must also be a multiple of 11. You can use similar reasoning to show that 3,795 is also a multiple of 11. In this case, each sum is 12, which means their difference is zero, another multiple of 11.
Now, suppose that ABC was a three-digit number with the desired property. If A+C was less than 10, then changing B to A+C would make ABC a multiple of 11. At the same time, if A+C was anywhere between 11 and 18 (inclusive), then changing B to A+C−11 would also make ABC a multiple of 11. That meant A+C had to be exactly 10.
Next, let’s return to B. If B was 0, 1, 2 or 3, then we could have added B+1 to whichever digit, A or C, was smaller, making ABC a multiple of 11. And if B was 5, 6, 7, 8 or 9, then we could have subtracted 10−B from whichever digit, A or C, was larger, making ABC a multiple of 11. That meant B had to be 4, while A and C then had to be 5. The smallest such number that was neither a multiple of 11 nor could be made a multiple of 11 by changing one digit was 545.
Many solvers also found larger numbers that were not multiples of 11 and which could not be made multiples of 11 by changing one digit. Jonathan Sievers wrote code to find that the next few such numbers were 27,272, 1,818,181 and 636,363,636.
Solution to last week’s Riddler Classic
Congratulations to 👏Beau Baker 👏 of San Mateo, California, winner of last week’s Riddler Classic.
Last week, you had an urn with an equal number of red balls and white balls, but you had no information about what that number was. You drew 19 balls at random, without replacement, and you got eight red balls and 11 white balls. What was your best guess for the original number of balls (red and white) in the urn?
First off, several readers took issue with the idea that you could have absolutely no prior information about how many balls were in the urn. Surely, the urn had some finite size and each ball had non-zero size, which meant there had to be some maximum number of balls in the urn. But if you suspended your disbelief and followed the puzzle down the rabbit hole, it got really interesting.
Assuming no prior knowledge about the number of balls, a reasonable way to start solving would be to look at every number of balls 2N (N red and N white) and calculate how likely it would have been to have drawn 19 such that eight were red and 11 were white. If it was unlikely, then that value of 2N would have been a bad guess. The value of 2N that maximized this likelihood would have been your best guess — even if your probability of guessing correctly among infinitely many possibilities remained essentially zero.
Suppose the urn contained N red balls and N white balls. What was the probability of drawing A red balls and B white balls? The probability of first A red balls was N/(2N) × (N−1)/(2N−1) × (N−2)/(2N−2) × … × (N−A+1)/(2N−A+1). The probability of then drawing B white balls was N/(2N−A) × (N−1)/(2N−A−1) × (N−2)/(2N−A−2) × … × (N−B+1)/(2N−A−B+1). Multiplying these products together and taking advantage of factorial notation, we get N!/(N−A)! × N!/(N−B)! × (2N−A−B)!/(2N)!. But drawing all the reds and then all the whites was just one possible ordering. In total, there were A+B choose A, or (A+B)!/(A!B!), equally likely orderings. Adding these up gave a final expression of N!/(N−A)! × N!/(N−B)! × (2N−A−B)!/(2N)! × (A+B)!/(A!B!). (As noted by many solvers, including Lily Koffman, this could also be expressed using a hypergeometric distribution.)
At this point, you could plug in the values of A and B (8 and 11, respectively, although due to the symmetry in this problem it didn’t matter if you swapped the order). Solver Kyle Giddon plotted a graph of the likelihood as a function of N:
The first thing you might have noticed about this graph was that the likelihood was zero when there were fewer than 22 balls in the urn. That’s because it was impossible to pick 11 white balls if there were fewer than 11 white balls in the urn initially.
The next thing you might have noticed was that the maximum occurred when N was 17, meaning there were 34 balls in the urn (17 red and 17 white). And when you had 34 balls, the probability of getting eight red balls and 11 white balls among the first 19 picked was about 16.21 percent. In the limit as N went to infinity, this likelihood decreased to about 14.4 percent, which wasn’t much lower than the maximum. Again, this led to several readers objecting that the probability of having exactly 34 balls in the urn was zero in the absence of priors. But a 34 balls was still technically your best guess.
A few solvers, including Mark Girard, solved this puzzle for the general case when A red balls and B white balls were drawn. Interestingly, according to Mark, a singular maximum value only occurred when A+B was greater than (A−B)2. Otherwise, the likelihood increased with N, and you would have looked pretty foolish guessing that there were infinitely many balls in the urn.
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.