Before you stands a building with N-floors. On each floor there is an open window. You have two identical glass balls. If you were to drop a ball out the window onto the ground below, it might or might not break.
Your goal is to determine the highest floor for which dropping a ball out the window results in the ball not breaking. You can continue dropping the balls out the window as long as at least one of the balls remains intact.
Example: You go to floor 1 and drop a ball. It doesn't break so you go to floor 2 and try again. This time it breaks so you can no longer use that ball. But you still have 1 ball left so you continue until that ball is broken. By the time the second ball breaks, you should know the answer (if not then the strategy is invalid).
The question: What is the most efficient strategy for determining said highest floor? For this question, the most efficient strategy is the one which yields the smallest average number of total drops over all possible highest floors for the building.
Example continued: If the building has 100 floors, the strategy described would require X + 1 drops where X = the highest floor's number. Summing over all possible X we would get 5050 so the average is 50.5 drops.
Note: It is possible that a drop from floor 1 results in a broken ball. It is also possible that a drop from the top floor results in an unbroken ball.
An answer will only get a green check if it is both correct and clearly explained.
Special aside: This is my first time posting a puzzle here. I tried to be clear and concise but please let me know about anything I need to clarify.
Is this question a duplicate? There are certainly similarities between this and the puzzle proposed here: Dinosaur egg drop. However, that puzzle specifies the number of floors and total number of drops. My question asks to generalize the number of floors and does not specify the number of drops, only that you can continue as long as at least one glass ball is intact. Additionally, I do not see the correct answer to this puzzle on that puzzle. Some of the answers and reasoning there are definitely similar to what I am looking for but none of those would get the green check from me on this puzzle.
Answer
Strategy
My thoughts on the matter, (probably insufficient to earn the green check of approval).
The strategy I would employ would be to drop it every $\sqrt{n}$ floors and then starting from the floor above the last one it didn't break it at, drop it successively higher by one floor.
Why this strategy?
Well this means the searching for the location in both "halves" of the search are isomorphic, searching $\sqrt{n}$ spots for the first break. You expect to find your spot in ~$\sqrt{n}+1$ drops as the first search would take on average $\sqrt{n}/2 +1/2$ drops and the second search would also take $\sqrt{n}/2 +1/2$ drops.
Well I might come back to improve my answer but that is far as I am going for now.
Hypothesis: for $K$ balls and $n$ floors, ~ ${n^{1/k}} + log(n) term$
3 ball example with 100 floors: break it into segments of roughly $100^{1/3}$ floors, so 4.64, then cluster these by groups of roughly 4.64 groups.This is 21.5 floors per cluster. So this would take on average lets say, 3 guesses to find the right super cluster, 3 guesses to find the fight group of 4.64, then 3 guesses to find the exact spot for an approximation of 9 guesses expect for 3 balls 100 floors.
(worth noting using the first ball for a drop in the middle then using groups of 7 on the remaining chunks also seems like it would have an expected of 9)
No comments:
Post a Comment