1. Puzzle challenge:
It's not original, but it's an interesting puzzle:
Part A:
You're doing tolerance testing on new high-strength crystal balls, and
want to find out how much height they can be dropped from. You've been
given two orbs to work with, and you intend to drop them from floors
of an office building with a hundred floors (starting at floor 1, just
above the ground).
Naturally, once one of your orbs breaks, you can't reuse it. Both of
the glass orbs are manufactured to the same grade, so they will both
break above a certain height, and both won't break below that.
What is the minimum number of 'drop tests' you have to perform to
identify the top floor from which the glass orbs will survive a drop?
(Worst case scenario)
Part B:
Can you generalise this to f floors and b balls? What if f = 1000000
and b = 500?
--
MrTrick
2. Re: Puzzle challenge:
On 10 Aug 2004, at 11:24, Patrick Barnes wrote:
>
>
> It's not original, but it's an interesting puzzle:
>
> Part A:
> You're doing tolerance testing on new high-strength crystal balls, and
> want to find out how much height they can be dropped from. You've been
> given two orbs to work with, and you intend to drop them from floors
> of an office building with a hundred floors (starting at floor 1, just
> above the ground).
>
> Naturally, once one of your orbs breaks, you can't reuse it. Both of
> the glass orbs are manufactured to the same grade, so they will both
> break above a certain height, and both won't break below that.
>
> What is the minimum number of 'drop tests' you have to perform to
> identify the top floor from which the glass orbs will survive a drop?
> (Worst case scenario)
One.
Drop it from the ground floor and it breaks, that's the top floor from which the
orbs will survive (worst case).
> Part B:
> Can you generalise this to f floors and b balls? What if f = 1000000
> and b = 500?
Worst case if b is given, is one: b.
Kat
3. Re: Puzzle challenge:
> > It's not original, but it's an interesting puzzle:
> >
> > Part A:
> > You're doing tolerance testing on new high-strength crystal balls, and
> > want to find out how much height they can be dropped from. You've been
> > given two orbs to work with, and you intend to drop them from floors
> > of an office building with a hundred floors (starting at floor 1, just
> > above the ground).
> >
> > Naturally, once one of your orbs breaks, you can't reuse it. Both of
> > the glass orbs are manufactured to the same grade, so they will both
> > break above a certain height, and both won't break below that.
> >
> > What is the minimum number of 'drop tests' you have to perform to
> > identify the top floor from which the glass orbs will survive a drop?
> > (Worst case scenario)
>
> One.
> Drop it from the ground floor and it breaks, that's the top floor from which
> the
> orbs will survive (worst case).
>
> > Part B:
> > Can you generalise this to f floors and b balls? What if f = 1000000
> > and b = 500?
>
> Worst case if b is given, is one: b.
>
> Kat
If it breaks on floor 1 wouldnt that be the best case and not the worst?
At first I was thinking a binary search algo would work best, but its
possible with a low tolerance on both balls they will both break without
knowing the answer.
My personal guess (which is probably wrong heh) would be 51 drops for
worst case. Start at floor 2 and move up in increments of 2. When (if)
it breaks move down 1 floor to fill in the gap. So (IMO) the worst case
would be having to move 50 times up to floor 100 and if it breaks so you
have to go down one floor and check 99 to see if it breaks there.
If this is the answer, the number of balls would make a difference as you
could try other schemes (like binary search) to figure it out faster.
If you only have two balls the algo (if I am right mind you) the worst case
would always be <number of floors>/2 + 1.
If (like your second example) you have enough balls the binary search algo
would work better. For 1,000,000 floors you should only have to drop a ball
20 times or so to get your answer.
Don Phillips - aka Graebel
National Instruments
mailto: eunexus @ yahoo.com
4. Re: Puzzle challenge:
> > (Worst case scenario)
>
> One.
> Drop it from the ground floor and it breaks, that's the top floor from which
> the
> orbs will survive (worst case).
>
> > Part B:
> > Can you generalise this to f floors and b balls? What if f = 1000000
> > and b = 500?
>
> Worst case if b is given, is one: b.
>
> Kat
Im asleep =)
Nice one Kat... I just now got what you were saying. I did not take
into consideration on if worst case is from the workers side of things
(more floors) or the manufacturers (always first floor). Very clever.
Don Phillips - aka Graebel
National Instruments
mailto: eunexus @ yahoo.com
5. Re: Puzzle challenge:
> > One.
> > Drop it from the ground floor and it breaks, that's the top floor from which
> > the
> > orbs will survive (worst case).
Alright, from an algorithmic point of view, what's the most number of
times you'll have to drop something to determine the top survivable
floor. :oP
No more loopholes. The balls are resilient, and aren't weakened by
each drop. Either they break, or they are fine. Um, any other
loopholes I'll close too. So no thinking outside the box!
Unfortunately the pure binary search won't work, because if you guess
50 first, and it's under, you lose your first ball (it breaks), and if
you guess 25 second, and it's under, you lose your second ball... and
you have no more to test with...
It can be done in 19 tries like this (worst case):
With first ball: 10 20 30 40 50 60 70 80 90 100 *break first ball*
With second ball: 91 92 93 94 95 96 97 98 99
The second ball will break somewhere between 91 and 99, and you'll
know the top floor. If the ball breaks at 18, then it's: 1st: 10 20
2nd:11 12 13 14 15 16 17 18 , the above is the worst case.
So, 19 tries. I can do it in 14 though....14 or less tries, no matter
what floor it breaks on... (Guess how)
Haven't figured out a general case algorithm yet though....
--
MrTrick
6. Re: Puzzle challenge:
Mr Trick wrote <snip>
> So, 19 tries. I can do it in 14 though....14 or less tries, no matter
> what floor it breaks on... (Guess how)
> Haven't figured out a general case algorithm yet though....
First drop is on 14: if it breaks, then dropping on 1-13 (at worst 13 drops)
will find the right floor.
If it doesn't break on 14, second drop is on 27: if it breaks, then dropping
15-26 (at worst 12 drops) will find the right floor.
If it doesn't braek on 27, the third drop is on 39 . . .
The sequence of drops until the first ball breaks is 14, 27, 39, 50, 60, 69,
77, 84, 90, 95, 99
For b=2, the number of drops (d) for a given f is the smallest d such that
d*(d+1)/2 is greater than or equal to f.
Later I will try to generalize this.
-- Mike Nelson
7. Re: Puzzle challenge:
On Tue, 10 Aug 2004 18:35:55 +0000, Brian Broker <bkb at cnw.com> wrote:
>
>
> Patrick Barnes wrote:
> >
> >
> > > > One.
> > > > Drop it from the ground floor and it breaks, that's the top floor from
> > > > which the
> > > > orbs will survive (worst case).
> >
> > Alright, from an algorithmic point of view, what's the most number of
> > times you'll have to drop something to determine the top survivable
> > floor. :oP
> > No more loopholes. The balls are resilient, and aren't weakened by
> > each drop. Either they break, or they are fine. Um, any other
> > loopholes I'll close too. So no thinking outside the box!
>
> Is determining the terminal velocity of the orb thinking outside of the
> box? Because you can limit the search up to the floor from which t.v.
> is reached.
>
> -- Brian
>
Assume that the balls are dense enough that terminal velocity is much
faster than could be attained during a drop, even from a 100,000
storey building.
Back in the box *Whip-crack!* back I say...!
--
MrTrick
8. Re: Puzzle challenge:
----- Original Message -----
From: "Patrick Barnes" <mrtrick at gmail.com>
To: "Euphoria Mailing List" <EUforum at topica.com>
Sent: Monday, August 09, 2004 8:24 PM
Subject: Puzzle challenge:
>
>
> It's not original, but it's an interesting puzzle:
>
> Part A:
> You're doing tolerance testing on new high-strength crystal balls, and
> want to find out how much height they can be dropped from. You've been
> given two orbs to work with,
which may or may not be equivalent in size or density,
> and you intend to drop them from floors
> of an office building with a hundred floors (starting at floor 1, just
> above the ground).
>
> Naturally, once one of your orbs breaks, you can't reuse it. Both of
> the glass orbs are manufactured to the same grade,
but because they are not necessarily equal in size or density they would not
necessarily break on the same floor; even if they had an equal impact
tolerance, the actual impact of one could be greater than the other.
> so they will both
> break above a certain height, and both won't break below that.
If this were the case, they would have to be manufactured to
<i>different</i> grades to compensate for a higher impact velocity.
> What is the minimum number of 'drop tests' you have to perform to
> identify the top floor from which the glass orbs will survive a drop?
> (Worst case scenario)
>
> Part B:
> Can you generalise this to f floors and b balls? What if f = 1000000
> and b = 500?
Then you would be wasting a lot of time and money paying for balls only to
drop them a million times waiting for one to shatter.
> --
> MrTrick
>
>
>
>
9. Re: Puzzle challenge:
Just stop thinking outside the box...
The balls are exactly the same size and density.
They were both produced in a rapid prototyping machine surrounded by a
heisenberg's uncertainty inhibitor, so they are identical down to the
sub-atomic level. Even any radioactive elements of the ball have the
same half-life.
The balls are dropped in the same manner each time, onto sections of
adamantium pavement. Each drop, the pavement is replaced with a new
section, manufactured at tolerances so tight that it would not affect
the floor rating (because a floor is roughly 3-4 meters, any
differences in hardness would only affect the dropping distance by a
few micrometers.
The dropping mechanism has been engineered to the same tolerances, and
has an automated checking system with hardware interlocks to ensure
the balls are dropped exactly the same way each time.
You are being paid $300/hr by an eccentric billionare who wants to
know how strong his stock of *identical* glass orbs are.
On Wed, 11 Aug 2004 00:10:22 -0500, William Heimbigner
<icxcnika at hotpop.com> wrote:
>
>
> ----- Original Message -----
> From: "Patrick Barnes" <mrtrick at gmail.com>
> To: "Euphoria Mailing List" <EUforum at topica.com>
> Sent: Monday, August 09, 2004 8:24 PM
> Subject: Puzzle challenge:
>
> >
> > It's not original, but it's an interesting puzzle:
> >
> > Part A:
> > You're doing tolerance testing on new high-strength crystal balls, and
> > want to find out how much height they can be dropped from. You've been
> > given two orbs to work with,
> which may or may not be equivalent in size or density,
> > and you intend to drop them from floors
> > of an office building with a hundred floors (starting at floor 1, just
> > above the ground).
> >
> > Naturally, once one of your orbs breaks, you can't reuse it. Both of
> > the glass orbs are manufactured to the same grade,
> but because they are not necessarily equal in size or density they would not
> necessarily break on the same floor; even if they had an equal impact
> tolerance, the actual impact of one could be greater than the other.
> > so they will both
> > break above a certain height, and both won't break below that.
> If this were the case, they would have to be manufactured to
> <i>different</i> grades to compensate for a higher impact velocity.
> > What is the minimum number of 'drop tests' you have to perform to
> > identify the top floor from which the glass orbs will survive a drop?
> > (Worst case scenario)
> >
> > Part B:
> > Can you generalise this to f floors and b balls? What if f = 1000000
> > and b = 500?
> Then you would be wasting a lot of time and money paying for balls only to
> drop them a million times waiting for one to shatter.
>
>
> > --
> > MrTrick
> >
> >
>
>
>
--
MrTrick
