REKREACJE MATEMATYCZNE
Ian Stewart
Cesarstwa i elektronika
poprzednim miesiÄ…cu zajmo- Na jednej kromce rysujemy kraw´dzie
waliĘmy si´ kolorowaniem z pierwszego zbioru, tak by si´ nie prze-
‚map. ChociaÅ» problem ten wy- cina"y, na drugiej zaĘ  drugi zbiór kra-
daje si troch´ niepowaÅ»ny, matematy- w´dzi, takÅ»e bez Å»adnych przeci´ç.
ka, b´dÄ…ca jego podstawÄ…, jest ca"kiem Wierzcho"ki rozszerzone do linii piono-  KANAPKA przedstawia graf
uÅ»yteczna. Mapy wiąŻą si´ z grafami  wych tworzÄ… nadzienie. Graf, który po- gruboĘci dwa: dwa p"askie grafy,
których wierzcho"ki zosta"y rozciÄ…gni´te
diagramami, w których wierzcho"ki sÄ… trzebuje t warstw chleba, ma gruboĘç t.
do pionowych linii.
po"Ä…czone liniami zwanymi kraw´dzia- Na poczÄ…tek wyobraÄ™my sobie obwód
mi. GruboĘç grafu, poj´cie wprowadzo- elektryczny w postaci grafu. Jego w´z"y
ne przy okazji zagadnienia cesarstw na sÄ… elementami elektronicznymi, a kra- przewodzÄ…cego. ÂcieÅ»ki pe"niÄ… funkcj´
Ziemi i Ksi´Å»ycu, zosta"a niedawno po- w´dzie po"Ä…czeniami elektrycznymi. Je- drutu "Ä…czÄ…cego komponenty. Bardzo
Å»ytecznie wykorzystana w produkcji ob- Ęli uk"ad scalony mamy zbudowaç po waÅ»nym problemem dla producentów
wodów scalonych. Związek ten przed- jednej stronie p"ytki z obwodem druko- obwodów scalonych jest wykrywanie
stawi"a Joan P. Hutchinson z Macalester wanym, to musi byç on p"aski, by unik- p"ytek ze zb´dnymi po"Ä…czeniami  do-
College w St. Paul (Minnesota) w arty- nÄ…ç zwarç. WykorzystujÄ…c obie strony datkowych kawa"ków ĘcieÅ»ek, które "Ä…-
kule wydrukowanym w czasopiĘmie Ma- p"ytki  analogicznie do dwóch kromek czą elektrycznie komponenty tam, gdzie
thematics (vol. 66, nr 4, paÄ™dziernik 1993). chleba w kanapce  moÅ»emy konstru- nie powinny one byç po"Ä…czone.
Zastosowanie to odkryli naukowcy owaç grafy gruboĘci dwa. Wraz z liczbÄ… Ze wzgl´dów praktycznych produ-
z AT&T Bell Laboratories w Murray Hill p"ytek gruboĘç grafu b´dzie ros"a. Po- cenci obwodów scalonych "Ä…czÄ… kompo-
(New Jersey). Przypomnijmy, Å»e graf dobne rozwaÅ»ania daje si´ stosowaç do nenty na p"ytce drukowanej w  sieci .
nazywamy p"askim, gdy moÅ»na go na- bardziej zaawansowanych technologicz- Sieç jest zbiorem komponentów po"Ä…czo-
rysowaç na p"aszczyÄ™nie, tak by Å»adne nie obwodów scalonych, poniewaÅ» w nych ĘcieÅ»kami tak, by nie zawiera"y za-
jego dwie kraw´dzie si´ nie przecina"y. bardzo duÅ»ej skali integracji (VLSI  ve- mkni´tej p´tli. Problem, który nas inte-
Nast´pnym etapem jest graf gruboĘci ry large scale integration) obwody mu- resuje, to stwierdzenie, czy dwie róŻne
dwa, którego kraw´dzie moÅ»na podzie- szÄ… byç budowane warstwami. sieci mogÄ… zostaç przypadkowo zwarte.
liç na dwa zbiory w taki sposób, Å»e kaÅ»- Typowa p"ytka z obwodem druko- Najprostszym sposobem jest sprawdze-
dy z nich jest p"aski. Graf ma gruboĘç wanym jest uk"adem 100 na 100 dziur, nie, czy wszystkie pary sieci sÄ… po"Ä…czo-
trzy, gdy jego kraw´dzie moÅ»na pogru- w których mogÄ… byç umieszczone kom- ne. MoÅ»na skonstruowaç obwód biegnÄ…-
powaç w trzy takie zbiory itd. ponenty elektroniczne po"Ä…czone pozio- cy od jednej sieci do dodatniego bieguna
Graf o gruboĘci dwa moŻna sobie wy- mymi i pionowymi liniami; te moŻna baterii i od ujemnego bieguna baterii po-
obraziç jako coĘ w rodzaju  kanapki . z kolei pokryç  ĘcieÅ»kami materia"u przez Å»arówk´ do drugiej sieci. JeĘli b´-
dÄ… one przypadkiem po"Ä…czone, to po-
p"ynie prÄ…d i Å»arówka si´ zapali.
OczywiĘcie w prawdziwych urządze-
niach testujÄ…cych stosuje si´ bardziej
skomplikowanÄ… elektronik´, jak choç-
by komputer sprz´Å»ony z robotem, któ-
ry automatycznie wyrzuca wadliwe
p"ytki, ale podstawą jest w"aĘnie ta idea.
K"opotów przysparza fakt, Że n sieci wy-
maga n(n  1)/2 prób  tyle ile jest par
sieci. PoniewaÅ» zwykle jest 500 sieci,
oznacza to, Że kaŻda p"ytka wymaga
125 tys. testów, a wi´c o wiele za duÅ»o.
StosujÄ…c poj´cie gruboĘci grafu, moÅ»e-
my bardzo szybko zmniejszyç liczb´ te-
stów do zaledwie 11. W rzeczywistoĘci
odrobina pomys"owoĘci zredukuje t´
liczb´ do jedynie czterech.
Punktem wyjĘcia jest zamiana sche-
matu p"ytki z obwodem drukowanym
P¸YTKA Z OBWODEM DRUKOWANYM zawiera dziury (kó"ka), w których znajdujÄ… si´
komponenty (kwadraty). Komponenty są po"ączone ĘcieŻkami metalu w  sieci ;
przyleg"e sieci majÄ… róŻne kolory. Ale niepotrzebne ĘcieÅ»ki (czarne) mogÄ… powodowaç b"´dy,
"Ä…czÄ…c przyleg"e sieci. JeĘli przyczepimy Å»aróweczk´ z bateriÄ… do obwodów testujÄ…cych
sieç zielonÄ… i niebieskÄ…, to zwarcie pozwoli na przep"yw prÄ…du i Å»aróweczka si´ zaĘwieci.
+ 
72 ÂWIAT NAUKI Listopad 1997
JENNIFER C. CHRISTIANSEN
JENNIFER C. CHRISTIANSEN
Wydawnictwo
w graf, który zawiera informacje o zwar-
ciach. Nazwijmy go grafem sieci obwodu
scalonego. PoniewaŻ szukamy krótkich
spi´ç pomi´dzy róŻnymi sieciami, to kaÅ»-
dej sieci przypisujemy jeden w´ze".
proponuje:
Kraw´dzie tego grafu sieci reprezen-
tujÄ… potencjalne, a nie rzeczywiste zwar-
cia (gdybyĘmy bowiem wiedzieli, gdzie
Jak dzia"ajÄ… witaminy i mikroelementy?
te zwarcia sÄ…, nie musielibyĘmy testowaç
Czy moÅ»na i naleÅ»y braç je w tabletkach?
obwodu). MówiÄ…c ĘciĘlej, dwa w´z"y gra-
Czy ich nadmiar moÅ»e zaszkodziç?
fu sieci b´dÄ… po"Ä…czone kraw´dziÄ…, gdy Czytelnik znajdzie w ksiÄ…Å»ce odpowiedzi
na te i inne pytania, proponowane dawki,
tylko odpowiadajÄ…ce im sieci sÄ…  przyle-
opis zalecanej diety, a takŻe ograniczenia
g"e  co oznacza, Å»e moÅ»na je "Ä…czyç po-
w stosowaniu i objawy niepoŻądane.
ziomą lub pionową linią prostą, która nie
Autorzy ksiąŻki bardzo rzetelnie opisują
przechodzi przez inne poĘrednie sieci.
potwierdzone wynikami badał

OczywiĘcie zwarcie moŻe teoretycznie
mechanizmy dzia"ania witamin
nastÄ…piç pomi´dzy dwoma nie przylega- i mikroelementów, jak równieÅ»
omawiajÄ… przypisywane,
jÄ…cymi sieciami. Ale prawie wszystkie ta-
a nie udowodnione korzyĘci
kie spi´cia muszÄ… takÅ»e "Ä…czyç przyleg"e
ze stosowania tych sk"adników.
sieci. Fabryczny robot zazwyczaj dwu-
W ksiąŻce podane są równieŻ polskie
krotnie przechodzi nad p"ytkÄ…: raz robiÄ…c
nazwy preparatów i zalecane w Polsce
po"Ä…czenia poziome, a drugi raz drukujÄ…c
dzienne zapotrzebowanie na te sk"adniki,
pionowe. B"´dy si´ pojawiajÄ…, gdy po"o- w zaleÅ»noĘci od wieku i kondycji.
Autorami  Witamin i mikroelementów
Ży on za duŻo materia"u przewodzące-
są najlepsi lekarze amerykał
scy,
go, nieopatrznie "Ä…czÄ…c dwie sieci. Taki
którym patronuje Farmakopea Stanów
b"Ä…d nazywamy  produkcyjnym . (SÄ…
Zjednoczonych (USP)  organizacja
takŻe inne, znacznie rzadsze sposoby wy-
ustanawiająca standardy leków
produkowania wadliwych p"ytek, ale nie
i preparatów odŻywczych w USA.
b´dziemy ich tu rozwaÅ»aç.) Ta dodatko-
wa linia materia"u przewodzącego moŻe
biec przez kilka sieci, ale dwie z nich b´-
dÄ… przyleg"e. Tak wi´c wystarczy rozwa- cena ok"adkowa 9,90 z" cena w sprzedaÅ»y wysy"kowej 5,50 z"
Å»yç tylko przyleg"e sieci.
Za"oŻy"em wczeĘniej, Że graf p"ytki
z obwodem drukowanym ma gruboĘç
dwa, co odpowiada jej dwóm stronom.
Z tych samych powodów graf sieci ma
gruboĘç dwa. Ale w myĘl twierdzenia
Autor s"ynnej  Biblii witamin , dr Earl
sformu"owanego przez XIX-wiecznego
Mindell, raz jeszcze doradza, jak Å»yç
brytyjskiego matematyka Percy ego Joh-
i odÅ»ywiaç si´ zdrowo. Przedstawia
100 sk"adników pokarmowych, zió",
na Heawooda kaŻdy graf gruboĘci dwa
witamin i mikroelementów potrzebnych
moÅ»na pokolorowaç 12 kolorami. KaÅ»de-
Earl Mindell
cz"owiekowi dla zachowania dobrej
mu wi´c wierzcho"kowi moÅ»emy przy-
formy, opisujÄ…c mechanizm ich dzia"ania,
AUTOR  BIBLII WITAMIN
pisaç jeden z dwunastu kolorów, tak by
potencjalne korzyĘci i ograniczenia
wierzcho"ki po"Ä…czone kraw´dziÄ… by"y
w stosowaniu. Szczególne znaczenie
róŻnych barw. MoŻemy teraz to poko- przywiązuje do tych sk"adników diety,
które mogą w znaczący sposób
lorowanie odnieĘç do sieci uk"adu sca-
BIBLIA
BIBLIA
przyczyniç si´ do obniÅ»enia poziomu
lonego. A zatem kaŻdej sieci przypo-
cholesterolu oraz byç przydatne
w profilaktyce przeciwnowotworowej.
Autor omawia równieÅ» cz´ste
M¸ODOÂCI
M¸ODOÂCI
dolegliwoĘci i schorzenia wieku
Ęredniego i starszego (m.in. chorob´
Alzheimera, choroby nowotworowe,
STO SK¸ADNIKÓW POKARMOWYCH,
choroby zwyrodnieniowe stawów)
OD KTÓRYCH ZALEÚY
i radzi, jak im zapobiegaç. Choç do
ZDROWIE
niektórych informacji naleÅ»y podchodziç
I DOBRE SAMOPOCZUCIE
z pewnym dystansem, na pewno
proponowane przez autora dieta
i styl Å»ycia pomogÄ… utrzymaç si´
w dobrej formie i prowadziç
zdrowy tryb Życia.
GRAF SIECI obwodu scalonego
przedstawionego obok ma gruboĘç dwa,
Cena ok"adkowa 14,60 z" cena w sprzedaŻy wysy"kowej 10 z"
po jednej dla kaŻdej strony p"ytki.
KaÅ»da sieç jest reprezentowana
przez wierzcho"ek (w´ze");
przyleg"e wierzcho"ki sÄ… po"Ä…czone KsiÄ…Å»ki moÅ»na kupiç w ksi´garniach lub zamówiç w sprzedaÅ»y wysy"kowej:
kraw´dziami  to potencjalne zwarcia. listownie w Klubie KsiÄ…Å»ki Ksi´garni Krajowej, skrytka pocztowa 21, 02-600 Warszawa13;
telefonicznie pod numerami: 0-800-244-88 (po"Ä…czenie bezp"atne) oraz (0-22) 43-51-21 i 43-41-61.
Koszt wysy"ki 3 z".
JENNIFER C. CHRISTIANSEN
NowoĘç
ZapowiedÄ™
"Ä…czenia. Teraz dodajmy bramk´ lub
+ 
prze"Ä…cznik pomi´dzy obwodami testu-
jącymi 1 i 2. Sprawdęmy dalej, czy ob-
wód testujący 3 jest po"ączony z obwo-
dem utworzonym przez po"Ä…czenie
obwodów 1 i 2. JeĘli tak, to jest on po"ą-
czony z obwodem testujÄ…cym 1 lub 2.
W kaŻdym przypadku jest to b"ąd i od-
rzucamy t´ p"ytk´. Nast´pnie dodajmy
drugÄ… bramk´ "Ä…czÄ…cÄ… obwód testujÄ…cy
3 z dwoma poprzednimi i sprawdęmy
naszÄ… p"ytk´ jak poprzednio. W ten spo-
BRAMKI lub prze"Ä…czniki "Ä…czÄ…
sób wystarczy jedynie 11 testów.
kolejno 12 obwodów testujących,
OBWÓD TESTUJŃCY "ączy Allen J. Schwenk z West Michigan
zmniejszajÄ…c ca"kowitÄ… liczb´ testów
wszystkie sieci danego koloru.
University w Kalamazoo zorientowa"
wykrywajÄ…cych zwarcia.
UmieszczajÄ…c Å»aróweczk´ pomi´dzy
si´, Å»e liczb´ testów moÅ»na jeszcze bar-
Żó"tym i niebieskim obwodem testującym,
dziej zredukowaç. Zapiszmy liczby 1,
moÅ»emy wykryç zwarcie
2, ..., 12 w systemie dwójkowym: 0001 czone, to ich binarne zapisy róŻniÄ… si´
pomi´dzy sieciami o tych kolorach.
aÅ» do 1100. Ponumerujmy odpowiednio co najmniej jednÄ… cyfrÄ…, a wi´c jeden
nasze obwody testujące. Przygotujmy z czterech testów wykryje b"ąd.
rządkowujemy jeden z dwunastu kolo-  superobwód testujący, który "ączy Zmniejszenie liczby testów ze 125 tys.
rów w taki sposób, by sieci o tej samej wszystkie obwody testujące zaczynają- do zaledwie czterech jest tym cenniejsze,
barwie nigdy do siebie nie przylega"y. ce si´ od 0 oraz drugi "Ä…czÄ…cy wszystkie im wi´ksza jest produkcja, poniewaÅ» wy-
PoniewaÅ» poszukujemy zwarç pomi´- obwody testujÄ…ce zaczynajÄ…ce si´ od 1. maga budowy tych skomplikowanych
dzy przyleg"ymi sieciami, to wiemy, Że Sprawdęmy teraz, czy te dwa super- obwodów i superobwodów testujących
moÅ»emy si´ ograniczyç do spi´ç pomi´- obwody sÄ… po"Ä…czone; jeĘli tak, to od- tylko raz dla kaÅ»dego typu p"ytki.
dzy sieciami o róŻnych barwach. W tym rzucamy badany obwód scalony. JeĘli W ubieg"ym miesiÄ…cu zacz´liĘmy od
celu dla kaÅ»dego z 12 kolorów konstru- nie, to konstruujemy dwa nowe super- kolorowania map cesarstw ziemsko-ksi´-
ujemy  obwód testujący . Ta struktura obwody "ączące obwody testujące o tych Życowych, a dziĘ koł
czymy na oszcz´d-
podobna do rozga"´zieÅ‚
drzewa zrobio- samych cyfrach na drugim miejscu ich nej metodzie testowania p"ytek z obwo-
na jest z materia"u przewodzÄ…cego i "Ä…- binarnego zapisu. Nast´pnie sprawdza- dami drukowanymi. To, co jest waÅ»ne w
czy wszystkie sieci danego koloru. my, czy są one po"ączone. To samo robi- matematyce, to nie szczególna reali-
PrzypuĘçmy, Å»e wybraliĘmy dwa ko- my dla trzecich i czwartych cyfr dwój- zacja jakiejĘ idei, ale moÅ»liwoĘci, jakie
lory  niebieski i Żó"ty. Przyczepiamy na- kowego zapisu. I tyle. Sprawdzając ona daje, gdy rozwijamy ją sprytnie i z
sze obwody testujÄ…ce koloru niebieskie- zasadnoĘç tego testu, pami´tajmy, Å»e je- wyobraÄ™niÄ….
T"umaczyli
go i Żó"tego do p"ytki z obwodem dru- Ęli dwa róŻne obwody testujące są po"ą- Zdzis"aw Pogoda i Robert Wolak
kowanym, uwaÅ»ajÄ…c, by ich nie po"Ä…czyç.
Nast´pnie pod"Ä…czamy bateri´ i Å»aró-
weczk´ do naszych obwodów testujÄ…-
SPRZóÚENIE ZWROTNE
cych i sprawdzamy, czy p"ynie prÄ…d.
JeĘli obwód scalony zosta" wykona-
ilka miesi´cy temu [Âwiat Nauki, ta droga na szachownicy 8 x 8 o nast´-
ny poprawnie, to nie pop"ynie Żaden
Kczerwiec 1997] omawialiĘmy kla- pującej w"asnoĘci: jeĘli kolejne po"oŻe-
prąd, poniewaŻ niebieski obwód testu-
syczny problem w´drówki konia szacho- nia skoczka oznaczymy numerami od 1
jący "ączy jedynie niebieskie sieci, Żó"ty
wego. Solomon W. Golomb z Universi- do 64, to liczby te utworzÄ… kwadrat ma-
zaĘ jedynie Żó"te sieci, a na p"ytce z ob-
ty of Southern California napisa", Że giczny (tzn. sumując osobno wszystkie
wodem drukowanym Żadna niebieska
udowodni" kilka wyników na ten temat rz´dy, kolumny i przekÄ…tne dostaniemy
sieç nie powinna byç po"Ä…czona z sieciÄ…
w artykule  Of Knights, Cooks, and the te same wyniki). Nie udowodniono ani
Å»ó"tÄ…. Gdy jednak wyst´puje b"Ä…d  pro-
Game of Cheskers opublikowanym istnienia, ani teÅ» nieistnienia takiej dro-
dukcyjny "Ä…czÄ…cy sieç niebieskÄ… z Å»ó"- w Journal of Recreational Mathematics gi, ale znanych jest kilka prawie ideal-
tÄ…, to prÄ…d pop"ynie.
(vol. 1, nr 3, ss. 130-138; lipiec 1968). nych rozwiązał
:
Zwróçmy uwag´, Å»e test nie wskaÅ»e Praca ta zawiera m.in. twierdzenie przy-
nam, gdzie jest b"ąd. PoniewaŻ odrzuca- pisywane Louisowi Pósa  Że szachow- (a) droga skoczka, w przypadku której
my wszystkie wadliwe p"ytki z obwo- nica 4 x n nie dopuszcza zamkni´tej w´- rz´dy i kolumny sumujÄ… si´ do 260, ale
drówki skoczka po wszystkich polach, nie przekątne,
dami drukowanymi (nie naprawiamy
oraz twierdzenie o istnieniu takiej drogi (b) magiczny kwadrat utworzony z po-
ich), to nie musimy tego wiedzieç. Úeby
na szachownicy 3 x 10. "ówek drogi skoczka (1 32 oraz 33 64),
znaleÄ™ç b"Ä…d produkcyjny, wystarczy
Z kolei Andy Campbell z West Hart- z których kaÅ»da pokrywa po"ow´ sza-
sprawdziç wszystkie pary obwodów te-
ford (Connecticut) przypomina problem chownicy,
stujÄ…cych. Jest ich tylko 12, a zatem licz-
magicznej drogi konia. Jest to zamkni´- (c) magiczna droga króla.
ba tych par wynosi 12 x 11/2 = 66. Za-
miast wi´c 125 tys. lub wi´kszej liczby
c
a b
19 36 64
46 55 44 58 9 22 7 15 20 17 13 64 61 34 61 62 63 1 2 3 4
testów wystarczy przeprowadziç tylko
56 21 57
43 18 47 21 6 59 10 18 37 14 60 35 12 63 60 11 58 8 7 54 5
66  a to oznacza juÅ» post´p.
41 44 9
54 45 20 12 57 8 23 25 16 19 5 62 33 56 12 59 10 56 55 6 53
MoŻemy jednak jeszcze bardziej upro-
48 59 16
17 42 53 5 24 11 60 38 45 26 22 55 4 11 13 14 15 49 50 51 52
Ęciç operacj´. SprawdÄ™my obwody testu-
13 27 6 20 17
52 3 32 40 61 34 25 24 39 43 10 57 54 19 18 48 47 46 45
jÄ…ce 1 i 2; odrzuçmy wszystkie p"ytki
4 40 23 21 24
31 16 49 33 28 37 62 49 46 58 3 32 9 38 23 41 42 27 44
29 47 42 37 40
z obwodami drukowanymi majÄ…ce po- 2 51 14 64 39 26 35 28 51 7 30 53 2 22 39 25 26 43 28
15 30 1 50 27 36 63 38 50 41 48 29 52 1 8 31 36 35 34 33 32 31 30 29
74 ÂWIAT NAUKI Listopad 1997
JENNIFER C. CHRISTIANSEN
JENNIFER C. CHRISTIANSEN
JENNIFER C. CHRISTIANSEN