Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/ 
Associated Topics:
High School Logic
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/