Conference rusure::math

        Can you, um, reuse a cat that has already been dropped,
        but with nonfatal result?  How many times?
        
        :-)
        
        Dan

    Sorry, Dan.  My note was pretty clear on this.  The defenestrations are
    harmless or fatal.  The middle is excluded.  Maybe they're quantum cats.

        Well, after a harmless drop the cat might run away. :-)
        That's why I asked if it could be reused, i.e.,
        recaptured and redropped.
        
        Dan

Any time you drop from too high a floor you lose one subject (cat, grad 
student, mathematician - whatever disposable resource you want to measure)
and you are reduced to a linear search of the "intervening range" between
the last established safe floor and the lowest established fatal floor. As
long as bothn subjects survive you can search the intervening range as though 
it was the range 1-k, reducing the case to one already seen. So a formula 
for the cost of testing up to n floors is

	f(n) = 1+min(max(n-k,f(k)))
		 k<n
The cost table starts off thus:
	n	f(n)
	1	 1
	2	 2
	3	 2
	4	 3
	5	 3
	6	 3
	7	 4
	8	 4
	9	 4
	10	 4
	11	 5
e.g. there is one 1, two 2's, etc. F(n) increases roughly as sqrt(n): the 
values of n at which f(n) increases are 1,2,4,7,11... = 1+(m*m-m)/2, m=0...

Another way of looking at the solution is to represent in tree form, where 
right branches respresent linear searches with one subject, and left 
branches are recursive searches with two subjects. Pick the root so that 
the depth of the leftmost and rightmost branches differ by one or zero.

This problem is isomorphic to the infamous "quantal response
problem" (to which I am grateful for having provided ny
dissertation topic) if you only admit that cats have individual
differences.  As soon as you do admit that variation, this is a
difficult statistical issue.

To avoid this distraction, consider using identical pottery
vases dropped on the sidewalk from varying heights.  Only a
change of scale, you know.  And its less likely to get the
SPCA upset.   :-)  

fwiw,

Dick

    Lynn's .4 solves the problem for 2 cats.   (After all, he *owns* 2
    cats so should be expected to know the answer here. :-) )
    
    For n cats, the solution is still simple, and can be intuitively seen
    by looking at the pattern of the decision tree, as Lynn suggested for
    n=2.
    
    For n=1, the tree is linear.
    For n=2, the tree is triangular.
    For n, the tree is an n-simplex, and whenever you "lose" a cat, you drop
    into a simplex of dimension 1 less than you were in.
    
    Cheers,
    Andrew.

    re .4:
    
    	could someone help me understand this with an example ?
    Suppose we have to search till 100 floors, and the 1st fatal floor
    happens to be 50.
    So we start with a binary search, drop a cat from the 50th floor, it
    dies. Now we need to do a linear scan between floors 1 and 50 with the
    one surviving cat. So we drop this cat repeatedly from floors 1,2,3,
     ... 49. Thus, this strategy required a total of 50 drops to find the
    first fatal floor. 
    According to the formula in .4, the total number of drops should be
    14. 
       ?
    
    thank you,
    
     _Vasmi

    re .7
    You wouldn't start with 50. You would start with some number (such as
    10) and go up in steps of 10, until you get a fatality. In this case
    you would know that 40 is safe, and 50 unsafe. So you start at 41 and
    work upwards.
    
    Andrew
    
    p.s.
    
    10,20,30,40,50... is probably not the optimal sequence for the first
    cat, but I couldn't be bothered to work out what was.

    Re .7
    
    Here's how 100 floors are handled with two cats:
    
    Drop the first cat from the 14th floor.  If it dies, you must drop the
    remaining cat from each of the 13 floors from 1 to 13 until it dies or
    you have done all those floors, reaching a maximum of 14 tries.
    
    If the first cat does not die when dropped from the 14th floor, drop it
    from the 27th floor.  Now you have used up two drops.  If the first cat
    dies now, you must try each of the 12 floors from 15 to 26 -- a maximum
    of 2 plus 12, or again 14.
    
    If the first cat did not die, try the 39th floor, then the 50th, 60th,
    69th, 78th, 85th, 91st, 96th, and 100th.
    
    Upon each throw of the first cat, you will have made k throws already
    and you might have to try each of the 14-k intermediate floors if the
    first cat dies.  This skipping of as many floors as you can without
    raising the maximum is the most effective use of the first cat.
    
    
    				-- edp