I got a rather interesting problem to solve on my last job interview, lets see how /sci/ handles it.You got a 100 story building and two identical balls. When you drop the balls from some height, it will break. By dropping balls as few times as possible, how do you find the highest floor from which you can drop a ball without breaking it? How many times do you need to drop a ball in the worst case? If both balls break, you're done and you better have an answer.Pic from me personal albums, it's almost related.My results (but not solution) if you're interested: At the time, after being pushed a bit to find a better solution, I found one which requires at most eightteen drops. Later at home I discovered a (very similar) solution which only requires fourteen drops. Can you beat it?
my first guessstart at floor 10 and (assuming one ball hasn't already broken) move up by 10 floors at a timewhen it breaks, move up by 1 starting from n-9so, you go 10, no break, 20 no break, 30 break21, 22, 23, 24 until you have answer
well 17 is pretty easy:worst case is floor 10, 20, 30, 40, 50, 60, 70 ,80, 90, 81, 82, 83, 84, 85, 86, 87, 88 (at which point you know whether its 88 or 89)
>>4338998so, to get down to 14 rounds, do 15, 29, 42, 54, 61, 71, 80, 88, 95, 89, 90, 91, 92, 93. Theres a little leeway but not much, so it doesn't seem like it can really be improved
>>4339003indeed, 14 seems to be the best answer.
>>4338998But if it's not 88 it could still be 89 or 90, so that's 18.>>4339003You got it, but you start at 14 for the same reason as above. I suppose that's the best solution then.
>>4339003oopsits14, 27, 39, 50, 60, 69, 78, 85, 91, 96, 92, 93, 94, 95oh well
I'd first drop one from the top floor. The range of all possible heights is far bigger then the height of the building, so without extra information I would start there. If it doesn't break, you have the answer right away.Then I would do a binary search. Start at floor 25. If it breaks, to go floor 13. If it breaks, go to floor 38. Continue. So lets see:100, 50, 25, 13, 7, 4, 2, 1. That is how many drops it will take every time, 8 drops. Unless you are lucky on the first one.
>>4339021if it breaks on 100, and it breaks on 50, then you can no longer drop any more balls because you've broken them both
Follow a geometric series:1, 2, 4, 8, 16, 32, ...If the ball was to break at like 55 or something, then the window would be fairly clear so a decent approximation could be made.
Now what if there are 3 balls?
>>4338987SAGE TO A DISGUISED HOMEWORK THREAD
>>4339027Then do it in reverse.
>>4339030You can get it in 9.With 2 eggs and 14 drops you can uniquely determine 105 floors.
>>4339030Assuming you don't know whether it will break from floor 1, and assuming 1 ball, it takes n drops to tell with n floors. With 2 balls, you narrow it down with triangle numbers (approximately). You first drop at floor k, then 2k-1, then 3k-3, then 4k-6, etc. This means k drops, so you can do up to k^2-(k-1)k/2 = k^2/2 + k/2 floors. So, with 14 drops you can tell between up to 105 floors apart (and with 13 you can tell up to 78 floors apart, so 14 is indeed the minimum)
uh...start at the 50th floor and drop, if it doesn't break move one floor up at a time until it breaks, if it broke at the 50th floor start at the bottom and work up one floor at a time?...
Drop one from 50th floor. If it breaks, go down to 25th floor.If it stays intact, go to the 75th floor.Drop again, go up or down one half of the previous amount of stories depending on if the ball breaks or not.Seven drops.
>>4339049No, imagine that the floor it breaks at is 10. Then you will have broken it at floor 50, and at floor 25. You have no more balls to break.
