i
i
“1094-Dobovisek-Brstenje” — 2010/7/13 — 10:07 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 19 (1991/1992)
Številka 4
Strani 214–218
Mirko Dobovišek:
BRSTENJE
Ključne besede: razvedrilo, naloge.
Elektronska verzija: http://www.presek.si/19/1094-Dobovisek.pdf
c© 1992 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
BRSTENJE
V sestavku bomo povedal i nekaj o zanimivi igri imenovani " Sprouts ", po
slovensko " Brstenje ". Prem išljevali bomo tud i o tem, kako bi igro spreme nili
in t ako" izumili" novo igro .
Igro sta po pripovedova nju odkrila John Horto n Conway, profesor ma-
tematike na Sidney Sussex College, Cambridge in takratn i študent Michael
St eward Paterson let a 1967. Igro igramo na papirju z n pikami tako , da
vl eče rno poteze. Potezo potegnemo tako , da narišemo krivuljo od ene pike
do druge ali pa nazaj do ist e pike in nato nekje na tej krivulji naredimo novo
piko. Pri t em moramo upošteva t i nas lednji pravili:
i) Povezava ima lahko kakršnokoli ob liko, ne sme pa sekati same sebe , prej
potegnjenih povezav in ne sme iti skozi nobeno prej narisanih pik.
ii) V nobeni piki se ne smejo za četi in končat i več kot tri povezave. Rekli
bom o, da ima vsaka pika tri življenja .
Igralca igrata t ako , da izmenoma vlečeta poteze. Zmagovalec je tisti ,
ki lahko zad nji povleče pot ezo . Na naslednji sliki je prikaza na tip i čna igra s
t remi za četnimi pikam i.
Slika 1
Igra se vedno konča , kar lahko dokažemo takole: Na začetku imamo n
pik. Dogovorili smo se že, da bomo možne začetke potez imenovali življenja .
Na začetku je to rej 3n življenj . Pri vsaki potezi uni čimo dve življenji in
dodamo eno novo (novi piki na povezavi ostane eno življenje) . Na vsakem
koraku se torej število življenj zmanjša za 1. Po 3n - 1 potezah imamo samo
še eno življenje in nove poteze ne moremo več potegniti . Ni težko pokazati,
da potrebujemo vsaj 2n potez, da bi igro končali . Bralec, ki se bo pregrizel
215
do konca sestavka, bo to gotovo znal sam dokazati.
Igre ne bomo podrobno analizirali . Napišimo le nekaj besed :
Pri igri z eno začetno piko ni težav. Prvi igralec ima na razpolago le eno
potezo. Piko poveže samo s seboj. Drugi igralec seveda zmaga. Poveže novo
piko z začetno. To lahko naredi na dva naeina : znotraj zanke ali zunaj nje.
Če malo premislimo , vidimo, da sta ti dve potezi na neki način enakovredni.
Pri igri z dvema pikama lahko drugi igralec igra tako, da zmaga. Potez je
tu še tako malo, da lahko vse možne igre narišemo in to preverimo. Dokazali
so že tudi, da igre s tremi, štirimi in petimi začetnimi pikami lahko dobi prvi
igralec, če seveda pravilno igra . Dokaz , da v igri s šestimi začetnimi pikami
lahko vedno zmaga drugi igralec, je dolg kar 49 strani. Za razumevanje dokaza
je potrebno že zelo veliko znanja . Sploh so se matematiki dosti ukvarjali s to
igro, saj je zanimiva tudi zato , ker povezuje topologijo in kombinatoriko.
Kako pa bi igro lahko spremenili? Lahko jo recimo igramo na sferi .
Igra ostane enaka, saj sfero, ki smo ji odvzeli katerokoli točko , lahko tako
preslikamo na ravnino, da vsaki točki na sferi brez ene točke pripada točka
na ravnini in obratno. Pri tem pa se nobena krivulja ne pretrga ali dodatno
zavozla.
Igra na torusu (recimo avtomo-
bilski zračnici) je že malo drugačna .
Lahko pa igramo tudi na vazi z več
ročaji. Možnosti je veliko. Vsaka pa
zahteva svojo" analizo" igre. Slika 2
Kaj pa, če ima pika namesto treh življenj štiri življenja? Na zgornjem
primeru vidimo, da potem igro lahko igramo tako, da se nikoli ne konča .
Kaj pa, če začnemo s križci namesto s pikami? Tako ima vsaka pika štiri
življenja, vendar nam križci določajo smer, v katero smemo začeti vleči nasled-
nje poteze . Nekatera življenja postanejo" ograjena" s prejšnjimi potezami.
Ali se igra konča ali ne? Enak razmislek kot prej ne bo dober, kajti z vsako
potezo uničirno dve življenji in dodamo novi dve. 5tevilo življenj je torej vse-
skozi enako . Dokaz, da se igra konča, je daljši : 5tevilo križcev označimo s
T , del krivulje med dvema križcema imenujmo povezava, število povezav pa
označimo s P. Območje naj bo del ravnine, ki je ograjen s povezavami in ne
vsebuje nobenega križca . 5tevilo območij označimo z O.
Na začetku imamo torej n križcev, nobene povezave in, če je n >
216
> 1, nobenega območja. Pri n = 1 si lahko mislimo, da je ravnina brez
križca območje (neomejeno). Z vsako potezo dobimo novo točko (tisto na
potegnjeni krivulji) in dve novi povezavi .
Da bomo te pojme lažje razumeli , si oglejmo igro z enim začetnim
križcem . Igra se konča v 3 korakih . Narišimo nekaj možnosti :
+
+
+
+
o
o
Slika 3
(...... )
Drugih različnih naeinov igranja ni, ce upoštevamo vse simetrije . Kaj
se je t o rej dogajalo v teh primerih? V začetku imamo eno območje (tisto
neomejeno) in en križec . V vseh primerih imamo po prvi potezi dva križca ,
dve povezavi in dve območjiIeno omejeno in eno neomejeno). Po drugem
koraku imamo tr i križce, tri območja in štiri povezave . Po četrtem koraku pa
so štirje križci, šest povezav in štiri območja. Eno območje je seveda vedno
neomejeno.
Vsako območje ima nekaj" rok" , na katerih lahko začnemo ali končamo
potezo. Le je teh prostih rok r , bomo rekli , da ima območje r življenj.
Oglejmo si še enkrat primer (*) . V začetku je eno območje ( neomejeno)
s 4 življenji. Po prvi potezi imamo dve območji . Eno ima eno življenje, drugo
pa tri . Po drugi potezi imamo tri območja: dve z enim življenjem in eno z
dvema . Ko se igra konča, ima vsako območje le eno življenje . V nekaterih
drugih primerih igranja igre z enim začetnim križcem , je število življenj v
območjih drugačno kot prej (recimo v **).
Le začnemo z več križci , se število območij ne spreminja tako" pravilno" ,
217
vsaj na začetku ne. Lahko se zgodi , da še po nekaj potezah ni nobenega
območja.
Oglejmo si, kako lahko začnemo igro s štirimi začetnimi križci:
+ + +
+
+
Slika 4
Igra se konča, ko ima vsako območje le po eno življenje. Pa se igra sploh
konca? Ali mogoce lahko igramo tako , da ne bo konca?
To, da se igra vedno konča , bomo dokazali z matemati čno indukcijo.
Videli smo že, da se igra z enim zaeetnim križcem konca. Predpostavimo
torej, da se kon čajo vse igre z manj kot n križci. S pomoejo te predpostavke
bomo dokazali, da se konca tudi igra z n začetnimi križci,
Dokažimo najprej , da bo prej ali slej vseh n začetnih križcev med seboj
povezanih . Sploh bodo potem povezani vsi križci, saj nove vedno narišemo
na povezavah .
Recimo, da temu ni tako. Potem lahko igramo tako, da do enega križca
nikoli ne potegnemo poteze oziroma povezave . To pa je tako, kot da bi
igrali igro z enim zaeetnim križcem manj . Taka igra se po predpostavki
konca . Ko se ta igra , z enim križcem manj , konca , lahko potegnemo še
potezo od osamljenega križca do življenja v območju, kjer ta križec je . Od
te poteze naprej , pa so vsi križci povezani. Tako smo prišli do protislovja s
predpostavko, da lahko tako igramo, da ne bodo nikoli vsi križci povezani.
Ravnina je razpadla na sama območja, Teh območij je seveda končno. Le
nam uspe dokazati, da lahko v vsakem obmoeju potegnemo le še koneno
potez , bomo dokazali, da se igra konča v koneno mnogo korakih.
Koliko potez lahko potegnemo v obmoeju s s življenji? Razmislimo
takole: V obmoeju z enim življenjem ne moremo potegniti nobene poteze .
V obmoeju z dvema življenjema, lahko naredimo eno potezo. Dobimo dve
območji, vsako z enim življenjem. Zato je konec igre v tem obmoeju . Le ima
območje tri življenja , povežemo dve med seboj. Dobimo dve območji, eno z
enim življenjem in eno z dvema . V drugem območju je, kot že vemo, možna
ena poteza. Skupaj smo potegnili torej dve potezi .
Z indukcijo pokažimo, da lahko v obmoeju s s življenji potegnemo
natanko s - 1 potez. Za s = 1 smo to že videli. S prvo potezo iz ob-