The Riddler - Series on FiveThirtyEight

[TheRealJoeFish]

The Riddler Puzzle One: What's the Best Way to Drop a Smartphone?

Here's the very first Riddler puzzle, posted by Oliver Roeder on December 11, 2015:

[quote]Now, here’s this week’s inaugural Riddler, which comes to us from Laura Feiveson, an economist at the Federal Reserve’s Board of Governors:

You work for a tech firm developing the newest smartphone that supposedly can survive falls from great heights. Your firm wants to advertise the maximum height from which the phone can be dropped without breaking.

You are given two of the smartphones and access to a 100-story tower from which you can drop either phone from whatever story you want. If it doesn’t break when it falls, you can retrieve it and use it for future drops. But if it breaks, you don’t get a replacement phone.

Using the two phones, what is the minimum number of drops you need to ensure that you can determine exactly the highest story from which a dropped phone does not break? (Assume you know that it breaks when dropped from the very top.) What if, instead, the tower were 1,000 stories high?[quote]

I haven't looked at the answer, and I don't immediately see how to solve it, so here are my thoughts written out on how to get towards a solution:

---

Obviously, the naive manner of correctly determining this would be to drop it from Story 1 ("S1"), then, if it doesn't break, from S2, and so on, until you get to S100, where you know it will break. Clearly, by this method you will need 99 drops to *ensure* you know the highest story you can drop it from.

A slight improvement would be to drop it from every even-numbered floor in ascending order. If you drop it from S2, and it breaks, then drop the back-up phone from S1. If it doesn't break from S2, drop it from S4. And so on. You'll eventually hit a point where it's ok at S(n) but not S(n+2); then you just need to drop the back-up from S(n+1) to see if the highest is either S(n) or S(n+1). By that method, you'll need at most 50 drops (S2, S4 through possibly S98, and then the corresponding even one).

If you had an unlimited number of phones, the best strategy would be to do it by powers of 2: drop Phone 1 from S50; if it breaks, do the next one at S25, and if it doesn't, go up to S75. You'll eventually get a sequence like: S50 - Break, S25 - Ok, S37 - OK, S43 - Break, S 40 - Break, S39 - Break, S38 - Break. Then you know it's S37. So, if you have an unlimited number of phones, the number of drops you'd need would just be log_2 (100), rounded up, which is 7 (that is, the number of drops you'd need, x, would be whatever x is such that 2^x > number of stories).

The problem, of course, is that you don't have limited phones - just two. So, whatever you do with the first phone, you need to save the second phone for precision (that is, to fine-tune by counting up one story at a time).

---

So, based on all that, here's my first guess towards a solution. I'm not convinced this is the best method, only that it's a reasonable guess that I'll need to spend some time thinking about improving:

---

The first really solid strategy that appears is to do this:
Drop phone 1 from S10, and if it breaks, drop phone 2 from S1, then S2... until it breaks. If S10 doesn't break phone 1, drop it from S20, S30 and so on until it breaks and S(10*n), and then use phone 2 to count upwards from S(10*n - 9) to S(10*n - 1). The greatest number of drops you would need is [bold]eighteen[/bold], a maximum of nine drops for phone 1 (S10, S20... S90) and a maximum of nine drops for phone 2 (S(10*n - 9), S(10*n - 8)... S(10*n - 1)).

---

So, my question becomes, is that the best strategy, though? I'm going to think about it for a little bit. If you think you have the answer, and want to check it against mine, go ahead and post if yours is better! Or post anything else that comes to mind, variations on the problem, etc. I haven't addressed the 1000 story variation (although I think my solution above could be easily extended to that case), so if you have thoughts on that post them as well!