
Calculus Calculus Math Forum 
 LinkBack  Thread Tools  Display Modes 
October 22nd, 2012, 05:42 AM  #1 
Senior Member Joined: Jul 2012 Posts: 225 Thanks: 0  Difficult question on efficiency and algorithms
A building has N floors {1,2,3,...N1,N}. You have 2 eggs. My question is what is the most efficient way to check from which floor, do eggs break when you throw them? For example, if you check floor by floor, you will have to check N floors worst case scenario. if you check 2 floors at a time, you will have to check N/2 + 1 floors. thats better. My question is what is the best and most efficient way to check. (notice, you don't always have to skip the same amount of floors. You could skip 2 floors, then skip 5, then 15, then 1, whatever you want. so the answer doesnt have to be square root of N [which is the correct answer if you always have to skip same amount of floors]) 
October 22nd, 2012, 06:23 AM  #2 
Math Team Joined: Apr 2010 Posts: 2,778 Thanks: 361  Re: Difficult question on efficiency and algorithms
let 1 <= m < n. May we assume that is an egg breaks from floor m, it will break from all floors higher? Then, do you want to give a statement like: "The doesn't break when thrown from floor m and lower but does from floor m + 1 and higher" Or just The egg breaks from floor m? If it's the latter, just throw from the highest and see if it breaks and there is your statement. If it is the first, I think, two eggs may not suffice. I'd do this (round down to first lower integer if neccesary): Throw from floor N/2. Breaks? Throw from N/4. Doesn't? Throw from 3N/4 etc. 
October 22nd, 2012, 06:32 AM  #3  
Senior Member Joined: Jul 2012 Posts: 225 Thanks: 0  Re: Difficult question on efficiency and algorithms Quote:
for example, in the method i gave, where you skip 10 floors, u have overall 19 checks worst case scenario. whereas if i go floor by floor 1 floor at a time, i will have 100 checks worst case scenario. 19 < 100 so the first method is better. Now i ask what is the most efficient way for N floors, and u dont have to skip same amount of floors all the time.  
October 22nd, 2012, 06:45 AM  #4 
Math Team Joined: Apr 2010 Posts: 2,778 Thanks: 361  Re: Difficult question on efficiency and algorithms
Ok, I assumed if you check, you loose the egg whether it breaks or not. I think, your method works best. Generally, if you have m eggs, you first go N^((m1)/m) floors up a time, then N^((m2)/m), ..., N^((mk)/m) until k = m. Perhaps you can reduce the amount a little if you can use information of how the egg breaks (minor crack or splashed all over). Or investigate the force it takes to break one, but that's a little more advanced. 
October 22nd, 2012, 06:49 AM  #5 
Senior Member Joined: Jul 2012 Posts: 225 Thanks: 0  Re: Difficult question on efficiency and algorithms
there are no cracks or anything. dont overthink this its not a trick question and if it doesnt break, you dont lose the egg. I need a proof that a certain method is faster than all others. and note again  the method i said, is fastest only as long as you can't change the number of floors you go by. i always have to skip 10 floors until the first egg breaks. But if i can change it, if i can go first 10, then 15, then 3, then 7, or whatever, then the answer is different  there is a faster way than skipping sqrt(N) every time. Just need to find what it is and prove that it is faster than all other methods 
October 22nd, 2012, 07:03 AM  #6 
Math Team Joined: Apr 2010 Posts: 2,778 Thanks: 361  Re: Difficult question on efficiency and algorithms
You have to check it doesn't break from floor k AND it breaks from floor k + 1. I think, the way to proof this is the fastest is to compare this to number system. Your example can be compared to the 10 digits number system. The tensdigit is 0  9, 10 options. The units digit, 0  9, 10 options. So 20 options together (or do floor 0 and 100 both exist). If you'd first go up say 20 a time and then 5 a time, you'd need 25 checks. Worse than 20. A similar statement could be phrased if you don't skip the same amount of floors all the time. 
June 8th, 2015, 06:00 PM  #7 
Newbie Joined: Jun 2015 From: USA Posts: 6 Thanks: 1 
I think the correct answer is more along the lines of always going half. If you have 100 floors, no need to go with 10, just go to half, which is 50. Breaks or doesn't, no matter, just half again. Lets say it does not, so you know at 50 it does not, so go half, or 75. lets say again, for worst case scenario it does not, go half again, or 87, which is rounded down to make it worst case. Does not break. Half again, or 93, rounded down for worst case. Does not break, half again rounded down or 96. Doesn't break, half again, or 98. Doesn't break, half again to 99. Doesn't break. Only possible floor left is 100. This gives you 8 checks instead of the 19 you have previously picked in your worst case scenario. Hope this either A, solves your problem, or B sheds new light. BTW, I have no clue how you would go about writing an equation to represent that, but to me it is just the fastest way to find the mark. Tom 
June 8th, 2015, 07:05 PM  #8 
Senior Member Joined: Oct 2013 From: New York, USA Posts: 619 Thanks: 83 
I would also say break it down into halves, although doing exactly half becomes impossible. Let's take the extreme case where the egg will only break from Floor 99 or 100. By testing Floors 50, 75, 88 (87.5 rounds to 88), 94, 97, and 99 (98.5 rounds to 99) you will determine that it breaks from Floor 99. Then you would need to test Floor 98, for a total of 7 checks. This assumes that the time and energy spent going from floor to floor is irrelevant.

June 8th, 2015, 08:56 PM  #9 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms 
Of course if you had just one egg you'd need to check floor 1, floor 2, and so on up to floor n. Once the first egg breaks, you'll be forced to use this strategy based on the bounds you know. For example, if you dropped it from floor 10 and it didn't break, but it broke on floor 20, you'll now need to drop the second egg on floors 11, 12, ..., 19 to see if it breaks. Let's imagine you can only make three egg drops. If the first drop smashes the egg you'll need to start from floor 1 on the second egg, letting you test floors 1 and 2 with your remaining two drops. So the first drop was on floor 3 to get complete coverage. If the egg survived floor 3 then you have two drops left, so floor 5 must be next since if it breaks then you need to test floor 4 with the last egg. Otherwise your single drop must be on floor 6. If you can make four drops with the two eggs you get an extra floor on each: floor 4 for the first egg, then floor 7 if it survives, then floor 9, then finally floor 10. If you can make five drops you test floors 5, 9, 12, 14, and 15. If you can make six drops you can test up to floor 6+5+4+3+2+1 = 6*7/2 = 21. Generally, if you can make n drops, you can test up to n(n+1)/2 floors. So 13 drops would let you get up to 91 floors and 14 would get you up to 105. The latter is the minimum needed with two eggs. Of course if you have 7 eggs you could use binary splitting, as thomasedillon1520 describes. But with two eggs it's not so easy. 
June 8th, 2015, 09:13 PM  #10 
Math Team Joined: Dec 2013 From: Colombia Posts: 7,502 Thanks: 2511 Math Focus: Mainly analysis and algebra 
But, if we have a fastest of $(\sqrt N  1)\sqrt N$ (worst case) when you can't change the number of floors you skip, then with the first egg you can start with $(\sqrt N  1)\sqrt N$ on the first throw without making the worst case any worse )if it breaks to go back to 1, 2, 3, ..., etc.. For the second throw, you'd then go to $2(\sqrt N  1)\sqrt N  1$. If it breaks you go to $(\sqrt N  1)\sqrt N + 1$, $(\sqrt N  1)\sqrt N + 2$, ..., etc.. For the third throw, $3(\sqrt N  1)\sqrt N  2$ and so on. This shows that you can get far higher than $N$ using $(\sqrt N  1)\sqrt N$ throws as a worst case. Of course, the probability that you require all $(\sqrt N  1)\sqrt N$ throws is also higher. Actually the problem statement is ambiguous. Should we be looking for the method with the least expected number of throws? Or the method with the least worstcase number of throws? Or something else? 

Tags 
algorithms, difficult, efficiency, question 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Algorithm efficiency  jhuntley  Computer Science  7  May 9th, 2014 04:20 PM 
DIfficult Question, try it  Iamthatdude  Math Events  1  August 28th, 2013 01:13 PM 
The factorial efficiency of Bayes Rule  BenFRayfield  Advanced Statistics  0  July 31st, 2013 10:33 AM 
Difficult question!  DragonScion  Advanced Statistics  0  October 29th, 2011 03:54 PM 
Engine Efficiency???????????????? how??  imcutenfresa  Calculus  1  October 13th, 2009 06:27 PM 