• 0

Lightbulb tester on PGH (puzzle growth hormone)

Question

Posted (edited) · Report post

Taking the up a few notches:

When dropped from the fth 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
Clearly state the strategy must be optimally efficient with respect to number of drops
0

Share this post


Link to post
Share on other sites

8 answers to this question

  • 0

Posted (edited) · Report post

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
0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

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

Edited by phil1882
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

[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 nf, more bulbs won't reduce the number of needed drops.

What is nf ?

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

Right on.

Use the elevator, make life easy. ;)

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

apologies some numbers wrong.

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
0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

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
0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

] 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
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.