|
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.
|
|
|
|
|
|
EPT
