Finding minimum number of moves
vb
will break at a certain floor and both won't break below that floor.
The height of building is N and the floor at which both will break is
F(unknown). What is the minimum number of drops you need to perform to
find out what the most height(i.e F) the glass will survive.
I know the minimum moves required is square root of F. But i am not
able to get to the solution. Can somebody help.
Mara Guida
> We are given two glasses. We are guaranteed that both of the glasses
> will break at a certain floor and both won't break below that floor.
> The height of building is N and the floor at which both will break is
> F(unknown). What is the minimum number of drops you need to perform to
> find out what the most height(i.e F) the glass will survive.
Drop a glass from floor 1;
if it breaks, F is 0.
If it didn't break, drop it from floor 2;
if it breaks, F is 1.
If it didn't break, drop it from floor 3;
...
Number of drops: F+1
glasses destroyed: 1
glasses saved: 1
Did I misread you?
> I know the minimum moves required is square root of F. But i am not
> able to get to the solution. Can somebody help.
If you have an unlimited supply of glasses and can break them all, the
maximum number of drops required is log(N)/log(2) rounded up to the
nearest integer, which is very much smaller than square root of F (for
N = 30000 you need a maximum of 15 moves; 15*15 is 225).
How did you come up with "the minimum moves required is square root of
F"?
Gareth Owen
> vb wrote:
> > We are given two glasses. We are guaranteed that both of the glasses
> > will break at a certain floor and both won't break below that floor.
> > The height of building is N and the floor at which both will break is
> > F(unknown). What is the minimum number of drops you need to perform to
> > find out what the most height(i.e F) the glass will survive.
>
> Drop a glass from floor 1;
> if it breaks, F is 0.
NB : Start on floor M=0.
i) climb to floor M+2.
ii) drop first glass.
iiia) If it breaks M <= F < M +2, i.e. F = M or M+1.
Dropping the second glass from floor M+1 will tell you which.
iii b) If it doesn't break, go back to step (i).
Number of steps ~= F/2 + 1.
Simon Tatham
That's the best you can do with one glass, but you can do better by
using the second one.
> If you have an unlimited supply of glasses and can break them all, the
> maximum number of drops required is log(N)/log(2) rounded up to the
> nearest integer,
Yes, given an unlimited number of glasses, you can do even better;
but the problem says you have at most two to work with.
> How did you come up with "the minimum moves required is square root of
> F"?
Suppose that at some point you currently have K glasses, and you are
working with a range of N floors: that is, you know that the glass
will not break if dropped from some height x, and will break if
dropped from some height x+N. Let F(N,K) denote the maximum number
of drops required if the optimal strategy is employed from this
point.
Boundary conditions: F(1,K) equals zero for all K (because if you
know the glass doesn't break at some height x, and does break at
x+1, the problem is already solved), and F(N,1) equals N-1 for all N
(from your own argument above: the only way you can guarantee to
find the exact floor is to go up one floor at a time starting from
x, and there are N-1 floors to investigate between 0 and N).
For any other values of N and K, the optimal strategy must involve
dropping a glass from some height H. (Well, x+H where x is the known
safe height, but we can call that zero for notational purposes.) If
you drop a glass from height H and it breaks, you now have one fewer
glass, and a gap of H between the known-safe and known-unsafe
heights, so you need a further F(H,K-1) drops after this one.
Whereas if you drop a glass from height H and it _doesn't_ break,
you still have the same number of glasses, and the gap between
known-safe and known-unsafe is now N-H. Thus, _given_ a drop height
H, the maximum number of drops is 1 + max(F(H,K-1),F(N-H,K)). And
the optimal strategy is defined to be that which minimises this
value - so the correct initial drop height is whatever H minimises
the above.
Given this recurrence formula, you can draw up a table of N against
K and go through it deriving the value of F (and also H) in every
cell. Better still, you can get a computer program to do it, which
is much easier...
If you do this and correctly analyse the result, you find that the
optimum strategy with two glasses is to first define a set of floors
from which to drop the first glass. These floors are most easily
defined from the top of the building _downwards_ (although of course
we have to drop the glass from each of them in the opposite order):
they are N-1, N-3, N-6, N-10 and so on through the triangular
numbers. The point of doing this is that once the first glass
breaks, we have to drop the second glass from all floors in between
the breaking height and the previous non-breaking height; and
because the heights from which we drop the first glass get closer
and closer together as we go up, the more drops we have performed
with the first glass the fewer we need to do with the second, so
that the overall maximum number of drops required is no greater than
the number of drops we might have to make with the first glass.
Thus, the maximum number of drops required is the `triangular root'
of N: the smallest integer t such that the t-th triangular number
t(t+1)/2 is at least N. This is approximately proportional to the
square root of N.
--
Simon Tatham "_shin_, n. An ingenious device for
<ana...@pobox.com> finding tables and chairs in the dark."
Mara Guida
> Mara Guida <mara...@gmail.com> wrote:
> > How did you come up with "the minimum moves required is square root of
> > F"?
> Thus, the maximum number of drops required is the `triangular root'
> of N: the smallest integer t such that the t-th triangular number
> t(t+1)/2 is at least N. This is approximately proportional to the
> square root of N.
WOW!
Many many thanks for the detailed explanation.
dgates
The minimum number of moves is the square root of an unknown number? I
would think it would be more like 2 times the square root of N.
Let's say it's a 100-story building. You (more or less) try floors
10, 20, 30, 40, etc. until the first glass breaks. (Let's say at the
70th floor). Then you narrow down the exact floor by dropping the
next glass at 61, 62, 63, 64, etc. until it breaks.
You gain some extra efficiency by not counting exactly by 10s at thye
beginning. You can skip more floors at the beginning and less floors
at the end (to avoid ever having to use up your full 19 or 20 drops).
I don't know why, but I have a feeling the best strategy involves
dropping the first bottle at about 14 and the second bottle at about
26 or 27.
Gerard Schildberger
Yes, floors 14, 27, 39, 50, 60, 69, 78, 86, 93, 99, 100
for a total of ceiling[3*sqrt(N)/2], start at that floor - 1.
______________________________________________________________Gerard S.
Mark J. Tilford
tr(N) = (-1 + sqrt(8N+1)) / 2
= sqrt(2N + 1/4) - 1/2
--
------------------------
Mark Jeffrey Tilford
til...@ugcs.caltech.edu
Phil Carmody
> | I don't know why, but I have a feeling the best strategy involves
> | dropping the first bottle at about 14 and the second bottle at about
> | 26 or 27.
>
> Yes, floors 14, 27, 39, 50, 60, 69, 78, 86, 93, 99, 100
> for a total of ceiling[3*sqrt(N)/2], start at that floor - 1.
There must be a O(log(N)) answer as binary chop, which
is evidently not quite optimal is Theta(log(N)) and works.
Phil
--
What is it: is man only a blunder of God, or God only a blunder of man?
-- Friedrich Nietzsche (1844-1900), The Twilight of the Gods
Willem
) "Gerard Schildberger" <Gera...@rrt.net> writes:
)> | I don't know why, but I have a feeling the best strategy involves
)> | dropping the first bottle at about 14 and the second bottle at about
)> | 26 or 27.
)>
)> Yes, floors 14, 27, 39, 50, 60, 69, 78, 86, 93, 99, 100
)> for a total of ceiling[3*sqrt(N)/2], start at that floor - 1.
)
) There must be a O(log(N)) answer as binary chop, which
) is evidently not quite optimal is Theta(log(N)) and works.
No it doesn't.
If your second glass breaks, you have to have found the answer.
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
Phil Carmody
> Phil wrote:
> ) "Gerard Schildberger" <Gera...@rrt.net> writes:
> )> | I don't know why, but I have a feeling the best strategy involves
> )> | dropping the first bottle at about 14 and the second bottle at about
> )> | 26 or 27.
> )>
> )> Yes, floors 14, 27, 39, 50, 60, 69, 78, 86, 93, 99, 100
> )> for a total of ceiling[3*sqrt(N)/2], start at that floor - 1.
> )
> ) There must be a O(log(N)) answer as binary chop, which
> ) is evidently not quite optimal is Theta(log(N)) and works.
>
> No it doesn't.
> If your second glass breaks, you have to have found the answer.
Ah, I thought someone had generalised the issue to more glasses.
I must be halucinating.
So, reverse-engineering the question from the answer, the above
is the procedure with the best worst case behaviour.
Is it also the best mean case, assuming flat distribution of
floors? I'd be surprised, but then again, I am hallucinating!
Oliver Wong
"Phil Carmody" <thefatphi...@yahoo.co.uk> wrote in message
news:87psjuz...@nonospaz.fatphil.org...
> Willem <wil...@stack.nl> writes:
>> Phil wrote:
>> ) "Gerard Schildberger" <Gera...@rrt.net> writes:
>> )> | I don't know why, but I have a feeling the best strategy involves
>> )> | dropping the first bottle at about 14 and the second bottle at about
>> )> | 26 or 27.
>> )>
>> )> Yes, floors 14, 27, 39, 50, 60, 69, 78, 86, 93, 99, 100
>> )> for a total of ceiling[3*sqrt(N)/2], start at that floor - 1.
>> )
>> ) There must be a O(log(N)) answer as binary chop, which
>> ) is evidently not quite optimal is Theta(log(N)) and works.
>>
>> No it doesn't.
>> If your second glass breaks, you have to have found the answer.
>
> Ah, I thought someone had generalised the issue to more glasses.
>
> I must be halucinating.
Someone did do such a generalization, but you can't "simply" do binary
chop, because maybe you have fewer than log_2(N) balls. If you have more
than log_2(N), then binary chop is probably optimal, assuming a uniform
distribution of breaking heights for the ball.
>
> So, reverse-engineering the question from the answer, the above
> is the procedure with the best worst case behaviour.
>
> Is it also the best mean case, assuming flat distribution of
> floors? I'd be surprised, but then again, I am hallucinating!
It is if the balls could break at any floor with uniform probability.
- Oliver