Algorithm for Throwing Grad Students Out of Buildings - Algorithm Ponderer

[LarrrSDonald]

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.

 

[AKG]

If N is big enough to do a binary search, wouldn't that be best? It would take log(B) time, right? You'd have to have N > log(B). The binary search appears to be better than the search in your second hint (every 2nd floor) when B > 8. If you use the search in the second hint checking every kth floor, then it has a best case 2, worst case B/k + (k-1), so on average, B/2k + (k+1)/2 = (2B + 2k² + 2k)/4k = (B + k² + k)/2k (am I even calculating this right?). If k = 1, average = B/2 + 1. If k = B, average = B/2 + 1. If we differentiate the average w.r.t k, we get -B/2k² + 1/2. This is 0 when k = sqrt(B), and for this k, we get average = sqrt(B) + 1/2. The binary search is still better than this.

By the way, this isn't a final answer, maybe there's something better than the binary search.

 

[LarrrSDonald]

I believe (although I'm at this time not at all in a position to prove it) that the optimal solutions will all wind up with f(N)*log(B) for N>=2, i.e. every static N>=2 has a k*log(B) solution (on average, best and worst may be further away and closer to it depending). My two "hint 2" solutions are certainly *way* not optimal in any way shape or form (as I'm sure you noticed) - I included them merely as a more solid example of what would consitute a working, albeit sub-optimal, solution (hint one is optimal but rather obvious once the problem is clear). I almost didn't even white them since they're no help once the problem is clear but I figured perhaps some retentive would want to try without them.

I'm really very prepared for people to algorithm circles around me - I by no means baffled anyone with my solutions a decade ago and though I've perhaps gotten a little better at practical algorithms I'm probably worse at the mathematical aspect.

[EDIT] For the f(N)*log(B) guess there may obviously also be floors, i.e. f(N)*|logx(B)| or something (where x is depenent on N and B). Dealing with discreet numbers this isn't avoidable mostly though not terribly significant for large N and B. The whole problem has an air of some of the incarnations of the weighing problem, I assume those who can solve it generally would make short work of this.

 

[NateTG]

IIRC this is a classic optimization problem:

Let's say we have $N$ grad students, $T$ trials, and $F$ floors.

Now, let's say we pick some floor $f$ to throw the student off of.
Then if the student makes it, we have the same problem, but with
$T-1$ trials and $F-f$floors, and $N$ grad students.

If the student does not make it, we have the problem with
$T-1$ trials and $f$floors, and $N$ grad students.

This leads to a recurrance relation for the best number of floors for $T$ trials and $N$ students:
$F_{\rm{max}}(T,N)=F_{\rm{max}}(T-1,N) + F_{\rm{max}}(T-1,N-1)$

Note: It doesn't take a whole lot to show that the recurrance relation above yields that
for $N\geq T$,
[tex]F_{\rm{max}}(T,N)=2^T-1[/itex]
which matches one of the cases that we know.

I expect that sophisticated attacks using the recurrance relation could yield a nice answer to the problem, but I'm too lazy for that.

So, let's shift gears, and look at how good the optimal solution can be:
Let's say we have some sort of testing program P with at most $T$ trials. Then we can write out the possible results of P as binary strings - with, say, 0 for a trial where the testing device was destroyed, and a 1 for a trial where it was not. Then the possible results are:
1111111...1
0111111...1
1011111...1
.
.
0011111...1
...
000000
...
..
.

If we pad the 'terminal' scenarios with 1's it's clear that the number of distinct scenarios that the program P can identify is going to be
$$F_{\rm{max}}(T,N) \leq \sum_{i=0}^{N}\left( \begin{array}{cc} T\\ i \end{array} \right)$$

Now, if we show that
$$\sum_{i=0}^{N}\left(\begin{array}{cc}T\\i\end{array}\right)= \sum_{i=0}^{N}\left(\begin{array}{cc}{T-1}\\i\end{array}\right)+ \sum_{i=0}^{N-1}\left(\begin{array}{cc}{T-1}\\i\end{array}\right)$$

Then with $T_1$ trials left, $N_1$ students left, and $F_1$ floors left to check, we can throw the student off of the:
$$f=\sum_{i=0}^{N_1-1}\left(\begin{array}{cc}{T_1-1}\\i\end{array}\right)$$
floor, and achieve an optimal solution.