P R E S E K
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652 Letnik 26 (1998/1999) Številka 4 Strani 226-229
Primož Potočnik:
KRIŽCI IN KROŽCI OŽIVLJENI
Ključne besede: zanimivosti, razvedrilo, matematika, rekreacijska matematika, matematične igre, kombinatorika, permutacije, avtomor-fizmi.
Elektronska verzija: http://www.presek.si/26/1376-Potocnik.pdf
© 1999 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo
KRIŽCI IN KROZCI OŽIVLJENI
Gotovo se je vsak od nas vsaj enkrat že poskusil v igri, ki jo poznamo pod imenom križci in krožci. Vseeno na hitro ponovimo pravila. V3x3 tabelo dva igralca - nasprotnika - izmenično vrisujeta eden križce, drugi krožce, Če komu od igralcev uspe zasesti eno od treh vrstic, treh stolpcev ali dveh diagonal, je zmagovalec.
Igro lahko predstavimo tudi drugače. Devet polj 3x3 tabele zamenjamo z devetimi točkami v ravnim. Če smo točke razporedih, kot kaže slika 2, lahko skoznje potegnemo osem ravnih črt, katerih vsaka povezuje tiste točke, ki so prej ležale bodisi v skupnem stolpcu bodisi v skupni vrstici bodisi na skupni diagonali. Igralca sedaj izmenično barvata točke, vsak s svojo barvo, zmaga pa tisti, ki s svojo barvo prvi pobarva vse točke neke črte.
		X
	0	
		
Slika 1. Križci in krožci.
8	3
	
	
I	2	3
Slika 2. Križci in krožci — malo drugače.
Zdrava pamet nam pove, da je igralec, ki začne, v prednosti in da je najpametneje pobarvati tisto točko, ki leži na največ črtah. S slike 2 je razvidno, da točka 5 leži na štirih črtah, točke 1,3,7 in 9 na treh črtah, točke 2,4,6 in 8 pa le na dveh črtah. Zato je za prvega igralca - recimo mu napadalec - najbolje, da pobarva točko 5. Drugi igralec branilec — mora igrati pazljivo. Če zasede katero od točk, ki ležijo le na dveh ČTtah. bo lahko napadalec s pravilno igro zmagal. Če pa branilec v svoji prvi potezi zasede eno od točk 1,3,7 ali 9, bo uspel obdržati ravnotežje in pripeljati igro do neodločenega izida. S tem smo vse možnosti izčrpali.
Ostane nam dvoje: igro lahko opustimo ah pa jo izboljšamo. Poskusimo s slednjim. Spremenimo igralno desko s slike 2. Pomaknimo točki 4 in 6 na pol poti proti točki 5. Točke lahko sedaj povežemo, kot kaže slika 3. Dobili smo novo igralno desko, ki pa jo od prve loči pomembna razlika. Napadalec sedaj nima očitne najboljše prve poteze, saj vsaka točka leži na natanko treh ČTtah. S tega stališča so vse točke enakovredne.
Denimo, da napadalec spet prične s točko 5. Kako naj odgovori branilec? Napadalec je s svojo potezo ogrozil tri črte, ki gredo skozi točko 5. Branilec sklepa, da je najpametneje zavarovati vsaj eno od teh črt,
Slika 3. Papusova razporeditev.
recimo tisto, ki gre skozi točke 1,5,9, in odgovori s točko 1. Hitro vidimo, da se igra zanj ne bo dobro končala. Napadalec bo namreč zasedel točko 3 in po izsiljeni potezi branilca še točko 4. Branilca je post avil pred nerešljiv problem, zaščititi se pred dvema grožnjama hkrati. Kako naj torej igra branilec po začetni potezi napadalca? Je igra zanj izgubljena? Prepričan sem, da boste odgovor našli sami.
Medtem pa poskusimo poiskati še kakšno zanimivo igralno desko, ki jo odlikujejo podobne lastnosti kot desko s slike 3. Postavljeni smo pred naslednjo nalogo:
V ravnini razpostavi n točk in skoznje potegni n ravnih črt tako, da ho vsaka črta vsebovala tri točke in bo vsaka točka ležala na treh črtah.
Naloga je vse prej kot lahka. Tiste, ki bi radi na takšen način razpostavili manj kot devet točk, naj od brezupnih poskusov že na začetku odvrnem in vam zaupam, da naloga pri n < 9 ni rešljiva. Morda najbližje rešitvi pridemo, če narišemo sliko 4. Tu smo sedem točk povezali s šestimi ravnimi črtami in eno krivo. Podobno se nam godi tudi pri osmih točkah. Za n = 9 eno rešitev že poznamo, na sliki 5 pa je še ena. Trikotnik s slike 5 nam da idejo še za nove razporeditve na sliki 6. Bralec je gotovo opazil vzorec, po katerem lahko sam poišče razporeditve za poljubno mnogo točk. Več kot je točk, zanimivejša je igra in težje je vprašanje, ali lahko napadalec ob pravilni igri vedno zmaga.
Posvetimo se še vprašanju, ah so na igralni deski, kjer vsaka točka leži na treh Črtah, res vse začetne poteze enakovredne. Ali se vseeno ne more zgoditi, da ena začetna poteza branilcu dopušča zadovoljivo obrambo, druga pa ne? Ali mu jo vsaj nekoliko oteži? Odgovoriti na ta vprašanja ni lahko. V posebnem primeru pa lahko vseeno zatrdimo, da so res vse začetne poteze enakovredne. Oglejmo si ta primer podrobneje.
Imejmo razporeditev n točk in te točke poimenujmo kar z naravnimi števili 1, 2,..., n. Permutaciji n teh točk, ki ima lastnost, da točke ■7r('i), 7v(j) in ?r(fc) ležijo na skupni črti natanko tedaj, ko na skupni Črti ležijo točke i, j in k, rečemo avtomorSzetn razporeditve. Permutacija neke množice je bijektivna preslikava te množice same nase. To pomeni, da
lahko permutacijo tt predstavimo kot niz prvih n naravnih števil, kjer vsako število med 1 in n nastopi natanko enkrat. Točka tt (i) bo v tem nizu nastopala na i-tern mestu.
Slika ti. Še nekaj razporeditev.
Za zgled avtomorfizma si oglejmo še enkrat sliko 3. Permutacijo, ki zamenja tri točke zgornje vrstice s tremi točkami spodnje vrstice, točke na sredini pa pusti, kjer so, bi označili z nizom (7,8,9,4.5,6,1,2,3). Prav hitro se prepričamo, da ta permutacija zadošča zahtevi avtomorfizma -črte res preslika v črte. Denimo točke 1, 5,9 so se preslikale v točke 7, 5, 3. Podobno se je črta, ki povezuje točke 1, 2, 3, preslikala v črto, ki povezuje točke 7,8,9.
Vrnimo se k našemu vprašanju, ali so vse začetne poteze enakovredne. Denimo, da za dve točki i in j obstaja avtomorfizem razporeditve, ki točko i preslika v točko j. Označimo ta avtomorfizem s n. Trdimo, da sta tedaj začetni potezi i in j enakovredni v smislu, da napadalec lahko s pravilno igro zmaga po potezi i natanko tedaj, ko lahko zmaga po potezi j, V to se z lahkoto prepričamo, če opazimo, da vsakemu zaporedju potez i, *2, ¿3,... v primeru začetne poteze i ustreza v primeru začetne poteze j
zaporedje potez j, ^(¿2), ^"(¿3),____ Pri tem bo zaradi zahtevane lastnosti
avtomorfizma (da točke na skupni črti preslika na točke, ki spet ležijo na
skupni črti) prvo zaporedje zmagovalno za napadalca natanko tedaj, ko bo zmagovalno tudi drugo zaporedje. Denimo, da ima naša razporeditev to lastnost, da za vsaki dve točki i in j obstaja neki avtomorfizem, ki eno preslika v drugo. Tedaj res lahko trdimo, da so vse začetne poteze enakovredne. Bralec naj sam premisli, ali imajo vse razmestitve, ki smo jih navedli do sedaj, to lastnost.
Za tiste, ki jih igranje križcev in krožcev dolgočasi, razmišljanje o avtomorfizmih pa jim ne gre od rok, naslednje vprašanje: Ali lahko vse razmestitve s slik 5 in 6 konstruiramo z ravnilom in šestilom? Za začetek se lahko spopadete s primerom s slike 5. Opozorim naj, da so trije trikotniki na sliki enakostranični, oglišča po velikosti srednjega od njih pa ležijo natanko na razpoloviščih stranic večjega. Kako v tem primeru s šestilom in ravnilom konstruirati oglišča notranjega trikotnika, da bodo nosilke njegovih stranic res vsebovale oglišča zunanjega trikotnika?
Primož Potočnik