EPTbrain teaser - Page 2
| Blogs > Shady Sands |
|
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 States18825 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 States9617 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 States44245 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 States44245 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? | ||
| ||
