During a puzzle solving contest (among programmers), much like the one Bilbo and Gollum had, and Gollum… I mean one of the players poses a question like the following:
You have 2 breakable things (could be eggs, lightbulbs, etc) and you have to find the exact point in an integer range (height, speed, etc e.g. 100 ft drop) where they break with a limited number to tests (usually 20). Close is not good enough. The answer must be exact.
The first off-the-cuff answer is usually “binary search… I’d start at 50 …” at which point the person who posed the question says “Ok. Let’s say the first item breaks at 50. Now what?” You only have 19 tries left and 49 positions to check. It can’t be done that way.
The problem solver has to think a minute but comes back with something new, usually even spacing like “start at 20. If it breaks go by 1s. If it doesn’t break try 40.” at this point the questioner follows with “Ok. What if it breaks at 40?” You only have 18 tries left and 19 positions to check. Works for the first step but not for the nth.
Now the problem solver has something that almost works so they back down to 10. “start a 10, then 20, then 30. Worst case it breaks at 100 and you have to go by 1s from 91 to 99 to find out where.” This does in fact solve the problem but it isn’t optimal.
So how do we revise the problem to get a more optimal solution? Attach a motivation. If, like on a game show, you’re going to keep $1000 for every test you can save in the worst case could you make any money? If so how much?
After a while the problem solver hits upon the idea of a sliding window. “start at 20 then go 18 then 17 more…” this works. Consider:
20 (skip 18) 38 (skip 17) 55 (skip 16) 71 (skip 15) 86 (skip 14) 100 breaks!
87 88 89 90 91 92 93 94 95 96 97 98 99
19 tests in the worst case and the average case takes 20 so that’s $1000, thank you very much. But wait, what if you want to make money in the average case?
Hmm. So now the problem solver hits upon the idea to build in the profit from the beginning. “Let’s say I wan’t to make $1000 every time. That means I have to build the profit in to the number of tests. I’ll only give myself 19 from the beginning” Ho ho! now we’re on to something.
19 (skip 17) 36 (skip 16) 52 (skip 15) 67 (skip 14) 81 (skip 13) 94 breaks!
82 83 84 85 86 87 88 89 90 91 92 93
Check it. The problem solver makes a minimum of $1000. Now the problem solver gets excited and wants to do the same process again but reserving 2 tests… then 3 tests. etc until she finds the most profitable solution.
At this point the questioner refines the problem “Wait. This is taking too long. What if the range was a million and you could do 200000 tests?” Can you think of a faster way than going step by step?
The problem solver will likely suggest binary searching for the optimal number of tests to reserve. “So we know a sliding scale starting at 20 works. Try 10. That doesn’t make money in the worst case. So then try 15. etc.”
And that is quite good enough as far as solving this problem goes… as long as the range isn’t dynamic.
Now here’s the deal. A mathematician (or someone who remembers a couple of useful things from college math) can get an optimal solution for this problem even if the range is dynamic. Here’s how:
Start off with the observation that we’re simply shrinking the range at each step:
(n)+(n-1)+(n-2)+…+1 where the sum is less than or equal to 100
You may recall a story about Einstein being asked by his teacher to add up all the numbers between 1 and 100 in order to keep him busy. Naturally Einstein found a quick way to do it and we can use his equation
to optimize our solution. We want to pick a sufficiently small n so that the sum of the series either hits the target (100) exactly or barely goes over. This gives us the equation:
(n(n-1))/2 >= 100
multiply both sides by 2
(n(n-1)) >= 200
(n * n^2) >= 200
Recalling our exposure to Big-O notation we can observe that n^2 will far outweigh n for sufficiently large values on the right side of the equals so we can simplify to
n^2 >= 200
Take the square root of both sides to solve for n
n >= 14.14
floor (or round down) 14.14 to get 14 (and the smallest value that meets our needs) then check the result by plugging 14 back into the equation.
14 + 14^2 = 210
try one lower (because of the n+ part) to make sure
13 + 13^2 => 182
yep. 14 is the answer. Try it
14 (skip 12) 26 (skip 11) 37 (skip 10) 47 (skip 9) 56 (skip 8 ) 64 (skip 7) 71 (skip 6) 77 (skip 5) 82 (skip 4) 86 (skip 3) 89 (skip 2) 91 92 93 94 95 96 97 98 99 100
Hmm. In the worst case (100) it takes 21 tests. The problem is we didn’t build the cost of the tests into the equation. Let’s do that:
(n(n-1)) / 2 >= 100 + (n-profit)
n will always be larger than profit and we can probably further bound profit to at most n/2 so
(n + n^2)/2 >= 100 + 1/2n
n + n^2 >= 200 + n
n^2 >= 200
get 14.14 again and plug it in.
14^2 >= 200
196 >= 200
false. This means we have to increment n to 15… which we can also do by rounding up instead or rounding down when we take the square root, getting
225 >= 200
Based on our question we can also estimate the profit to be at most 1/2n or 7.5 steps. Try it:
15 (skip 13) 28 (skip 12) 40 (skip 11) 51 (skip 10) 61 (skip 9) 70 (skip 8 ) 78 (skip 7) 85 (skip 6) 91 (skip 5) 96 (skip 4) 100 break
97 98 99
The problem solver can pocket $5000 on average and $6000 in the case where the item breaks at 100.
There we have it, a quicker and more cost effective way to solve the problem for any range.