| Blogs > Shady Sands |
|
Shady Sands
United States4021 Posts
Using only the method of dropping a rock from a certain floor and seeing whether it will crack open or not, what is the least number of drop attempts you need to use to figure out the highest floor from which a rock, dropped, will not break? 1) Breaking is ordinal--a rock that breaks from a 60 floor etc. can be safely assumed to break from a 70 floor drop, etc. Once you have calculated this for the 100-floor building, what is the answer for an n-floor building?   | ||
|
AnachronisticAnarchy
United States2957 Posts
| ||
|
TOCHMY
Sweden1692 Posts
least number of drop attempts: 2, cuz you only have, at most, 2 rocks? Dont mind the spoiler, I misunderstood the question... | ||
|
Warmonger
United States69 Posts
On November 21 2012 06:46 AnachronisticAnarchy wrote: Is this a trick question? It seems impossible to do it with only 2 rocks. Not impossible, it would just take a while without further assumptions/knowledge. + Show Spoiler + 1.)Drop the first rock from halfway up the building, N/2 2a.)If it breaks start on the 1st floor and keep going up a floor until it breaks 2b.)If it doesn't break start on the 51st floor (N/2 +1) and keep going up a floor until it breaks | ||
|
AiurZ
United States429 Posts
for an n-floor building u just find the minimum of (n/x)+x=y and that is the amount of floors u skip each try (for a 100 floor building it is 10). | ||
micronesia
United States24680 Posts
Except they used eggs. | ||
|
L3gendary
Canada1470 Posts
nvm i skipped over the u can only break it twice part, the egg one made it more clear to me. The steps of 10 seems right. For N case it'd be 2*root(N)-1. | ||
|
Shield
Bulgaria4824 Posts
On November 21 2012 06:53 Warmonger wrote: Not impossible, it would just take a while without further assumptions/knowledge. + Show Spoiler + 1.)Drop the first rock from halfway up the building, N/2 2a.)If it breaks start on the 1st floor and keep going up a floor until it breaks 2b.)If it doesn't break start on the 51st floor (N/2 +1) and keep going up a floor until it breaks It sounds like it works, but is it the fastest way? | ||
|
AnachronisticAnarchy
United States2957 Posts
On November 21 2012 06:53 Warmonger wrote: Not impossible, it would just take a while without further assumptions/knowledge. + Show Spoiler + 1.)Drop the first rock from halfway up the building, N/2 2a.)If it breaks start on the 1st floor and keep going up a floor until it breaks 2b.)If it doesn't break start on the 51st floor (N/2 +1) and keep going up a floor until it breaks You only have 2 rocks, though. I guess if you want to discard that limit, you could do this: 1. drop a rock from the 50th floor 2a. if it breaks, go to floor 25 2b. if it doesn't break, go to floor 75 3a,a: if it breaks, go to floor 13 3a,b: if it doesn't break, go to floor 37 3b, a: if it does break, go to floor 63 3b, b: if it doesn't break, go to floor 87 and so on and so on By doing this, you maximize the amount of floors each drop covers, until you find the floor you're looking for. I'm not fond of the question though. Even without the 2-rock limit, there's the fact that the appropriate floor is random, so odds are you would stumble upon the answer before you finish the process you are doing and rule out everything but the answer. | ||
|
stenole
Norway868 Posts
| ||
|
Melliflue
United Kingdom1389 Posts
On November 21 2012 06:53 Warmonger wrote: Not impossible, it would just take a while without further assumptions/knowledge. + Show Spoiler + 1.)Drop the first rock from halfway up the building, N/2 2a.)If it breaks start on the 1st floor and keep going up a floor until it breaks 2b.)If it doesn't break start on the 51st floor (N/2 +1) and keep going up a floor until it breaks You can do better than this. + Show Spoiler + If the rock doesn't break (case 2b) then you can drop a rock from the 75th floor using the same argument. If it breaks then start on 51st floor, if it doesn't then try higher. I doubt that is optimal though. Edit: On November 21 2012 07:12 AnachronisticAnarchy wrote: You only have 2 rocks, though. I guess if you want to discard that limit, you could do this: 1. drop a rock from the 50th floor 2a. if it breaks, go to floor 25 2b. if it doesn't break, go to floor 75 3a,a: if it breaks, go to floor 13 3a,b: if it doesn't break, go to floor 37 3b, a: if it does break, go to floor 63 3b, b: if it doesn't break, go to floor 87 and so on and so on By doing this, you maximize the amount of floors each drop covers, until you find the floor you're looking for. I'm not fond of the question though. Even without the 2-rock limit, there's the fact that the appropriate floor is random, so odds are you would stumble upon the answer before you finish the process you are doing and rule out everything but the answer. That's a standard binary search or bisection search. I can't remember the technical term for it. It is the most efficient way with enough rocks. I am not sure I follow your argument for why you don't like the question. The floor is random, but the question is what is the least number of drops needed to be certain that you know which floor it is. | ||
|
spinesheath
Germany8679 Posts
Heh, guess I was wrong about the 10 20 30 solution being right. | ||
|
Cyber_Cheese
Australia3615 Posts
I think the working the way up in multiples of 10 thing was best for 2 stones only, sqrt(floors) I'm not about to sit down and calculate every scenario though.. | ||
|
Phael
United States281 Posts
+ Show Spoiler + A straightforward solution would be to drop the first rock every 10 floors until it breaks, then drop the second rock from the last floor that didn't break up in increments of 1. Ex: drop at 10, 20, 30, 40, 50 .. break. Ok, second rock: 41, 42, 43, 44 ... break. Highest floor: 43. This would give us a solution of 19, which isn't optimal, because you're "wasting" potential drops if the rock cracks on floor 9, for example, vs floor 99. So instead, drop the first rock at floor 14, then floor 27 (14+13), then floor 39 (14+13+12), etc. This way, the "worst case scenario" of a rock breaking at 14 means you drop 13 more times, the WCS of a rock breaking at 27 would be dropping 12 more times, etc. so in total, you should only need 14 drops no matter which floor the rocks crack on. How did I get 14? I recognized that you need 1 + 2 + 3 + 4 + 5 + ... + d >= number of floors, and for 100, d = 14. General solution + Show Spoiler + General solution for d drops on a building with n floors: Following from previous, 1 + 2 + 3 + 4 + 5 + ... + d >= n. d*(d+1)/2 >=n d^2 + d - 2n >= 0 By the quadratic equation, the positive solutions: d >= (root(8n+1)-1)/2 so minimum number of drops needed = ceiling((root(8n+1)-1)/2) | ||
|
Warmonger
United States69 Posts
On November 21 2012 07:12 darkness wrote: It sounds like it works, but is it the fastest way? You are right, I overlooked being able to re-use the first rock if it didn't break. In which case the "best" method may be defined differently for different needs. Are we looking for fastest average solution for a building with N stories? The solution with least attempts on worst-case? I don't have the knowledge to do either off the top of my head, but I'm sure some CS major can do it fairly easily. | ||
|
CoughingHydra
177 Posts
On November 21 2012 07:06 L3gendary wrote: logN/log2 ? rounded of course. This is the first thing that came to my mind too ( binary search algorithm ). http://en.wikipedia.org/wiki/Binary_search_algorithm EDIT: Nevermind  | ||
|
Blazinghand
United States25551 Posts
| ||
|
opisska
Poland8852 Posts
| ||
|
AnachronisticAnarchy
United States2957 Posts
| ||
|
Varanice
United States1517 Posts
On November 21 2012 07:22 Phael wrote: Solution for 100 floors: + Show Spoiler + A straightforward solution would be to drop the first rock every 10 floors until it breaks, then drop the second rock from the last floor that didn't break up in increments of 1. Ex: drop at 10, 20, 30, 40, 50 .. break. Ok, second rock: 41, 42, 43, 44 ... break. Highest floor: 43. This would give us a solution of 19, which isn't optimal, because you're "wasting" potential drops if the rock cracks on floor 9, for example, vs floor 99. So instead, drop the first rock at floor 14, then floor 27 (14+13), then floor 39 (14+13+12), etc. This way, the "worst case scenario" of a rock breaking at 14 means you drop 13 more times, the WCS of a rock breaking at 27 would be dropping 12 more times, etc. so in total, you should only need 14 drops no matter which floor the rocks crack on. How did I get 14? I recognized that you need 1 + 2 + 3 + 4 + 5 + ... + d >= number of floors, and for 100, d = 14. General solution + Show Spoiler + General solution for d drops on a building with n floors: Following from previous, 1 + 2 + 3 + 4 + 5 + ... + d >= n. d*(d+1)/2 >=n d^2 + d - 2n >= 0 By the quadratic equation, the positive solutions: d >= (root(8n+1)-1)/2 so minimum number of drops needed = ceiling((root(8n+1)-1)/2) I was getting close to this for the 100 floor version, but you sir are a genius. | ||
|
synapse
China13814 Posts
| ||
|
KaRnaGe[cF]
United States355 Posts
| ||
|
Aerisky
United States12129 Posts
I am sooo bad at logic puzzles/brain teasers though lol ;__;. Maybe I shouldn't go through with a technical field and/or EECS after all. And karnage the assumption is that the rock sustains no damage until it hits the breaking point, whereupon the rock immediately and completely breaks. Otherwise you can't actually do the puzzle lol. | ||
|
farvacola
United States18826 Posts
| ||
|
Complete
United States1864 Posts
On November 13 2011 13:34 Complete wrote: 14,27,39,50,60,69,77,84,90,95,99,100 worst case 14 My answer from another thread with this question. | ||
|
ClysmiC
United States2192 Posts
You drop the first one at 50, it breaks. You drop the second one at 25, it breaks. Both your rocks are now broken and you can't continue testing. If you had unlimited number of rocks, then yes, binary selection is the fastest way. That being said, I'm not sure what the fastest way is ^_^ | ||
|
snively
United States1159 Posts
xD | ||
|
brian
United States9619 Posts
| ||
|
Shady Sands
United States4021 Posts
On November 21 2012 12:24 Gene wrote: seriously. As a Brian, I can confirm this is #1 most annoying thing in the world. =/ bah edit: ty mystery mod | ||
|
DarkPlasmaBall
United States44324 Posts
| ||
|
peidongyang
Canada2084 Posts
Recursive Relation: a(n)=2*a(n-1), where n is the number of rocks Proof For 1 rock, we are able to drop it from floor 1 and if it breaks, and it won't break from floor 0 For 2 rocks, we are able to drop it from floor 2. If it breaks, we drop it from floor 1. If not, we will drop it from floor 3. Therefore we are able to determine breaking from floors 1-4. Without going into rigorous mathematical proof, it is very easy to see that 2^n floors can be determined with n rocks, or the reserve, the binary search tree with log(2)n time. Therefore the solution for 100 floors is ceil(log(2)100). The general solution is ceil(log(2)n) edit2: nvm again I think my solution holds. Guaranteed to produce result in 7 searches | ||
|
Blazinghand
United States25551 Posts
On November 21 2012 15:21 DarkPlasmaBall wrote: I agree with the "10 steps of 10" starting point. It seems in general you want your second rock to be responsible for the same number of steps as your first rock, assuming the worst case scenario- that your first rock breaks on the first try. From there, the answer is trivial. Yeah the thing is, if you do 10 steps of 10 as a starting point you quickly realize it's not optimal. Let's say you drop at 10, 20, 30, etc all the way up to 80. Where do you drop now? Well, you could drop at 90, but then your first rock is responsible for 1 step and your second rock could be responsible for 10. So basically your initial increment should be bigger than 10, and by the time you get to 100 it should be pretty small. This ends up being increment of 14, 13, 12, 11, and so on, so that each time, even later on, both rocks are responsible for the same amount of chance. | ||
|
DarkPlasmaBall
United States44324 Posts
On November 21 2012 15:31 Blazinghand wrote: Yeah the thing is, if you do 10 steps of 10 as a starting point you quickly realize it's not optimal. Let's say you drop at 10, 20, 30, etc all the way up to 80. Where do you drop now? Well, you could drop at 90, but then your first rock is responsible for 1 step and your second rock could be responsible for 10. So basically your initial increment should be bigger than 10, and by the time you get to 100 it should be pretty small. This ends up being increment of 14, 13, 12, 11, and so on, so that each time, even later on, both rocks are responsible for the same amount of chance. Well can't you adjust after each drop, so that every step would hypothetically cause your second rock to require the same amount of floor responsibility as the first one, if the first rock broke at any given step? I'm just concerned about the starting point for starters. If you start at floor 10 and the first rock does break, the the second rock will then be responsible for 10 floors (1-9). If the first rock didn't break, then you need to account for the other 90 floors. I'm not suggesting that you always go up in increments in 10 (although looking back at my post, I totally could have chosen better words- I just meant the starting point though), as I do agree with your reasoning that then the first rock would be doing less work (so to speak) in accounting for fewer relative groups, whereas the second rock would always need to do increments of 10. But then we would just keep rounding (perhaps via square roots? I don't know; I'm tired) such that the first and second rocks are always hypothetically responsible for the same amount of work (the first rock being the larger division and then the second rock having an equal sub-division in case the first rock breaks at any time) at any given step. EDIT: So I guess for the second step, assuming the first rock doesn't break and there are 90 floors left... drop the first rock at ~sqrt(90), or 9 or 10 floors, up, so that the second rock can also cover that many floors in case the rock breaks? If the first rock attempted to cover more to make your job easier, you'd fall behind on your counting if it breaks. If you cover fewer floors in an attempt to ensure the rock doesn't break, then you still have potentially many more floors to go in the long run. Or is it the case that with all of these cumulatively smaller increments, it ends up being slightly larger overall than if you happened to just plain start off with a bigger number for the first rock drop than floor 10? Is there a justification for this other than working out all the calculations? | ||
|
GhandiEAGLE
United States20754 Posts
| ||
|
Cyber_Cheese
Australia3615 Posts
On November 21 2012 15:31 Blazinghand wrote: Yeah the thing is, if you do 10 steps of 10 as a starting point you quickly realize it's not optimal. Let's say you drop at 10, 20, 30, etc all the way up to 80. Where do you drop now? Well, you could drop at 90, but then your first rock is responsible for 1 step and your second rock could be responsible for 10. So basically your initial increment should be bigger than 10, and by the time you get to 100 it should be pretty small. This ends up being increment of 14, 13, 12, 11, and so on, so that each time, even later on, both rocks are responsible for the same amount of chance. I think this changes the average to be better too The 10 example works out to ~ 11 average (if I'm not mistaken.) The average number of guesses the first rock will take is the average of the sum of 1->10 which is 5.5, then the second rocks the same for 11 total. As a worst case scenario, it goes to 19 (10,20,30...100 =10), when it breaks on 99 or 100 (Because it has to break somewhere right?) You have to test 91,92,93....99. with 14+13... it's a little more complicated to find an average, the first rock has 12 possibilites, but it's an average of (x?), because the early ones are more likely to show up, and then the second one has 11 possibilites, but an average of (y?) because the ones the cooincide with a large number of rock 1 drops will require less rock 2 drops If I did x+y, it'd be manually tallying, I suspect someone knows a better way? | ||
|
Rannasha
Netherlands2398 Posts
On November 21 2012 18:27 Cyber_Cheese wrote: I think this changes the average to be better too The 10 example works out to ~ 11 average (if I'm not mistaken.) The average number of guesses the first rock will take is the average of the sum of 1->10 which is 5.5, then the second rocks the same for 11 total. As a worst case scenario, it goes to 19 (10,20,30...100 =10), when it breaks on 99 or 100 (Because it has to break somewhere right?) You have to test 91,92,93....99. with 14+13... it's a little more complicated to find an average, the first rock has 12 possibilites, but it's an average of (x?), because the early ones are more likely to show up, and then the second one has 11 possibilites, but an average of (y?) because the ones the cooincide with a large number of rock 1 drops will require less rock 2 drops If I did x+y, it'd be manually tallying, I suspect someone knows a better way? The second option (14,13,12...) averages at 10.36 drops. Determined by just averaging the number of drops from all possible heights. | ||
|
Cyber_Cheese
Australia3615 Posts
On November 21 2012 18:51 Rannasha wrote: The second option (14,13,12...) averages at 10.36 drops. Determined by just averaging the number of drops from all possible heights. Did you include that '14' would be 14 drops, because you don't know if the rock broke at 13 or not? Same with 27,39,50,60,69,77,84,90,95,99 | ||
|
Flonomenalz
Nigeria3519 Posts
| ||
|
AcrossFiveJulys
United States3612 Posts
On November 21 2012 06:40 Shady Sands wrote: + Show Spoiler + Imagine you have, at most, two identical rocks and a 100-floor building. Using only the method of dropping a rock from a certain floor and seeing whether it will crack open or not, what is the least number of drop attempts you need to use to figure out the highest floor from which a rock, dropped, will not break? 1) Breaking is ordinal--a rock that breaks from a 60 floor etc. can be safely assumed to break from a 70 floor drop, etc. Once you have calculated this for the 100-floor building, what is the answer for an n-floor building? The "at most 2 identical rocks" condition is confusingly worded. One interpretation would be that you start with either 1 rock or 2 identical rocks, and if a rock breaks, you can't drop it anymore. So the challenge is that if you break all rocks you start with without finding a floor in which a rock doesn't break you can't say with certainty any floor in which a rock does not break. So under that interpretation, if you start with 1, the only strategy that is guaranteed to give you an answer is to start at floor 1 and continue upwards until the rock breaks; the floor before the one in which it breaks is the answer. If you start with 2, the best strategy that is guaranteed to give you an answer would be one in which you ascend 2 floors at a time and drop one rock at each floor until it breaks. Then you try the other rock on the floor below. If it breaks at floor X, the answer is floor X-1; if it doesn't break, the floor X is the answer. Another interpretation of the "at most 2 identical rocks" condition would be that you start with a (known finite? infinite?) number of rocks in which at most 2 are identical, and you are trying to find the highest floor that some rock breaks. In this scenario, the optimal strategy depends on how many rocks you start with which you didn't tell us. Yet another (loose) interpretation is that we start with an infinite number of identical rocks. In this case the optimal strategy is a binary search: try floor ceil(N/2), if a rock breaks, try floor ceil(N/4), and if not try floor ceil(3*N/4), and so on. The maximum number of drops will be ceil(log_2(N)). | ||
|
Cyber_Cheese
Australia3615 Posts
On November 21 2012 19:35 AcrossFiveJulys wrote: The "at most 2 identical rocks" condition is confusingly worded. One interpretation would be that you start with either 1 rock or 2 identical rocks, and if a rock breaks, you can't drop it anymore. So the challenge is that if you break all rocks you start with without finding a floor in which a rock doesn't break you can't say with certainty any floor in which a rock does not break. So under that interpretation, if you start with 1, the only strategy that is guaranteed to give you an answer is to start at floor 1 and continue upwards until the rock breaks; the floor before the one in which it breaks is the answer. If you start with 2, the best strategy that is guaranteed to give you an answer would be one in which you ascend 2 floors at a time and drop one rock at each floor until it breaks. Then you try the other rock on the floor below. If it breaks, the answer is the floor below; if it doesn't break, the current floor is the answer. .... What? The first rock exsists to narrow down the range such that the second could act as your only rock example. What if the answer was 99? Are you seriously calling 51 potential drops optimal? | ||
|
Ota Solgryn
Denmark2011 Posts
On November 21 2012 06:40 Shady Sands wrote: Imagine you have, at most, two identical rocks and a 100-floor building. Using only the method of dropping a rock from a certain floor and seeing whether it will crack open or not, what is the least number of drop attempts you need to use to figure out the highest floor from which a rock, dropped, will not break? 1) Breaking is ordinal--a rock that breaks from a 60 floor etc. can be safely assumed to break from a 70 floor drop, etc. Once you have calculated this for the 100-floor building, what is the answer for an n-floor building? The least number of drops you need to use is 2. You drop the first rock from n+1 floor -> it breaks. You drop the next rock from n floor -> it doesn't break. So now you know the highest floor from which is doesn't break is the n floor. The answer cannot be 1 (the rock breaks at 1st floor) because then there would be no floor from which the rock would be intact. This is unless you are allowed to use the exclusion principle and just drop one rock from the 2nd floor and you then know the rock would be intact on the 1st floor (then it would be only 1 drop). I did it this way becuase the question is the least number of drops. Most people here seem to calculate what is the maximum number of drops you would need to use in the case you have the most optimal way of generally finding the highest floor of which the rock would be intact. | ||
|
AcrossFiveJulys
United States3612 Posts
On November 21 2012 19:45 Cyber_Cheese wrote: .... What? The first rock exsists to narrow down the range such that the second could act as your only rock example. What if the answer was 99? Are you seriously calling 51 potential drops optimal? Mmmm you're right. It's 6am here >< | ||
|
Clazziquai10
Singapore1949 Posts
How do you drop the rocks in such a way that yields the best worst-case scenario? i.e. the worst case scenario for a particular way to drop the rocks would require the lowest number of drops compared to other ways to do so | ||
|
Rannasha
Netherlands2398 Posts
On November 21 2012 19:48 Ota Solgryn wrote: The least number of drops you need to use is 2. You drop the first rock from n+1 floor -> it breaks. You drop the next rock from n floor -> it doesn't break. So now you know the highest floor from which is doesn't break is the n floor. Except you don't know what n is. I did it this way becuase the question is the least number of drops. Most people here seem to calculate what is the maximum number of drops you would need to use in the case you have the most optimal way of generally finding the highest floor of which the rock would be intact. What you answered is the least number of drops you need to verify that the highest non-breaking-floor is n, when n is provided a priori. If n is not known, you need to the "best worst-case-scenario", which is what people have been calculating. | ||
|
Rannasha
Netherlands2398 Posts
On November 21 2012 15:29 peidongyang wrote: Base case: For 0 rocks we are able to determine whether or not 1 floor is passable (we assume it is) Recursive Relation: a(n)=2*a(n-1), where n is the number of rocks Proof For 1 rock, we are able to drop it from floor 1 and if it breaks, and it won't break from floor 0 For 2 rocks, we are able to drop it from floor 2. If it breaks, we drop it from floor 1. If not, we will drop it from floor 3. Therefore we are able to determine breaking from floors 1-4. Without going into rigorous mathematical proof, it is very easy to see that 2^n floors can be determined with n rocks, or the reserve, the binary search tree with log(2)n time. Therefore the solution for 100 floors is ceil(log(2)100). The general solution is ceil(log(2)n) edit2: nvm again I think my solution holds. Guaranteed to produce result in 7 searches The problem only allows you 2 rocks, your solution requires more. Specifically, if the rock already breaks on the first floor, your binary search tree requires you to break 7 rocks. This is why binary search trees are not a correct way of approaching the problem. (The problem would be rather dull otherwise, since binary search trees are such a common technique.) | ||
|
Incze
Romania2058 Posts
| ||
|
Rannasha
Netherlands2398 Posts
On November 21 2012 22:17 Incze wrote: But if a rock would normally break when thrown from, say, the 50th floor, then if it's already been dropped from all the previous floors, it won't be able to reach 50, it would break much sooner because each fall, no matter how small affects its structural integrity. It's an abstract problem. The only reason it's described with physical concepts such as rocks and floors is to make it accessible. In this case, you must assume that the rocks is completely unaffected by a drop that doesn't outright break it. If you can't do that, I can give you a purely mathematical description of the problem. | ||
|
Ota Solgryn
Denmark2011 Posts
On November 21 2012 21:47 Rannasha wrote: Except you don't know what n is. What you answered is the least number of drops you need to verify that the highest non-breaking-floor is n, when n is provided a priori. If n is not known, you need to the "best worst-case-scenario", which is what people have been calculating. No, I provided the least number of drops you need if you make a lucky guess, I do not need to know n, nowhere does the question state that you could not make guess, and be lucky with that guess. Anyhow, I just answered it as was it a trick question, which to me it is, because of a vague formulation. | ||
|
DarkPlasmaBall
United States44324 Posts
On November 21 2012 22:46 Ota Solgryn wrote: No, I provided the least number of drops you need if you make a lucky guess, I do not need to know n, nowhere does the question state that you could not make guess, and be lucky with that guess. Anyhow, I just answered it as was it a trick question, which to me it is, because of a vague formulation. While I understand that possible ambiguity/ need to be clever, I'm also pretty sure that based on the context, you really understood that it wasn't a trick question. It means for any given floor, the fact that you're always looking to optimize your answer (not just "get lucky"), and the understanding that you can't risk both rocks breaking without knowing for a fact what the correct floor is. You can't just arbitrarily say, "I choose to pick the two perfect floors to give me the correct answer, meaning the answer's two", because you're incapable of knowing for sure that you'd pick those two ideal floors. You'd need to already know the answers, and then drop the rocks to reconfirm them. However, as the person dropping the rocks, you don't actually know yet what those ideal floors are. I mean, after all, if you really want to be a dick about it, why not just say, "Well I was super lucky in my individual trial because the answer was "the rock breaks at the first floor" and I dropped my first rock on the first floor and it broke, and therefore I didn't even need the second rock. Answer's one." It's really missing the point of the brain teaser, because if it hadn't broken, I would have only eliminated one floor in one step, and I'd still have ninety-nine to go... and you simply can't work under the assumption that it will be the first floor, so it's silly to pick floor one to drop the first rock. It will be better for you (probability-wise) to drop the first rock at floor two at step one than at floor one. | ||
|
Scorch
Austria3371 Posts
| ||
|
spinesheath
Germany8679 Posts
| ||
|
Warillions
United States215 Posts
| ||
|
green.at
Austria1459 Posts
my initial thought is n/2 if i start on floor 2 and go up 2 each time it does not break, gonna think about it some more  | ||
|
vaL4r
Germany240 Posts
On November 21 2012 06:40 Shady Sands wrote: what is the least number of drop attempts you need to use to figure out the highest floor from which a rock, dropped, will not break? + Show Spoiler + Two. I drop my first rock from floor X which just so happens to be the floor above the one from which it won't break, of course at this time I don't know this.. not until I drop the rock from the floor X-1 and discover it is intact! In case I am missunderstanding I could be wrong but it seems to me as thought this was a silly trick question and not a puzzle with a clever mathematical answer. I would appreciate if you told me which one is EDIT: oh nvm I get it.. so the idea is that if the rock doesn't break I can pick it up and use it again so the question is which is the most effective method for finding the floor without breaking more than 2 rocks. Meh I don't see it! Seems like too much of a shot in the dark - I would start by throwing it from the [ highest floor - 1 ], if it doesn't break you can go test the highest floor, if it does I would just go back to floor 0 and go one up every throw... every other method I can come up with on the fly seems flawed in that it could be really bad depending on what the right floor number actually is. | ||
|
Z-BosoN
Brazil2590 Posts
| ||
|
AcrossFiveJulys
United States3612 Posts
Here's my solution which ends up more rigorously deriving Phael's solution. So you drop the first rock on some floor x_1. If it breaks, you are forced to start from floor 1 and increase to x_1-1 until the rock breaks, at which point you know the answer in x_1 steps. If it doesn't break, you get to choose another floor x2 to drop the first rock, where if it breaks you have to ascend from floor x_1+1 to x_2-1, which makes you take x_2-x_1+1 steps. Extending this reasoning to general x_k, the worst case becomes x_k - x_{k-1} + k-1. So the problem can be formulated as choosing x1, x2, ..., xN to minimize max_k {x_k-x_{k-1}+k-1}, Let the number of steps that strategy G takes given the answer is F be G(F). Now consider the space of strategies that contains those that are valid (always outputs a solution) and never perform useless drops (ones that give no additional information); call that space S. Obviously this space of strategies contains the optimal strategy. Then for all G in S, G(F) summed over F=1 to N is the same. I think this is a safe assertion that could be easily proved via a proof by contradiction. Then, we conclude that in order to minimize the maximum number of steps, the number of steps required for each possible F in the optimal strategy should be the same. So we need to find x_1, ..., x_M such that x_k-x_{k-1}+k-1 for all k from 1 to M, and where M <= N. The unique solution to that recurrence relation is Phael's solution. | ||
|
Shady Sands
United States4021 Posts
| ||
|
zlefin
United States7689 Posts
since question is poorly formulated; i get to interpret it to my convenience. drop it from the top floor, if it doesn't break, it won't break at any floor; hence it is the highest floor from which a rock dropped will not break (since tehre is no higher floor). question doesnt' say whether to look for best or worst case scenarios; so i choose best case | ||
|
LockeTazeline
2390 Posts
+ Show Spoiler + Drop it from the midway point of the available floors, rounded up. Longest solve (answer 1st floor): -50 (break) -25 (break) -13 (break) -7 (break) -4 (break) -2 (break) -1 (break) =7 Overall: Log 2 of n. (rounded up) | ||
|
targ
Malaysia445 Posts
On November 21 2012 06:55 AiurZ wrote: fastest way to find out is to drop from 10th floor, then 20th floor, then 30th floor, etc. until it breaks and then you drop the 2nd rock ascending each floor 1 by 1. for an n-floor building u just find the minimum of (n/x)+x=y and that is the amount of floors u skip each try (for a 100 floor building it is 10). This was my original idea too, just get the minimum of (n/x)+x-1=y, I think you missed out the -1, because say you drop and break on the tenth floor then you only need to drop the second rock nine times. However this only yields the optimal solution in the case that x is fixed, so it is less optimal that the 14 + 13 + 12... solution. Binary search would be fastest if we had more rocks, but since we only have two its not workable. | ||
|
Ota Solgryn
Denmark2011 Posts
On November 21 2012 23:25 DarkPlasmaBall wrote: While I understand that possible ambiguity/ need to be clever, I'm also pretty sure that based on the context, you really understood that it wasn't a trick question. It means for any given floor, the fact that you're always looking to optimize your answer (not just "get lucky"), and the understanding that you can't risk both rocks breaking without knowing for a fact what the correct floor is. You can't just arbitrarily say, "I choose to pick the two perfect floors to give me the correct answer, meaning the answer's two", because you're incapable of knowing for sure that you'd pick those two ideal floors. You'd need to already know the answers, and then drop the rocks to reconfirm them. However, as the person dropping the rocks, you don't actually know yet what those ideal floors are. I mean, after all, if you really want to be a dick about it, why not just say, "Well I was super lucky in my individual trial because the answer was "the rock breaks at the first floor" and I dropped my first rock on the first floor and it broke, and therefore I didn't even need the second rock. Answer's one." It's really missing the point of the brain teaser, because if it hadn't broken, I would have only eliminated one floor in one step, and I'd still have ninety-nine to go... and you simply can't work under the assumption that it will be the first floor, so it's silly to pick floor one to drop the first rock. It will be better for you (probability-wise) to drop the first rock at floor two at step one than at floor one. Yeah, you're right, I was trying to be clever ;o) but my point still stands. The least number of drops you would need to show the highest floor from which the rock will not drop is still 2, and here I do not assume that I know the floor, I assume the specific case in which a lucky guess was made. And this specific case would yield the result of least dropped rocks: 2. Your last paragraph I also commented on, but I excluded this as the answer becuase if the rock breaks at the first floor then there is no floor from which the rock survives a drop and the answer is not 1 but null. | ||
|
Rannasha
Netherlands2398 Posts
On November 22 2012 11:18 LockeTazeline wrote: I think: + Show Spoiler + Drop it from the midway point of the available floors, rounded up. Longest solve (answer 1st floor): -50 (break) -25 (break) -13 (break) -7 (break) -4 (break) -2 (break) -1 (break) =7 Overall: Log 2 of n. (rounded up) You only have 2 rocks you can break, not 7. | ||
| ||
StarCraft 2 StarCraft: Brood War Dota 2 Counter-Strike Other Games |
|
WardiTV European League
MaNa vs NightPhoenix
ByuN vs YoungYakov
ShoWTimE vs Nicoract
Harstem vs ArT
Korean StarCraft League
CranKy Ducklings
BSL20 Non-Korean Champi…
Mihu vs QiaoGege
Zhanhun vs Dewalt
Fengzi vs TBD
WardiTV European League
Online Event
Sparkling Tuna Cup
BSL20 Non-Korean Champi…
Bonyth vs TBD
WardiTV European League
Wardi Open
[ Show More ] |
|
|
EPT
