Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
Rozdział1.ORGANON
Marienbadu,zabawialisiętąniewątpliwiegodnąuwagigrą.Grętęszczegó-
łowoopiszemy,byczytelnikowizademonstrowaćsiłęukładubinarnego;
optymalnastrategia–dziękidwójkowemuzapisowi–jestniezwykleprosta,
abezsystemubinarnegobardzotrudnadowyrażenia.Grajestdwuosobowa.
Określonąliczbęzapałek(wielkośćtaniejestważnadlazrozumieniaistoty
gry)podzielononakilkakupek–zespołów.Dlaustaleniauwagiprzyjmij-
my,żetakichczęścijestk;niechi-tystosliczynizapałek,i=1,...,k.Gra-
czenaprzemianwykonująruchy,zwanetutajciągnieniami.Każdygracz,
gdyruchdoniegonależy,możezabraćdowolnąliczbęzapałekzwybranej
przezsiebiekupki.Jeśliciągniezi-tegostosu,toliczbaxzabranychzapałek
spełniawarunki:1ŚxŚni,gdzienioznaczaaktualnąliczbęzapałekwi-tym
stosie.Gracz,któryweźmieostatniązapałkę,wygrywa.Czyistniejestrate-
giawygrywająca?Któryzgraczymastrategięzapewniającązwycięstwo?
Odpowiedźnatepytaniajestzależnaodwektora(n1,...,nk).Zanimodpo-
wiemy,przypomnijmy,żewkażdymciągnieniumożnabraćzapałkitylko
zjednejkupki;należywziąćprzynajmniejjedną,aleniewięcejniżwtym
stadiumgryjestwtejwłaśniekupce.Graczmapełnąswobodęwyborusto-
sóworazdecydujeoliczbie–wdopuszczalnychgranicach–wybranych
zapałek.Zakładamytu,żegraczeniepopełniająbłędówiznająstrategię
optymalną,którązachwilępodamy.Algorytmgwarantującyzwycięstwo
jednemuzgraczyzależyodpewnejmacierzyowyrazachbędącychzerami
ijedynkami.Macierzetakiedzielimynaparzysteinieparzyste.Macierzjest
parzysta,jeśliwkażdejkolumniejestparzystaliczbajedynek.Brakjedynek
jestparzystąliczbąjedynek.Wprzeciwnymrazie,gdyprzynajmniejwjed-
nejkolumniejestnieparzystaliczbajedynek,macierznazywasięnieparzy-
stą.Wektorowi(n1,...,nk)przyporządkowujemymacierz
M(n1,...,nk)=(aij),
gdzieaijjestj-tącyfrąwrozwinięciudwójkowymliczbyni.Macierz
M(n1,...,nk)makwierszy,każdejwięckupceodpowiadajedenwiersz,na-
tomiastliczbakolumnzależyodukładuliczbni:jesttakąnajwiększąliczbą
naturalnąm+1,że2mŚmax{n1,...,nk}.Ewentualnebrakującecyfryna
początkuuzupełniamyzerami.Jeżeliprzykładowo:n1=4,n2=5oraz
n3=10,to
M(4,5,10)=
(
|
|
k
1
0
0
1
1
0
0
0
1
0
1
0
N
|
|
)
,
20
