Testing Your Shock Absorber Prototype: Min Drops to Determine Breaking Height

[Gokul43201]

You are designing a type of shock absorber that protects delicate objects from jolts during transportation. To test your prototypes, to decided to find the maximum height from which a crytal vase wrapped in your absorber can be safely dropped. You get a step ladder with 40 steps and decide to drop the wrapped vase from different heights. If you are satisfied with an accuracy of one step spacing, and you are allowed to break only 2 vases for a prototype, what is the minimum number of drops needed to determine the breaking height ?

 

[Chen]

Starting with N = 1 (unless you want to take into consideration the possibility that your shock absorber won't even work from the first step), you drop the first vase from N+2 steps. If it doesn't break, you go to N+4 and repeat the process. If it does break, you drop the second vase from N+1 steps. If it doen't break, the answer is N+1. If it breaks again though, the minimum height is N.

But it can probably be done better...

 

[jcsd]

But N can be as high as 40 Chen.

I don't know if this is right answre but it's the sort of thing you should be looking at:drop it at height 20, from this you can deterrmiine N> 20 (if it doesn't break) or N <= 20 (if it does break). Now drop it at 30 or 10 steps dependnt on the whether it broke or not, etc. This strategy means that it will take a maximum of 6 tests determine the correct height.

 

[Chen]

No, N varies between 1 (or 0) and 38. Anyway, I didn't calculate the "minimum number of drops" because I don't quite understand that... the minimum number of drops depends on what the breaking height actually is.

And jcsd, you are only allowed to break 2 vases. So what do you do when one breaks from 20 steps, and the other one breaks at 10 steps?

 

[jcsd]

No, N varies between 1 (or 0) and 38. Anyway, I didn't calculate the "minimum number of drops" because I don't quite understand that... the minimum number of drops depends on what the breaking height actually is.

And jcsd, you are only allowed to break 2 vases. So what do you do when one breaks from 20 steps, and the other one breaks at 10 steps?

yep your right I din't read it properly. In that case tho' you still wnat to partion the steps by test drops.

 

[verty]

Here is how I reason it.

If the breaking height is H, then the minimum number of drops is (H/2 + 1).

You will drop it progressively higher at intervals or two steps until it breaks, and then use the last drop to determine which step of the final interval is the correct one.

This can be generalised as follows:
H: breaking height
D: allowed drops
Formula = H/(2^(D-1)) + D - 1

I hope I didn't misunderstand the question.

 

[Njorl]

I can gauge that vase in 6 drops.


I am assuming the vase might break at step one.

start at 8

-increment by 8 if it survives, and repeat until it survives 32

-decrement by 5 if it does not

-- if second vase survives, try again at +2 if this works, just call it one better and quit

--if second vase breaks, call it 2 worse and quit.


If you get to 32 ok, jump to 37,
-if it survives, call it 39 and quit
-if it fails, do 35
--if it breaks, call it 33
--if it survives, call it 35

6 drops is the most you need to do.

Njorl

 

[Njorl]

Actually, there are more wauys to do it in 6 and be sure of getting it.

 

[Njorl]

I just got it down to 5.

first drops,
12,22,30,36,38

if it breaks at 12 try:
3,6,9

if it breaks at 22 try:
15,18,20

if it breaks at 30, try:
25,28

if it breaks at 36, try:
33,36

If it breaks or survives at 38, you don't need another drop

Njorl

 

[Gokul43201]

I can gauge that vase in 6 drops.


I am assuming the vase might break at step one.

start at 8

-increment by 8 if it survives, and repeat until it survives 32

-decrement by 5 if it does not

-- if second vase survives, try again at +2 if this works, just call it one better and quit

--if second vase breaks, call it 2 worse and quit.


If you get to 32 ok, jump to 37,
-if it survives, call it 39 and quit
-if it fails, do 35
--if it breaks, call it 33
--if it survives, call it 35

6 drops is the most you need to do.

Njorl

I don't see how this works...

Consider the following cases :

1. So, let's start at 8 and let the vase break. Now you go to 3 and suppose it breaks again. Then you don't know if the lowest breaking step is 1, 2 or 3. So there's definitely a flaw in the 'decrement by 5' idea.

2. You get to 32 ok (4 drops) and jump to 37 (5th drop), where the vase breaks. then you take the second vase and drop it from 35 (6th drop) and that breaks too. You've run out of drops and the answer can still be 33, 34 or 35.

 

[Gokul43201]

No, N varies between 1 (or 0) and 38. Anyway, I didn't calculate the "minimum number of drops" because I don't quite understand that... the minimum number of drops depends on what the breaking height actually is.

You want to find the strategy that minimizes the number of drops for the worst case. For your strategy, the worst case would be if N=38 or 40, for which you will need 21 drops.

You CAN do better than 21.

 

[Gokul43201]

But N can be as high as 40 Chen.

I don't know if this is right answre but it's the sort of thing you should be looking at:drop it at height 20, from this you can deterrmiine N> 20 (if it doesn't break) or N <= 20 (if it does break). Now drop it at 30 or 10 steps dependnt on the whether it broke or not, etc. This strategy means that it will take a maximum of 6 tests determine the correct height.

Haha...the binary search ! Your computer doesn't crash if it misses twice, does it ?

 

[Njorl]

I don't see how this works...

Consider the following cases :

1. So, let's start at 8 and let the vase break. Now you go to 3 and suppose it breaks again. Then you don't know if the lowest breaking step is 1, 2 or 3. So there's definitely a flaw in the 'decrement by 5' idea.

2. You get to 32 ok (4 drops) and jump to 37 (5th drop), where the vase breaks. then you take the second vase and drop it from 35 (6th drop) and that breaks too. You've run out of drops and the answer can still be 33, 34 or 35.

You only need to get it within 1 right? Or does one step spacing not mean +/- one step?

Njorl

 

[Gokul43201]

You only need to get it within 1 right? Or does one step spacing not mean +/- one step?

Njorl

Sorry if I wasn't clear on this. You need to figure out the exact step.

What I meant by the "accuracy of 1 step height" statement was that the least count of measurement being 1 step was okay .

 

[Gokul43201]

3 days gone by...and the best solution so far requires 21 drops - optimal solution is near half this number.

HINT to a slightly (but useful) sub-optimal solution : "minimize the perimeter of a rectangle of fixed area."

HINT to optimal solution : apply a dynamic correction to solution from above hint.

 

[Njorl]

6 12 18 24 30 36
after break, step up from last unbroken by one
worst case is 39 or 40, 10 drops

Njorl

edited - argh! 35 takes 11!

 

[Njorl]

telescoping the first drops would make it better

9,17,24,30,35,38,40

then go by ones from the last safe drop

Njorl

 

[Njorl]

8 takes 9 drops
16 takes 9 drops
23 takes 9 drops
29 takes 9 drops
34 takes 9 drops
37 takes 8 drops
39 takes 8 drops
40 takes 7 drops

Njorl

 

[Gokul43201]

Nice one Njorl !

Hmm...were the hints too easy ?

Njorl with the winner !