You are studying the effects of gravity on clay spheres. You conjecture that they will shatter... but at what height? You want to find out the smallest integral height in meters from which the clay will fall and shatter.

Unfortunately, you only have four identical clay spheres, at least until the company that makes them starts returning your calls. Also, you only have enough time for 8 tests, during which the general area will be cleared of people. Last time someone did such an experiment, an egg... well, it was messy. Up to what height can you test the effects of gravity on the clay?

The first pot is dropped at 64 meters. If it breaks, we follow this scheme to determine the smallest integral height of failure.
                            64
                           /
    ___________22____________                                    
  6_                       _________38_________                          
1   11__               27_                      _____49______                
2  7    15           23    31               42_              ____56____       
3  8  12  18        24 28   34        39    45         52             _60_
4  9  13 16  20    25 29 32  36    40  43   47   50  54       58     62
5 10 14 17 19 21 26 30 33 35 37 41 44 46 48 51 53 55 57 59 61 63

If the pot dropped from 64 meters survives, we drop the second pot from 106 meters. Should that one break, we follow this scheme:
             64__________________________________
                      _____________________________106
     ________80_________                              
  69_                   _______91______                        
65   73_            _84_              ____98_____
66 70   76       81    87_        94             _102_     
67 71 74  78    82 85   89    92  96      100       104   
68 72 75 77 79 83 86 88 90 93 95 97 99 101 103 105

If the pots dropped from 64 and 106 meters survive, we drop a pot at 132 meters. If that breaks we follow this scheme:
64
  106_________________________________
                        _______________________132
      ________117__________                          
  110                         _____124______                        
107   113             _120_              __128__
108 111   115     118    122       126        130  
109 112 114 116 119 121 123 125 127 129 131

And finally, should pots dropped from 64, 106, and 132 survive we follow this scheme:
64
  106
     132__________________
                   ____________ 147____________
      _____139______                         ______155_____ 
  135__                _143_                _151_                _159_
133   137         141      145        149       153        157       161
134 136 138 140 142 144 146 148 150 152 154 156 158 160 162   
Again, this corresponds with our being able to test 8C4+8C3+8C2+8C1+8C0 = 2^7 + (8C4/2) = 163 outcomes including zero. So the greatest value for smallest integral height we can test is 162 meters.



Edited on May 5, 2006, 3:35 am

Edited on May 5, 2006, 3:51 am

Edited on May 5, 2006, 4:01 am

Edited on May 5, 2006, 4:01 am

Edited on May 5, 2006, 9:48 pm

Posted by Eric on 2006-05-05 03:04:00