Welcome to The Riddler. Every week, I offer up a problem related to the things we hold dear around here — math, logic and probability, of course. These problems, puzzles and riddles come from lots of top-notch puzzle folks around the world, including you, the readers.
You’ll find this week’s puzzle below. Mull it on your commute, dissect it on your lunch break, and argue about it with your friends and lovers. When you’re ready, submit your answer using the form at the bottom! I’ll reveal the solution next week, and a randomly chosen correct submission will earn a hearty shoutout in this column. (UPDATE: Dec. 22, 11:51 a.m.: The solution is now available!) Important small print: If you want to be eligible for the shoutout, I need to receive your correct answer before midnight EST tonight. Speed is prized around here, but so is considered thought.
But before we get to the new puzzle, let’s dwell on last week’s! Congratulations to 👏 Chris McKitterick 👏 from Philadelphia, our inaugural big winner. You can find a full solution to the previous Riddler at the bottom of this post.
Now, here’s this week’s Riddler, which comes to us from Brian Galebach, an amateur mathematician from Columbia, Maryland:
You arrive at the beautiful Three Geysers National Park. You read a placard explaining that the three eponymous geysers — creatively named A, B and C — erupt at intervals of precisely two hours, four hours and six hours, respectively. However, you just got there, so you have no idea how the three eruptions are staggered. Assuming they each started erupting at some independently random point in history, what are the probabilities that A, B and C, respectively, will be the first to erupt after your arrival?
(UPDATE: Dec. 22, 11:51 a.m.): See the solution here!
Note: Because of holidays, The Riddler will run on Tuesday for the next two weeks (Dec. 22 and 29). Happy Holidays!
[googleapps domain=”docs” dir=”forms/d/1UhcWCasfq7-YLtizI5um6dZXnC2OtshvVz41SWpRn8c/viewform” query=”embedded=true” width=”760″ height=”1100″ /]
Now, here is the full solution to last week’s Riddler, concerning the most efficient way to drop smartphones from great heights, courtesy of Laura Feiveson. I am proud to report that 25.4 percent of you submitted correct answers:
For 100 stories, the smallest number of drops needed is 14. Here’s a strategy that does it: Drop phone A from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 for as long as it doesn’t break. When it does break, test the floors between the previous drop (where it didn’t break) and the current floor (where it just broke). To do this, go up one floor at a time with phone B until either it breaks or you reach the floor just below the one where A broke. For example, suppose that phone A broke when dropped from floor 39 (after having survived the two previous falls from floors 14 and 27). You would then take phone B and drop it from floor 28 and then move up one floor at a time until it broke. Suppose that you get to floor 38 without B breaking — then you know that floor 38 is the highest floor from which you can drop a phone without it breaking!
An important feature of this strategy is that the most drops you will need is 14 regardless of where phone A breaks. If phone A breaks with your first drop at floor 14, then you need at most an additional 13 drops from phone B to determine the “breaking floor” — that adds up to a maximum of 14 drops, one from phone A and 13 from phone B. But if instead phone A doesn’t break until floor 90, you will need only a maximum of five drops from phone B — again, a maximum of 14 drops, this time nine from phone A and five from phone B. The main intuition is that because the maximum number of drops you need is the same regardless of where A breaks, you can’t “improve” upon the strategy.
To generalize this strategy to more floors, it is useful to see the pattern in the sequence of floors from which you drop phone A: Start with 14, then add 13, then add 12, then add 11, etc. Specifically, the solution for 100 floors was 14 because 14 is the smallest number such that \(1+2+3+…+n\geq 100\). Math tells us that \(1+2+3+\ldots+n = n(n+1)/2\). So the solution to the problem with some number \(f\) floors really amounts to finding the smallest \(n\) such that \(n(n+1)/2 \geq f\). For the case of 1,000 floors, the solution is 45 drops. Note that the exponential nature of the series means that even though 1,000 is 10 times 100, you need only roughly three times the number of drops to find the “breaking floor.” For 10,000 floors, you would need to have only 141 drops.
Finally, one beautiful extension is to think about how many total drops you would need if you had three smartphones, rather than two. In fact, it is possible to generalize even more and to come up with a relatively simple formula that determines the number of drops you would need for \(m\) phones and \(f\) floors.