How to Cut a Cake: And Other Mathematical Conundrums by Ian Stewart

Author:Ian Stewart [Stewart, Ian]
Language: eng
Format: epub, mobi
Tags: Games, Puzzles, Mathematics, General
ISBN: 9780199205905
Google: 7ko_AQAAIAAJ
Amazon: 0199205906
Publisher: Oxford University Press
Published: 2006-12-10T16:00:00+00:00

Figure 29 Attaching two probes: one to all the red nets, one to all the green nets (here just one).

If the PCB has been correctly made, no current will flow, because the red probe connects only to red nets, the green probe connects only to green nets, and on the PCB no red net should connect to any green net. However, if the PCB contains a fabrication fault that links a red net to a green one, then current will flow between the two probes. Now, any fabrication fault in the PCB necessarily connects two adjacent nets, and these must have different colours. So when the PCB is tested using the corresponding two probes, a current will flow in the test device.

Notice that this test doesn’t tell us where the error is. But since we are discarding all faulty PCBs, not repairing them, we don’t need to know that. The upshot is that in order to detect the presence of a fabrication fault, it is enough to check for the existence of electrical connections – through the conducting material of the board – between all possible pairs of probes. Since there are only 12 probes, the number of such pairs is 12 × 11/2 = 66. So instead of 125,000 or more tests, we need only 66 – already a major improvement.

However, we can easily do better (Figure 30). Test probe 1 against probe 2; throw out any PCBs with connections between them. Now add a ‘gate’ to connect probes 1 and 2. Test probe 3 to see if it connects to the circuit formed by probes 1, 2, and the gate. If so, then probe 3 connects either to probe 1 or to probe 2. Either eventuality is a mistake, so we don’t care which one occurs: we just throw the PCB out. Now add a second gate connecting probe 3 to the previous two, and continue in this manner. That gets the number of checks down to 11.

Allen Schwenk (West Michigan University, Kalamazoo) realized that a further reduction can be made. Write the numbers 1, …, 12 in binary: 0001 up to 1100. Make a ‘superprobe’ that connects all probes that start with 0; make another that connects those starting with 1. Test whether these two superprobes are connected. If so, throw out the PCB. If not, create two more superprobes connecting probes that have the same binary digit in the second place. Check whether these are connected. Do the same for the third place and the fourth place in the binary expression. That’s it. To see why it works, note that if two distinct probes are connected by a short circuit, then their binary expressions must differ in at least one of the four places, so one or other of the four tests will detect the mistake.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.