|
If the goal is to minimize the maximum number of tests then that maximum for n glasses is log2n (log to the base 2 of n), rounded up.
If the number of glasses is a power of 2 (32, 64, 128, 256, etc.) then the correct procedure on the first step would be to test exactly half the glasses. Then test half of the glasses in the positive half next. Keep repeating this procedure. Each step will narrow down the field of poisoned glasses by a factor of 2.
If the number number of glasses is not a power of 2 then there are lots of ways you can test them and still achieve the same maximum number of tests. One way would be to find the closest power of 2 less than n, set this many glasses aside, and then test the others. The only n for which this remainder is 1, between 100 and 200, is 129. In the case of 129 the first test would likely be negative. Then proceed with the procedure for testing 128. Between the first test and the log2128 the maximum number of tests is 8. |
