Puzzle of the Week for 11 January 1999: Hints

If there were only one bit that could be used for testing, the only safe strategy would be to test at 100 rpm, 200 rpm, 300 rpm, etc., until the bit was destroyed or we reached 6000 rpm. Following this approach, we might need to perform as many as 60 tests, so the cost would be 60 * \$10, or \$600, in the worst case. (This would be the "worst case" in terms of the cost of the test, that is. It would be the best case in terms of the reliability of the drill bit!)

If we have two bits, other testing strategies are possible. For example, we can test at 3000 rpm first. If the first bit fails this test, we can test the second one at 100 rpm, 200 rpm, 300 rpm, etc.; on the other hand, if the first bit passes the test at 3000 rpm, we might try 6000 rpm next, and then test the second bit at 3100 rpm, 3200 rpm, 3300 rpm, etc. if the first bit fails at 6000 rpm. Using this strategy, we will need at most 31 tests at a cost of \$310.

It's possible to do much better than this, however, with a variety of other strategies. If we can get additional test bits, we can save even more.

By the way, bits that can drill (almost) square holes actually exist! How would you design one?