- #1
LarrrSDonald
- 71
- 0
This is a problem that was posed by our professor when taking algorithms years and years ago. Unfortunately I can't recall terribly much about his solutions and (rather lengthy) musings on it, so I don't have a "correct" or "optimal" answer as such. Since I don't have a more normally worded version I can't really look it up. However, I thought it was a rather interesting problem so I'll go ahead and post it.
You are faced with the challenge of finding out which floor of a building you can toss a graduate student out of and still have him survive. You have, by other means, determined that the building and grad students act ideally - they will all always die when tossed out of windows above the critical level and all always survive from floors below it without their survivability upon subsequent tosses changing. You've gathered up the ones you mentor and found that there are N students to test with. Since they are all mostly a nuisance anyway, there is no reason to conserve - you only want to optimize for fewest possible tosses as your time, on the other hand, is immensely valuable. Your building is B floors high and the floor which will kill is random, no lower then 1 and no higher then B. What is an appropriate algorithm? If the general case is too complex, special cases for specific N are also of interest.
Hint (really more of a clarification):
For N=1, there is only one workable solution - toss from 1, then 2, then 3 and so on until your one subject doesn't make it. It will take B/2 tosses on average, best case 1 worst case B. Anything else will not be guaranteed to yield a solution.
Hint 2 (as above):
For N=2, you could, for instance, toss from 2, then 4, then 6 and so on until your first subject dies. Then test the floor below with the remaining student. This would take B/4+1 on average, best 2 worst B/2+1. You could also test 3,6,9... and then the floor where the first one died -2 and -1. There are several other solutions.
[DISCLAIMER] This is merely an algorithm problem and in no way meant to reflect attitudes and actions on anyones behalf. Any similarity to real persons, living or dead, are coincidental.
You are faced with the challenge of finding out which floor of a building you can toss a graduate student out of and still have him survive. You have, by other means, determined that the building and grad students act ideally - they will all always die when tossed out of windows above the critical level and all always survive from floors below it without their survivability upon subsequent tosses changing. You've gathered up the ones you mentor and found that there are N students to test with. Since they are all mostly a nuisance anyway, there is no reason to conserve - you only want to optimize for fewest possible tosses as your time, on the other hand, is immensely valuable. Your building is B floors high and the floor which will kill is random, no lower then 1 and no higher then B. What is an appropriate algorithm? If the general case is too complex, special cases for specific N are also of interest.
Hint (really more of a clarification):
For N=1, there is only one workable solution - toss from 1, then 2, then 3 and so on until your one subject doesn't make it. It will take B/2 tosses on average, best case 1 worst case B. Anything else will not be guaranteed to yield a solution.
Hint 2 (as above):
For N=2, you could, for instance, toss from 2, then 4, then 6 and so on until your first subject dies. Then test the floor below with the remaining student. This would take B/4+1 on average, best 2 worst B/2+1. You could also test 3,6,9... and then the floor where the first one died -2 and -1. There are several other solutions.
[DISCLAIMER] This is merely an algorithm problem and in no way meant to reflect attitudes and actions on anyones behalf. Any similarity to real persons, living or dead, are coincidental.