You are not logged in.
Pages: 1
continuing (finishing) my previous:
We're testing in blocks, in effect.
:
o 0-k1
o k1+1 - k1+k2
, etc.
Once we've finished the first block, we know that floors 1-k are no-break - and so that the break floor occurs above there. We're into the second block. k2 is analogous to k1 in its block.
But where, exactly, is k2?
We have now dropped one ball, so we can't take as many drops for this block as we did for the first - so let's try just one less.
Go up one from k1, and test the block from there to F, using no more than k-1 drops.
k2 = k1 + 1
This generates the series k1, k1+1, k1+2, ...
which has to sum to F.
Sum: k*(k+1)/2 + k*k*(k+1)/2
= (k+1)*(k+1)/2
so F = (k+1)^2/2
so k = sqrt(2F)
I've been working on an approach to presenting a solution that tries to make each step simple and easily held in the mind. It starts like this:
Let F be the number of floors, and k be the number of the floor that it's optimal to drop the first ball from.
Drop a ball from the kth floor
(We don't know what the value of k is yet; it's an unknown with only the property that we've set for it (it's the optimal first-drop floor).)
If the ball doesn't break, we still have two balls - and only F-k floors to cover.
(We've dropped a ball once so far.)
If it does break, we have k-1 floors left to test, with only one ball left to test them with.
And the only way to do that is to start at the bottom floor and test each floor above that successively until either it breaks or we get to the (k-1)th floor (we've tested the kth floor)
(We could just continue on up testing with the second ball - but testing only one floor at a time is not efficient enough for the optimal solution.)
State: 2 balls, F-k floors to test.
We'll climb up a few floors to do our next test drop -- but how many?
If we go up too much farther, we won't be able to test all the remaining floors below that with a single surviving ball - which violates a condition of our effort.
Looking over your solution again (Page 4), I realized that I don't, in fact, understand where the summation equation comes from. Would you please explain?
Thanks.
Yes, I agree that we should end up with a nice clean solution.
And it'd be nice to connect it up to the old problem statement, somehow.
In the LaTex tutorial, the exaample code should be in plain text -- but it's already been interpreted. (so you can't tell what to type to get the result)
Is there a switch for that that should be used on that page?
Thanks!
Don't worry about taking finite time to reply!
off-topic - but since I'm here:
How do you make the nice math characters that are in your first reply?
I used to be able to do them in Word, but never in a context like this one.
Thank you so much!
The seemingly obvious "try n+1" was new to me - and so, appreciated, even though it's not algebraic.
Yes, I'm wanting an algebraic solution.
Sadly, although I've found two in the past, trying for several days hasn't reproduced them - so I'm feeling old and useless.
The solution to the Ball-Drop Problem begins with the answer, and relies on it throughout. Although it's nice to see that, that's kinda cheating!
I'd like to see a simple (as possible) solution that doesn't require knowing the answer first!
(72 years old, BS in Pure Math from MIIT)
Pages: 1