Saturday morning puzzle
You might have heard various variations of this problem before.
You have 2 ostrich eggs in your hand (fairly hard shells) and you are in front of a 50 story building. The basic challenge is to figure out which is the floor from and above which the eggs will break on impact to the ground when you drop them from a window of that floor. Of course, this can be done with only one egg. You start with first floor – if it does not break, go to second floor. And keep doing this till you find the floor where it does break. The minimum number of tries you will need to guarantee finding out that floor is 50. (Basically, in the worst case, you have to keep trying all the way to the top)
But you have 2 eggs. Now, the challenge is to find out the minimum number of tries with which you can guarantee finding out that threshold floor at or above which an egg will break (one try means one dropping of an egg). Needless to say, once an egg breaks, you cannot use it again.
25 ? Drop one from the 25th and go upward if it breaks or start at first floor if it doesn’t
Kenneth, I think we can do for less…
Indranath, wouldn’t n be 11 in your formula?
Rajib Roy n=9, series =45, n=10, series =55, n=11, series =66
We are looking to cross the value (50) which is 10 .. am I missing something?
sum of a series starting with n-1 is (n)(n-1)/2, right? For it to be >= 50, n=11, right? With n=11, the series is 55. There is a off by one error perhaps in your calculation? Otherwise the logic seems to be correct to me.
if you can explain how you came up with the series, I can try figuring out where the off by one error is happening.
Rajib Roy there are 2 hypothesis- 1. You can break the entire floors into equal parts (10,20,..50) and then try them from 10 onward and then when you have reached the level where it broke (say 30)- from there come up from 20 , 1 floor at a time – hence you need 11 tries
2. The next one is a bit different
Have to go out now – will explain the rest later
Ok
10 tries minimum – I leave the math to you guys – here is a link to visually represent the tries… https://docs.google.com/spreadsheets/d/18jtsyl8jWFN-M2GFgMw_NTcRvripFSE2y7gqtogDoR4
Philippe, did you get to 10 – which is the answer – by trial and error in spreadsheet or mathematical proof?
Philippe, got it. Mine is not as strong as yours…
Answer:
Step 1: Note that once you have established a floor (call it “B”) where the egg does not break and a floor (call it “A”) where the egg does break, after that your only option is to take the only egg left and start from B+1 and go sequentially up to A-1 till you realize which floor breaks the second egg. If the second egg does not break even in A-1, then A is the answer of course.
Step 2: Note that you cannot a priori come up with an arbitrary value for “B” since the egg might break in your first try. The only known value of “B” – where egg does not break is in your initial condition (Floor 0).
Step 3. Suppose the answer to the question is “n”. What would be your strategy for the first try? This is best understood if we take an actual value of “n”. Say, you knew the answer to the question “minimum tries required to establish the threshold floor in all cases” is 7. Well, your strategy for the first try will be Floor “7”. Why?
Case A:
If in Floor 7, the egg breaks, you know that you start sequentially from Floor 1 thru to Floor 6. If it does not break in Floor 6, you know Floor 7 is the answer. So in 7 tries you established which floor is the answer. (remember your first try led to a broken egg and then you went 1 thru 6)
BTW, if you tried in a higher floor – Floor 8, let’s say, you would need more than 7 tries if at Floor 6 the second egg did not break. You are done with all 7 tries but you are still note sure what happens in Floor 7.
If you tried a lower floor, you would have established the exact answer but never required all the 7 tries (same logic as above). So you are not maximizing your resources.
Case B:
What if in Floor 7, the egg did not break?
Well, now you have established “B” = 7. You have exactly the original problem as before except you can think of Floor 7 as your Floor 0, you have one LESS try and you have both eggs left.
Using same logic as before, your next stop would be Floor 13. (you have 6 tries left. So you will jump 6 floors). If the first one breaks on Floor 13, you basically try the next 5 tries thru Floor 8-12.
And what if it does not break? You obviously then go to the 18th floor since you have 5 tries left.
In essence, your strategy would be to go “n”, then “n+(n-1)”, then “n+(n-1)+(n-2)”…. to establish which is the threshold floor ASSUMING you knew what “n” was to begin with.
If you knew what n was to begin with, you know that the max floors you can deal with is the sum of the series n, n-1, n-2, …., 1 which is (n)(n+))/2 using above strategy.
So the question is what is the minimum value of n for which the above value crosses 50 (the original height of the building). If n is 9, the series adds up to 45. If it is 10, it adds up to 55.
So you will need minimum 10 tries to make sure you are covered for any threshold floor value 1 thru 50.
Hope you enjoyed it!