My Math Forum  

Go Back   My Math Forum > College Math Forum > Calculus

Calculus Calculus Math Forum


Reply
 
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,...N-1,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])
OriaG is offline  
 
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.
Hoempa is offline  
October 22nd, 2012, 06:32 AM   #3
Senior Member
 
Joined: Jul 2012

Posts: 225
Thanks: 0

Re: Difficult question on efficiency and algorithms

Quote:
Originally Posted by Hoempa
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.
Firstly, yes, if it breaks when thrown from floor m, that it will break from all the floors higher than m as well. and 2 eggs do suffice. lets take for example N=100. there are a 100 floors. the best way to do this would be to go 10 floors at a time, i went to floor 10, didnt break, floor 20, didnt break, floor 30 didnt break, until i reach floor 100, in floor 100 it broke, now i have to check 91, 92, 93...99. so overall worst case scenario is 19 checks ( floor 10, floor 20, floor 30,...floor 100. floor 91, floor 92, floor 93...floor 99). By most efficient way i mean that in the worst case scenario for that method, you have less checks than any other method.

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.
OriaG is offline  
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^((m-1)/m) floors up a time, then N^((m-2)/m), ..., N^((m-k)/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.
Hoempa is offline  
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
OriaG is offline  
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 tens-digit 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.
Hoempa is offline  
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
thomasedillon1520 is offline  
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.
EvanJ is offline  
June 8th, 2015, 08:56 PM   #9
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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 worst-case number of throws? Or something else?
v8archie is offline  
Reply

  My Math Forum > College Math Forum > Calculus

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





Copyright © 2018 My Math Forum. All rights reserved.