Time to post the solution to the marble problem from last time. First of all, lets just try some naive strategies. When I introduced the problem, I had suggested the idea of just moving up the floors one at a time until the marble broke. Since we have two marbles, we can try to do better by moving up two floors at a time. We try floors 2,4,6,8,10,... and when the marble breaks on floor k, we simply use the other marble to try floor k-1 and confirm which was the critical floor. This strategy is much less wasteful that the last one (at least it makes use of the second marble), and the worst case scenario is if the critical floor, N, is 99 or 100, in which case we need to try all the even floors (50 of them) plus floor 99 for a total of 51 tries.
Alright, if two floors at a time improved our position, lets try three. Now we will test floors 3,6,9,12,... and when the marble breaks on floor k, we try k-1 and k-2 to confirm. I suppose if we get to floor 99 and the marble doesn't break, we don't actually need to try floor 100, but whatever. The worst case scenario is if we go all the way to 99 and must do 97 and 98. In this case we did 3,6,9,12,...99 for 33 floors and 97 and 98 for a total of 35 tries.
So taking larger steps seems to be better, we could try something silly like 25 floors at a time and then your worst case is 27 (easy to confirm). It is pretty clear that you will get the optimal strategy of this form if you just do 10 at a time (the square root of 100), and the worst case is 19.
Now the next thing to notice is that if you were to make a bigger step at the beginning, you don't make your life any worse. In particular, if you start with floor 15 and then go 25,35,45,..95, then go back, the worst case won't be N=100 anymore (that would take only 11 tries), the worst case will be N=94 or 95 for a total of 18 floors (its one better than the last case because you basically skipped a set of 10).
This idea of skipping a bunch of floors at the beginning will only work so far, of course. If you try to move all the way up to 20, then if it breaks right away you must try all 20 initial floors. So we see that if the actual worst case scenario is that it takes M tries, then you cannot start on a floor higher than M (because if the critical floor N is M-1 you are in trouble). Next, you can move up another M-1 floors at most, because if you move up M more and N is 2M-1 then you will need M+1 total tries to find it. Clearly we must move up by M-1 floors to floor 2M-1. Next we can move up by M-2 floors at most. You can see what is happening here.
If the total number of floors is the Kth triangle number, then you can solve the problem most efficiently in K steps by moving up K floors then K-1 then K-2 and so on. The 13th triangle number is 91, so we cannot do more than 91 floors in 13 steps. Thus we can just treat our 100 floor building as a 105 floor building (the 14th triangle number) and use that solution.
skip to main |
skip to sidebar
Musings of a physicist, mostly on logic puzzles involving people wearing hats. However, I can't promise that I won't occasionally get sidetracked into ramblings on other math or physics.
6 comments:
I was wondering if this problem gets any additional interestingness if you solve it for n-marbles over k-floors?
I haven't worked it out, but I suspect for 3 marbles you just use the pyramidal numbers instead of triangle numbers (that is, the sums of triangle numbers). In general, you'll wind up using Pascals triangle, since that has the triangle and pyramidal numbers and so on. For k-floors, its not especially interesting, since you just wind up overshooting always anyway.
I thought n-marbles would be interesting because it like, makes the solution space much, much bigger. You have the opportunity for different kinds of solutions when you have more than one mistake (ie. your first choice would not dictate all subsequent choices).
So maybe for sufficient marbles and appropriate floors different classes of solutions would evolve presumably binary search (or other types of search) would come into existence for sufficient marbles because since with 100 floors you can identify the worst case in 6 or 7 marbles.
Off the top of my head, "binary search until you have 2 marbles left, then treat the stretch of floors remaining as a version of the k-floor original problem" I suspect is ideal, but haven't proved.
It is certainly not ideal. Heres the thing, the 2 marble case has a small decision space because there is only one strategy for the 1 marble case. But now there is only one strategy for the 2 marble case (the right one), so that specifies the strategy of the 3 marble case. You have to use sums of triangle numbers instead of sums of integers (=triangle numbers). For the 4 marble case you must use sums of sums of triangle numbers. It keeps going like that. Fortunately, Pascals triangle contains all of those sequences, so the problem just reduces to n choose m.
I'm actually certain of this. If you'd like, i'll put up a proof of it soon. Actually, I'll probably put up a proof of it anyway, cause its fun.
Come to think of it, its probably the case that if the number of marbles you have is large (not sure how to define that yet), the proper solution converges to the binary search algorithm.
I would both like to see the proof and exploration of the convergence to the binary search.
Yay.
Post a Comment