|
So i lurk an awful lot these days and really enjoy the puzzle/maths homework questions that pop up from time to time, so thought i'd share one.
A friend got asked the following during a job interview for an actuarial position:
"Someone gives you two identical and supposedly unbreakable eggs. You have access to a 50 storey building. You want to test whether the eggs are unbreakable or not. What is the minimum number of drops of eggs out of windows to allow you to find the lowest floor (if it exists) that the eggs break on."
I'm pretty sure it's a (relatively) common problem, that you could just google, but it's a nice one to try to figure out.
I'll provide spoilered vague hints if requested
=====
Bonus question:
"You have a large cube, made up of 1000 smaller cubes (10x10x10). You break off the top layer all over the surface of the cube. How many do you have left?"
btw that's a very simple puzzle, but they wanted to see the thought process behind getting to your answer, and asked him to reason it out loud.
|
+ Show Spoiler +Well for the first one, I'd say one, because if you start with the top floor and you drop it and it doesn't break, then you know. I feel like that answer is a cop-out though...
And I have to study bio so I'll get back to you on the second one.
|
The second one seems to be 900 ice cubes
edit: whoops i misread the question
so ya its 8 ^3
|
"Someone gives you two identical and supposedly unbreakable eggs. You have access to a 50 storey building. You want to test whether the eggs are unbreakable or not. What is the minimum number of drops of eggs out of windows to allow you to find the lowest floor (if it exists) that the eggs break on."
One drop. If they are supposedly unbreakable and one of them breaks, I'll go find the someone who gave them to me and drop them off the 50 story building for being a liar, unless they tell me how tough they really are.
Bonus question - 8^3=512.
|
I'll reply unspoilered to ya gumbum just to clarify things for everyone else too
Well for the first one, I'd say one, because if you start with the top floor and you drop it and it doesn't break, then you know. I feel like that answer is a cop-out though...
sure, if you drop it off the top and it doesn't break then you did it in one drop, but what if it does? then all you know that it breaks dropped from somewhere between 1 and 50 floors. likewise, you could just get lucky and find the floor on your first try.
the question is at least how many drops do you need to do to always be guaranteed to find the exact floor it will break from.
|
#1
+ Show Spoiler + I would say it's 6ish unless gumbum8's answer is actually right...
you start at 25th floor I think, and then if it doesn't break you go up, if it breaks you go down to either 37 or 12, and etc keep dividing stuff in half like binary search or w.e
edit: wtf you only get 2 eggs? OH... I see um... I don't get the question. I mean it could always be one if you mean minimum... but do you mean the minimum in worst case scenario? Then you'd have to throw it like 26ish times.
you throw the first egg off the 25th floor, and then if it breaks, you start dropping the second egg from the first floor and go one up until it breaks, but if ti doesn't break you start dropping it off 26th and up floors one by one until it breaks.
so 26 is the worst case scenario situation I think.
#2
+ Show Spoiler + Eh well aren't you just left with a 8x8x8 cube? which is 512
|
Kau
Canada3500 Posts
Question 1 is 8? Similar to binary searching?
Question 2 is 1000 - 100 - 100 - 80 - 80 - 64 - 64 = 512
Edit: oh you get two eggs, then you need 26 drops because you can only go two floors at a time.
|
klarp
#1 - the answers not right. but more importantly - you only have 2 eggs. say you start at 25, and it breaks, and you go up to 37, and it breaks - then you're done. you only have 2 eggs
you will need to do maths to solve it
#2 yeah thats right. it was the logic they were looking for apparently. as in
+ Show Spoiler +that you realise that you end up with an 8x8x8 cube, instead of just trying to count the cubes you took off
|
Since you got only two eggs, the only way to be sure is to take the first egg, and drop it once every three floors, in ascending orders. Say
1 -> 4 -> 7 -> 10 ...
Eventually your first egg will break. Say it happend at 37. Then you drop the other egg at 35th floor to see if it also breaks. If it breaks, then 35th is the lowest floor that will break the egg. If it does not, then try again at 36th.
EDIT: OK I found a problem with my solution. I will fix it later.
|
The second one is certainly 512, not 900. It would be 900 if you only took off the first layer on a single side.
I don't get the first one. Maybe there's a shortcut I'm not imagining, but you'd have to start at the 1st floor and go up one at a time. The minimum would be one drop, if they break while dropping them from the first floor. If you started at the top and they broke, you would know that they will break from 50 stories but won't know what the minimum is--hence starting from the bottom.
Edit: Illu is smarter than I am.
|
On November 11 2009 02:07 MakkurtE wrote:klarp #1 - the answers not right. but more importantly - you only have 2 eggs. say you start at 25, and it breaks, and you go up to 37, and it breaks - then you're done. you only have 2 eggs you will need to do maths to solve it #2 yeah thats right. it was the logic they were looking for apparently. as in + Show Spoiler +that you realise that you end up with an 8x8x8 cube, instead of just trying to count the cubes you took off
got new answer for #1 in my original post!!! check it out
|
@illu
that's one way to do it, but theres a far faster way to do it, and also be just as sure. it's not a trick question btw.
|
+ Show Spoiler +10 drops I think + Show Spoiler +
Start at 10th floor, if it breaks drop second egg from first floor and work up to the 9th.
If it doesn't break, drop from the 19th, 27th, 34th, 40th, 45th, 49th
|
got new answer for #1 in my original post!!! check it out
it's the worst case scenario alright. as in the minimum to be sure of every floor, whether thats the 1st or the 50th. you're getting slightly warmer though, although {your answer] is way too high.
|
On November 11 2009 02:08 Biochemist wrote:
The second one is certainly 512, not 900. It would be 900 if you only took off the first layer on a single side.
I don't get the first one. Maybe there's a shortcut I'm not imagining, but you'd have to start at the 1st floor and go up one at a time. The minimum would be one drop, if they break while dropping them from the first floor. If you started at the top and they broke, you would know that they will break from 50 stories but won't know what the minimum is--hence starting from the bottom.
Ya I screwed up that question, I'm in class so I wasn't reading the question too carefully X.X
I think the first one the logic is:
- Drop it from the 50th floor
- If it breaks, drop it from the first floor
- If it doesn't break, you have an unbreakable egg
- If it breaks on the 1st floor, the first floor is the lowest floor
- If it doesn't break on the 1st floor, then you drop it from the 25th floor
- If it breaks on the 25th floor, go to the 13th or 12th floor
- If it doesn't break on the 25th floor, go to the 37th or the 38th floor
etc.
Or you could cheat, and you throw it on the ground and it breaks (because it is an egg)
|
@LiAIH4
+ Show Spoiler +gg, took me aaaaaages to work it out. 10 is absolutely optimal. actually optimal is like 9.5 drops when you solve the equations, but you have to round it up obviously
@oreoboi
you only have 2 eggs. once 2 break, you're done
|
It would take me 10 drops to be sure.
Dropping in this order (assuming no breakages):
10
19
27
34
40
45
48
|
Alright yeah you get an equation n + (n-1) + (n-2) + (n-3) +... + (n-k) = 50 and (n-k-1) + (n-k) = n
or something like that, you solve and you get approximate answer, then try around there and it turns out to be 10.
|
solution:
+ Show Spoiler +
x^2 + x - 2(floors)=0 will solve for 2 eggs and any number of floors
in this case optimal is 9.xxxx, but you can't drop an egg 9 and a half times - so 10.
for the answer to be a perfectly round number the number of floors has to be a triangular number
i love the elegance of the method to get to the equation more then anything else really
|
mine came out to be way different, but it gave a similar answer in the end =/ Since the approximations aren't exact there'd be a bunch of different equations that solve for this I think.
! Problem:
I remember solving this for so long, and I still dun remember if I actually finished it back when i was in high school:
For all integers 4x^2 + x = 3y^2 + y, prove that y-x is a perfect square.
|
#2
+ Show Spoiler +
#1
+ Show Spoiler +
(don't forget you have just two eggs, so you can't apply binary searching; suppose you take your SUPPOSEDLY unbreakable egg and drop it from the 25th floor, now you have one egg left and no clue what the critical floor is)
drop at floor f and it breaks, so you drop at f-2; if it breaks at f-2, you're done. if it doesn't break, you have to drop at f-1
drop at floor f and it doesn't break, drop at f+3
so you start from floor 3
so if they were unbreakable you would drop all 16 times to get to the 48th floor but because 3 goes into 50 with a remainder , you have to drop again at the 50th floor (if it were to break at the 50th, you would have to use the 18th drop on the 49th floor, but otherwise, it would take 17 drops)
if they are unbreakable, you have to drop 17 times to SAFELY verify that they are unbreakable; if you drop more than this, you're fine, because you would just be doing a linear evaluation like start at floor 1 and go to 50 (if the eggs' integrity isn't affected by the impacts). but if you drop fewer times than this, you get fucked up if they DO break like the people who want to do binary searching.
after you drop at 48, you don't have to drop at 49 before 50 which is why it doesn't take 50/3 + remainder drops (that would be 18)
it takes 17 drops because we don't KNOW that they're unbreakable, if we knew they were unbreakable it would only take 1 drop (at floor 50, but if your egg broke at floor 50, you would have to do a linear search and drop a max of 49 times to safely figure it out). we have to test it as though we didn't know, which is the above method. 17 drops.
|
+ Show Spoiler [Question #1] +The correct answer for the first problem should be 6. You start on the 25th floor and go up half the floors left if the egg doesn't break. At best case scenario, where the egg breaks only at the 50 floor or doesn't break at all, you would test 6 times.
25, 38, 44, 47, 49, 50
If the egg breaks at any point before the 50th floor, then you would have to start testing from the floor above the last floor that it didn't break from. But yeah, the least number of tests to find the floor which the egg breaks is 6.
Nevermind. Was only thinking about best case scenario.
+ Show Spoiler [Question #2] +People already got this one. It's 8^3, which is 512.
|
Question #1 revisited
+ Show Spoiler +stop trying to use binary searching. it's tantamount to saying "I know this egg is unbreakable so I will just drop it on the 50th floor so it only takes me 1 drop"
My 17 drop method is in fact not the most efficient (I retract any implications I made to that effect) - although it's miles better than the binary searching bullshit which isn't even valid. I see the 10 drop method now. That's really elegant, and I'm going to remember that.
|
@LiAIH4
i think ur rightbut ur order for dropping can be improved on. here is what i put
+ Show Spoiler +
10,19,27,34,40,45,48,50,49
or, if it breaks on 10
10,1,2,3,4,5,6,7,8,9
actually, i guess the best way to go would be
10,18,26,33,39,44,47,48,49,50
|
Edit: Oops, hit back too much and resubmitted old stuff.
Edit2: Looks like LiAIH4 has the right answer.
|
For all integers 4x^2 + x = 3y^2 + y
Are there any non zero solutions to that equation?
|
Question 1
I think everybody is over complicating this.
+ Show Spoiler +The answer is 2 drops. That is the minimum number you would need to find out at which floor it would break.
Example: Let us say the egg will break if you drop it off the 30th floor or higher. For your first attempt you just happen to drop it off the 30th floor. For your 2nd attempt, you go down one floor and drop it off the 29th floor. You now know that it will break on the 30th floor but no lower. Problem solved, 2 drops.
Alternatively, if the eggs really are unbreakable, you could figure that out with one drop off the 50th floor. In that case, the answer is 1 drop.
It won't work without fail obviously, but it accurately answers the question as given. Maybe I am that jerk who looks at the wording too hard though, idk.
Question 2
+ Show Spoiler +512, everybody already posted that one. 8x8x8 == 512
|
yes, you're reading it badly. so badly.
It won't work without fail obviously
|
On November 11 2009 07:04 MakkurtE wrote:yes, you're reading it badly. so badly.
The question never says it has to work 100% of the time, just the minimum number. Hence my statement that I might just be reading it too literally.
|
it also never said "if the first floor you randomly choose is the one the above breaking point" but don't let that stop ya
shine on you pedantic diamond
|
On November 11 2009 02:39 MakkurtE wrote:solution: + Show Spoiler +
x^2 + x - 2(floors)=0 will solve for 2 eggs and any number of floors
in this case optimal is 9.xxxx, but you can't drop an egg 9 and a half times - so 10.
for the answer to be a perfectly round number the number of floors has to be a triangular number
i love the elegance of the method to get to the equation more then anything else really
Could you explain how you arrived at the equation? I'm not seeing the method.
|
On November 11 2009 07:39 MakkurtE wrote:
it also never said "if the first floor you randomly choose is the one the above breaking point" but don't let that stop ya
shine on you pedantic diamond
no need to get uppity, makkurte, he's not wrong. the question should have been phrased better.
|
On November 11 2009 07:39 MakkurtE wrote:
it also never said "if the first floor you randomly choose is the one the above breaking point" but don't let that stop ya
shine on you pedantic diamond
I pointed out why my answer was probably flawed. I was very clear that my answer was just taking advantage of the wording. No need to try to use ridiculous extremes and sarcasm to point out what I already did.
Edit: Also I think your formula will not solve for any number of floors. Edit again after I actually do the math.
|
Tried to quote someone and their post was deleted.....
|
jeejee/bear - thats i know it's awkwardly worded, thats why i clarified it properly, several times. going back and picking at the original statement is pointless and tiresome
and lol, are you kidding me?
x^2 + x - 2(floors) = 0
x^2 + x - 2(10) = 0
x^2 + x - 20 = 0
(x+5)(x-4) = 0
x = -5 x = 4
x = -5 inadmissable
x=4 in the answer
|
On November 11 2009 08:16 MakkurtE wrote:
jeejee/bear - thats i know it's awkwardly worded, thats why i clarified it properly, several times. going back and picking at the original statement is pointless and tiresome
and lol, are you kidding me?
x^2 + x - 2(floors) = 0
x^2 + x - 2(10) = 0
x^2 + x - 20 = 0
(x+5)(x-4) = 0
x = -5 x = 4
x = -5 inadmissable
x=4 in the answer
How would you go about dropping an egg 4 times to solve it 100% of the time? Seriously, not being an annoying ass, I'm doing different combinations of floor drops and I can't find one that works every time in 4.
|
conCentrate9:
+ Show Spoiler +if you had infinite number of eggs you'd just binary search, starting at 25 (wiki can explain that better then i can). but obviously with only two eggs thats out. so you have to pick a large increment, drop the egg, if it doesn't break, you move up by one more increment and try again until it does. once you find the unsafe large increment floor, you then work your way up to that in one's from the last highest "safe" known floor, one at a time. so d=number of drops with egg2 (1+d)+(1+(d-1))+(1+(d-2))+.....+1+0 = no floors let 1+d=x=total number of drops x+(x-1)+(x-2).....= floors x(x+1)/2 = floors x(x+1) = 2(floors) x(x+1) - 2(floors) = 0 x^2 +x - 2(floors) = 0 hope you see where i'm coming from now. i never realized typing formulae was such a pain in the ass 
|
4 - 7 - 9 - 10
If it breaks on 4, start at 1 and go to 3. Max of 4 drops.
If it breaks on 7, start at 5, and go to 6. Max of 4 drops.
If it breaks on 9, start at 8. Max of 4 drops.
If it breaks on 10, you know where it broke.
Easy.
|
|
|
On November 11 2009 08:21 lMPERVlOUS wrote:
4 - 7 - 9 - 10
If it breaks on 4, start at 1 and go to 3. Max of 4 drops.
If it breaks on 7, start at 5, and go to 6. Max of 4 drops.
If it breaks on 9, start at 8. Max of 4 drops.
If it breaks on 10, you know where it broke.
Easy.
Ah, my bad. I even did that combination of drops. I must have counted wrong or something. My bad.
|
you decrease the the number you go up by when an egg doesn't break by one each time, which cancels out the extra drop caused by it not breaking.
wow, now thats a sentence you can justifiyable rip me for how little sense it makes
|
|
|
I had the exact same question for my programming homework. It is simply binary searching.
if both eggs are breakable start from half the max height and towards the max floor. Every iteration, divide the search space by two and drop the egg from that floor. Once the first egg breaks, u know the the max floor on which the egg is breakable is in between the last known safe floor and the floor which the egg broke on. then u run a linear search from the last known safe floor to find the actual number.
Or for an amortized best worst-case algorithm, use steps of sqrt(maxfloor) for your first egg, and when the first egg breaks, run linear search on the second egg.
i.e. you have 50 stories, and the egg breaks on 37 floor. Then u would test in this order:
1st egg: 25 -> 37 (oops the egg breaks!)
2nd egg: 26,27,28,29,30,31,32,33,34,35,36,37(breaks, therefore the egg's value is 36)
There isnt any real shortcut to this problem.
|
what if you drop your first egg from 25 and it breaks - you'd have to work your way up from 1 - potentially 25 drops. did you read the theory of how to do it just as well in less then half that number?
|
yea well that is the main failing with the binary search. like i said you could try steps of sqrt(max_floor) but i could also say the same if the egg broke on the 43rd floor, binary search could reach that very fast. each algorithm has it best and worse case scenario.
|
Binary search :/ on a problem that you're supposed to solve without pen or paper?
It's an interview question ffs.
Even if you could use pen and paper, you have only 2 eggs. Binary search is way too risky.
|
|
|
Wow, my friend interviewed for a similar position and he got the exact same question (#1). Must be a standard interview question or something...
|
So whats the answer to #1 and the formula?! Im still stuck on whether or not the eggs will break
Imo if your drop @ 50 and it doesnt break..done..but its an egg and it will break @ 1 so...
But its a math problem and Im no genious so I cant be right
|
Well for #1 it seems like you can easily derive the formula if you know it's triangle numbers, but is there a way to show this has to be the optimum (e.g. equispaced drops will always be equal or worse)? Apart from computing it?
I suppose if you only consider the worst case, triangle numbers win out. The way the question is phrased seems to imply that's what you're looking for too.
|
#1
+ Show Spoiler +Drop first egg from 10,19,27,34,40,45,49th floor, when your egg broke in floor 34, then drop your 2nd egg starting with 28 and going on, so my answer is 10
#2
+ Show Spoiler +
|
On November 11 2009 06:44 gyth wrote:Are there any non zero solutions to that equation?
Yeah there are.
for example: (26,30)
|
I need another envelope, I can only show x has to be even =_=
y^2 = (4y +4x +1)(y -x)
x^2 = (3y +3x +1)(y -x)
|
#1+ Show Spoiler +25, 38, 44, 47, 49, 50. That's 6 drops, assuming no breaks. If there's a break somewhere, just search in between that range in the same way. i don't know why people are trying to make this so difficult, and saying 10.
|
On November 13 2009 14:12 Luddite wrote:#1 + Show Spoiler +25, 38, 44, 47, 49, 50. That's 6 drops, assuming no breaks. If there's a break somewhere, just search in between that range in the same way. i don't know why people are trying to make this so difficult, and saying 10.
What if it breaks on 25, then breaks on 12/13 (whichever you choose to drop on)? How do you find out what floor it really breaks on then?
You only have 2 eggs to drop. If the first one breaks on 25, you have to do a linear search from 1-24. That's a potential for 25 drops. The 10 drop method will find it in 10 drops or less.
|
if you have two eggs, then you should drop the first egg in a way such that it only takes roughly sqrt(N) drops to get to floor N, so you can do either f(n) = sqrt(N)*n or f(n) = n^2, the former is better if the answer is close to N, but the latter works better if the answer is small compared to N, so let's say you use the first one, and you broke it at some floor f(k), then you know the answer N' is within f(k-1) < N' <= f(k), so you use the second egg, start from f(k-1)+1, go up by 1 floor each time until you get the right answer. At the worst case (floor 49), this will require 14 drops if we pick f(n) = 7*n (7,14,21,28,35,42,49,43,44,45,46,47,48,49)
This is also generalizable to if you're given an arbitrarily number of eggs E, then the number of drops required is O(N^(1/E))
|
On November 13 2009 15:52 imDerek wrote:
if you have two eggs, then you should drop the first egg in a way such that it only takes roughly sqrt(N) drops to get to floor N, so you can do either f(n) = sqrt(N)*n or f(n) = n^2, the former is better if the answer is close to N, but the latter works better if the answer is small compared to N, so let's say you use the first one, and you broke it at some floor f(k), then you know the answer N' is within f(k-1) < N' <= f(k), so you use the second egg, start from f(k-1)+1, go up by 1 floor each time until you get the right answer. At the worst case (floor 49), this will require 14 drops if we pick f(n) = 7*n (7,14,21,28,35,42,49,43,44,45,46,47,48,49)
This is also generalizable to if you're given an arbitrarily number of eggs E, then the number of drops required is O(N^(1/E))
Well done, that seems right to me.
|
|
|
|
|
|
EPT
