8 replies to this topic

[bonanova]

Taking the light bulb puzzle up a few notches:

 

When dropped from the f^th floor of a building, Bonanova's Brilliant Lightbulbs uniformly will break, but not if dropped from a lower floor. You are tasked with determining f using a nearby 1000-story building. Formulate an efficient strategy for determining f, and then request only as many BBLs as are needed to carry it out, covering the strategy's worst case.

 

Here's one strategy:

 

Drop a BBL from randomly chosen floors.

Worst case requires 1000 drops.

Ask for 1000 BBLs.

 

But you can do better.

 

What's the number of BBL's needed to determine f with the fewest number of drops?

You may assume that a 1000-story building is tall enough for this task.

Edited by bonanova, 18 February 2013 - 11:35 PM.
Clearly state the strategy must be optimally efficient with respect to number of drops

[phil1882]

Spoiler for 1 bulb

drop it from the lowest floor. if it survives increment by 1. keep incrementing by 1 until it breaks.

Edited by phil1882, 18 February 2013 - 11:01 PM.

[bonanova]

Yes. Absolutely correct. And I did not ask the question that I intended to ask.  

[Where are the puzzle testers when you need them?]

 

Restate:

 

How many BBLs are needed to determine f with the fewest possible drops?

 

To be sure that I mean to say when I ask what I think I mean to ask, I'll break it down.

You have n bulbs; there is a strategy for determining f in the fewest drops.

 

Phil's answer is correct for n=1, and worst case it takes 1000 drops.

If you have 2 bulbs, there is a strategy for determining f with fewer than 1000 drops.

Given 3 bulbs, you could get f with even fewer drops.

At some point, say n_f, more bulbs won't reduce the number of needed drops.

 

What is n_f ?

 

_{I'll try to rescue the OP with an edit.}

[phaze]

Spoiler for Solution

no more than 10 as 2^10 = 1024

Floor = 512
Travel = 256
Repeat
start dropping from Floor
if it breaks go down Travel stairs
if it survives go up Travel stairs
Travel = roundDown(Travel/2)
if Travel is not 0 go to Repeat
Finished with 10 light bulbs or less

Maximum number of stairs climbed < 512

Edited by phaze, 19 February 2013 - 12:02 AM.

[bonanova]

Right on.

Use the elevator, make life easy.

[phil1882]

Spoiler for optimal solution, 8 bulbs.

 1   2   3   4   5   6   7    8    9
 1   1   1   1   1   1   1    1    1
 2   3   3   3   3   3   3    3    3
 3   6   7   7   7   7   7    7    7
 4  10  13  15  15  15  15   15   15  
 5  15  23  28  31  31  31   31   31
 6  21  38  51  59  63  63   63   63
 7  36  59  89 110 127 127  127  127
 8  45 104 148 199 237 255  255  255
 9  55 159 252 347 436 492  511  511
10  66 225 311 599 783 928 1003 1023

start at bulb-1 drop-1. (492 in this case.) if it breaks go to bulb-2 drop-1 (237.) if it doesn't, add 256.

[phil1882]

apologies some numbers wrong.

Spoiler for

 1   2   3   4   5   6   7    8    9
 1   1   1   1   1   1   1    1    1
 2   3   3   3   3   3   3    3    3
 3   6   7   7   7   7   7    7    7
 4  10  13  15  15  15  15   15   15  
 5  15  23  28  31  31  31   31   31
 6  21  38  51  59  63  63   63   63
 7  36  59  89 110 127 127  127  127
 8  45  95 148 199 237 255  255  255
 9  55 140 243 347 436 492  511  511
10  66 195 383 590 783 928 1003 1023

Edited by phil1882, 19 February 2013 - 03:25 PM.

[jamieg]

Spoiler for For n=2:

Maximum is 48 drops with 2 bulbs:
drop at floor 48. If bulb breaks, increments of 1 from floor 1 to floor 47 (max 48 if breaks at floor 47). If bulb survives first drop, go to floor 48+47=95 (2nd drop). If break, increments of 1 from 49 to 94 (max 48 if breaks at floor 93). If bulb survives at 95, go to floor 48+47+46=141. If breaks at 141 (third drop), incremental from 96 to 140 (max 48 if breaks at floor 140).
Note that the pattern will get you to 48+47+46+45+...+3+2+1, which is overkill (sum=1035), but starting at 47 won't get you to 1000 floors. So 48 is our magic number.

As far as extrapolating for future steps, my instinct would be to do a similar procedure for n=3, where, if the bulb breaks (eg) at 48, then you go to floor 10, then if break incremental; if not, floor 10+9=19, etc etc, which will have a max of 10 within the step, for a max of 11; however, 11 isn't our maximum because we know it can take 48 drops to get to the top floors. So there's some other way that takes these steps to make for even distribution regardless of the floor, e.g. floor 14^2, then floor 14^2+13^2, then 14^2+13^2+12^2, etc, and then a pattern within that following the n=2 system (N+(N-1)+(N-2)...+1). But I'll let someone else do the actual optimization and give all the glory to him/her/them.

Edited by jamieg, 20 February 2013 - 02:47 AM.

[BMAD]

Spoiler for statistics vs Math

] Maybe it is my statistical background as opposed to mathematics or maybe I am over thinking it but I don't think dropping one bulb off a floor is sufficient to verify and represent the whole collection. I would drop three. If the majority breaks then I would assume to be at a breakable level but if <2 break I wouldn't be able to make that assumption and thus try a higher level

Edited by BMAD, 20 February 2013 - 06:21 AM.