A Hundred Thousand Switches, One Defect: How Few Tests?Date: 04/19/2011 at 22:39:14 From: David Subject: How many robots required to detect the defective lamps Suppose there are 100,000 lamps. One of them is defective. An operator has robots to identify the bad lamp. Each robot can test any number of lamps in one batch. If a lamp is OK, the robot will signal "OK." But testing a defective lamp damages the robot. It takes 1 hour to complete the test. The operator needs to finish testing the lamps within 2 hours. What's the fewest number of robots that an operator needs to find the defective item? I have tried spreading the 100,000 lamps on the Cartesian plane, representing each lamp as one of 316 x 317 points (which actually yields more than 100,000 points). I've put a robot at each positive integer unit on the x-axis and y-axis. So each x-axis robot can test all lamp on the vertical line (x = 1, 2, 3, ...); and similarly with y-axis robots testing horizontally. If the n-th robot (x-axis) and m-th robot (y-axis) are damaged, then we can locate the defective lamp at (n, m). But we can map out the lamps and robots multi-dimensionally, thus reducing the number of robots. How do you figure that out? Date: 04/20/2011 at 08:14:14 From: Doctor Anthony Subject: Re: How many robots required to detect the defective lamps If we number the lamps 1 to 100,000, then in binary scale we have 2^17 = 131,072 = 131,071 = 111......1111111 (17 1's) So 17 robots will be sufficient. Robot 1 determines the rightmost 2^0 digit, Robot 2 determines the 2^1's digit, Robot 3 determines the 2^2's digit, and so on. If we count '1' as a robot being damaged and '0' for a robot signalling OK, then after 1 hour a result of, for example, 00000000011001010 means that lamp number 202 is defective. With problems like this, it is often helpful to start with smaller numbers and see if you can find a pattern. Suppose we have 31 lamps and 5 robots. 31 = 2^4 + 2^3 + 2^2 + 2 + 1 = 11111 (base 2) So if lamp number 31 is the damaged lamp, our system must ensure that every robot tests that lamp. 30 = 11110 29 = 11101 28 = 11100 27 = 11011 26 = 11010 25 = 11001 24 = 11000 23 = 10111 22 = 10110 21 = 10101 20 = 10100 19 = 10011 18 = 10010 17 = 10001 16 = 10000 15 = 01111 14 = 01110 13 = 01101 12 = 01100 11 = 01011 10 = 01010 9 = 01001 8 = 01000 7 = 00111 6 = 00110 5 = 00101 4 = 00100 3 = 00011 2 = 00010 1 = 00001 Starting with the right-hand digit, Robot 1 must test lamps 1, 3, 5, 7, ...., 29, 31 Robot 2 must test lamps (2, 3), (6, 7), (10, 11), (14, 15), (18, 19), (22, 23), (26, 27), (30, 31) Robot 3 must test lamps (4, 5, 6, 7), (12, 13, 14, 15), (20, 21, 22, 23), (28, 29, 30, 31) Robot 4 must test lamps (8, 9, 10, 11, 12, 13, 14, 15), (24, 25, 26, 27, 28, 29, 30, 31) Robot 5 must test lamps (16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31) From these figures, it is easy to see the pattern involved -- a pattern that can clearly be extended to 17 robots and 100,000 lamps. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ Date: 04/20/2011 at 18:31:59 From: David Subject: How many robots required to detect the defective lamps Thanks, Will it make any difference if the testing is to be completed in 2 hours, i.e., by 2 consecutive tests? Can the number of robots be reduced? Regards Date: 04/21/2011 at 04:55:53 From: Doctor Anthony Subject: Re: How many robots required to detect the defective lamps Yes, but only by 1. The same robots could be used in two shifts. If we take 50,000 lamps, we have 2^16 = 65536. So two lots of 16 will cover the 100,000 lamps. Saving one robot in this way is probably not worth the trouble. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/