Can You Switch A Digit?
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 Ben Weiss and David Butler comes a what is presumably Eleven’s favorite puzzle to think about in her sensory deprivation tank:
Anna loves multiples of 11, but her friend Jane is not quite so keen. One day, Anna is flipping idly through the yellow pages (remember those?), which is full of 10-digit numbers. She notices that every 10-digit number seems to have an interesting property: It is either a multiple of 11, or it can be made a multiple of 11 by changing a single digit. For example, there are several ways to make the 10-digit number 5551234567 into a multiple of 11, such as changing the first digit to 4.
This gets the two friends wondering: Does every counting number have this property? Either prove it’s true for every number, or find the smallest counting number that is not a multiple of 11 and cannot be made a multiple of 11 by changing one digit.
This week’s Classic may seem nonsensical at first. But surely there’s more to it …
You have an urn with an equal number of red balls and white balls, but you have no information about what that number might be. You draw 19 balls at random, without replacement, and you get eight red balls and 11 white balls. What is your best guess for the original number of balls (red and white) in the urn?
Solution to last week’s Riddler Express
Congratulations to 👏 Whit Rappole 👏 of Winchester, Massachusetts, winner of last week’s Riddler Express.
Last week, you enjoyed a brief stay at Riddler Hospital. Every day on a certain ward at the hospital, one patient was admitted who needed one day of treatment, one who needed two days and so on, up to seven days. Each patient remained in their own room for the duration of their stay.
You were a nurse who was assigned to a room at random on a particular day. What was the probability that the patient you saw in that room was still there the next day?
One (incorrect) approach was to assume that on any given day the hospital had an equal number of patients who stayed one day, two days and so on, up to seven days. If that had been the case, then the probability the patient would have been there the next day was the average of 0/1, 1/2, 2/3, 3/4, 4/5, 5/6 and 6/7. Each fraction corresponded to a patient staying a different number of days. For example, if a patient was staying seven days, then the probability they would be there the next day was 6/7 since there was only a one-in-seven chance that you happened to visit them on their very last day. The average of these seven fractions was 617/980, or about 63 percent. But as I said, that was not the answer, and a few readers fell into that trap.
The key to this puzzle was to realize that the ward couldn’t have had an equal number of patients who stayed different numbers of days. To see why, solver Adaline Filinovich considered the very first day, at which point there were seven patients. The next day, the patient who stayed one day departed and was replaced by another patient who stayed one day. But all the other patients remained, meaning there were two patients staying two, three, four, five, six and seven days.
At steady state — meaning the ward’s population was no longer changing from one day to the next — on any given day there was one patient staying one day, two patients staying two days and so on, up to seven patients staying seven days. That meant there were 28 total patients, and patients with longer hospital stays were more likely to be picked at random. Solver Kyle Giddon used a spreadsheet to help visualize all 28 of these patients:
To compute the correct answer, you had to multiply each of the aforementioned seven fractions by the corresponding probability of picking a patient who stayed that many days: 1/28·0/1 + 2/28·1/2 + 3/28·2/3 + … + 7/28·6/7. After canceling out the factors in each term, the answer was (1+2+3+4+5+6)/28, which simplified to 3/4, or 75 percent.
By the way, if instead of seven the longest stay had been N days, then the answer would similarly have been the sum of the numbers from 1 to N−1 divided by the sum of the numbers from 1 to N. This resulted in a nice and compact expression: (N−1)/(N+1).
Solution to last week’s Riddler Classic
Congratulations to 👏Simon Essig Aberg 👏 of Alamosa, Colorado, winner of last week’s Riddler Classic.
Last week, you were trying to catch a grasshopper on a balance beam that was 1 meter long. Every time you tried to catch it, it jumped to a random point along the interval between 20 centimeters left of its current position and 20 centimeters right of its current position.
If the grasshopper was within 20 centimeters of one of the edges, it didn’t jump off the edge. For example, if it was 10 centimeters from the left edge of the beam, then it randomly jumped to anywhere within 30 centimeters of that edge with equal probability (meaning it would have been twice as likely to jump right as it was to jump left).
After many, many failed attempts to catch the grasshopper, where was it most likely to be on the beam? Where was it least likely? And what was the ratio between these respective probabilities?
The fact that the grasshopper’s jumps were randomly selected from uniform probability distributions — rather than discrete steps left or right — made this puzzle extra challenging. To get a handle on what was going on, several solvers began by simulating the grasshopper. David Ding sampled 1,000 starting points along the beam and had each grasshopper jump 10 million (!) times. When David plotted where the grasshopper wound up, this is what he found:
It appeared that the grasshopper followed a trapezoidal probability distribution and was most likely to be in the middle 60 percent of the beam and least likely to be at the ends of the beam.
Other solvers took a different tack, assuming the beam was discrete rather than continuous. This was helpful for computationally solving the problem, since a continuous beam could be described as the limit in which the number of discrete points on the beam went to infinity. By having a beam with 21 discrete locations, one solver used a Markov chain to map out the grasshopper’s location after 100 jumps. Again, the same trapezoidal distribution emerged.
A few brave souls sought the precise solution for a continuous beam in the limit as the number of jumps went to infinity. Laurent Lessard modeled each jump as the convolution of a truncated uniform probability distribution with the previous probability distribution to find the next probability distribution. With each successive jump, this distribution approached the trapezoid:
For each of these approaches, solvers found that the probability density was twice as great along the middle 60 percent of the beam when compared to the ends of the beam.
While this factor of two was far from obvious, it made intuitive sense when you thought about where the grasshopper could have been jumping from in order to land at each point on the beam. In the middle of the beam, the grasshopper could have been coming from either direction (left or right), whereas at the left end of the beam the grasshopper could only have been coming from the right — i.e., half as many directions (and vice versa for the right end of the beam). But why was the final distribution piecewise linear, as opposed to something curvier? This was because the truncated uniform probability distribution for the next jump got “squished” near the ends of the beam, making the math work out quite nicely.
In any event, if you want to catch that grasshopper, you had best stick to the middle of the beam.
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.