1

3

2

4

1

3

2

4

1

3

2

4

1

2

4

1

2

1

80 Â

WIAT

N

AUKI

Maj 2000

T

radycja objaÊniania matematyki za
pomocà gier i zagadek si´ga czasów
staro˝ytnych Babiloƒczyków, któ-

rzy zapisywali arytmetyczne ∏amig∏ówki
na glinianych tabliczkach. Ostatnio jednak
szybki rozwój matematyki spowodowa∏
powstanie mnóstwa ca∏kiem nowych gier.
Jednà z nich wymyÊli∏ David Gale z Uni-
versity of California w Berkeley, a opisa-
na zosta∏a w ksià˝ce Games of No Chance
(Gry nielosowe) pod redakcjà R. J. Nowa-
kowskiego (Cambridge University Press,
1996). Gra zawiera zarówno elementy teo-
rii zbiorów, jak i topologii. Powinna szcze-
gólnie zainteresowaç osoby zajmujàce si´
matematykà rekreacyjnà, nikt bowiem jesz-
cze nie okreÊli∏ dla tej gry strategii prowa-
dzàcej do wygrywania.

Zacznijmy od krótkiego przypomnienia

teorii zbiorów. Zbiory sà zespo∏ami obiek-
tów, które nazywamy elementami danego
zbioru. JeÊli zbiór ma skoƒczonà liczb´ ele-
mentów, mo˝emy je wypisaç pomi´dzy
dwoma nawiasami. Na przyk∏ad {2, 3, 5, 7}
to zbiór wszystkich liczb pierwszych mniej-
szych od 10. Zbiór X jest podzbiorem zbio-
ru Y, jeÊli ka˝dy element zbioru X jest tak-
˝e elementem zbioru Y. Zbiór {3, 5, 7}
wszystkich nieparzystych liczb pierwszych
mniejszych od 10 jest podzbiorem zbioru
{2, 3, 5, 7}. Ka˝dy zbiór uwa˝a si´ za jego
w∏asny podzbiór; podzbiór zbioru X jest
podzbiorem „w∏aÊciwym”, gdy ró˝ni si´ od
X. Zbiór mo˝e mieç tylko jeden element –
na przyk∏ad {2} jest zbiorem wszystkich pa-
rzystych liczb pierwszych. Zbiór mo˝e nie
zawieraç w ogóle elementów – mówimy
wtedy, ˝e jest pusty.

Gra Gale’a nazywa si´ zabieranie pod-

zbiorów. Zaczyna si´ od skoƒczonego zbio-
ru S, za który przyjmiemy zbiór {1, 2,..., n}
wszystkich liczb ca∏kowitych od 1 do n.
Dwaj gracze kolejno wybierajà niepuste,
w∏aÊciwe podzbiory S z jednym ogranicze-
niem: ˝aden uprzednio wybrany (przez
któregokolwiek z graczy) zbiór nie mo˝e

byç podzbiorem aktualnie wybieranego
zbioru. Przegrywa ten, kto nie mo˝e ju˝
wybraç ˝adnego zbioru. Jednym z mo˝li-
wych sposobów rozegrania partii w prak-
tyce jest narysowanie na kartce kolumn
ponumerowanych liczbami od 1 do n i sta-
wianie w jednej linii krzy˝yków w tych ko-
lumnach, które zawierajà wybierane ele-
menty. ˚aden kolejny ruch nie mo˝e
obejmowaç wszystkich krzy˝yków z jakie-
gokolwiek ruchu poprzedniego.

Niech zgodnie z tradycjà graczami b´-

dà Alicja i Bolek, przy czym Alicja rozpo-
czyna gr´. Gdy n = 1, ruchy odpowiadajà-
ce ustalonym regu∏om nie sà mo˝liwe. Gdy
n = 2, S = {1, 2}. Jedynymi ruchami zgodny-
mi z zasadami gry sà wtedy {1} oraz {2} –
jeÊli Alicja wybierze którykolwiek z nich,
Bolek mo˝e wybraç drugi. Wtedy Alicja
nie mo˝e ju˝ wykonaç ruchu, wi´c wygry-
wa Bolek.

Gra staje si´ bardziej interesujàca, gdy

n = 3, a S = {1, 2, 3}. PrzypuÊçmy, ˝e Alicja
wybierze zbiór dwuelementowy {1, 2}.
Wówczas Bolek mo˝e wybraç zbiór jedno-
elementowy {3}, zawierajàcy element, któ-
rego nie wybra∏a Alicja. Teraz Alicja nie
mo˝e wybraç niczego, co zawiera 3, musi
wi´c wybraç podzbiór zbioru {1, 2} i od te-
go momentu gra jest dok∏adnie taka, jakby
zaczyna∏a si´ od zbioru {1, 2}. A zatem Bo-
lek znów wygrywa. Dzieje si´ tak samo,
gdy Alicja wybierze jakikolwiek inny pod-
zbiór dwuelementowy. Jednak Alicja ma
innà mo˝liwoÊç: w pierwszym ruchu wy-
braç zbiór jednoelementowy, na przyk∏ad
{3}. Wtedy – jeÊli Bolek wybierze podzbiór
dope∏niajàcy {1, 2}, to gra potoczy si´ tak,
jakby zaczyna∏a si´ od zbioru {1, 2} i Bolek
wygra ponownie. A poniewa˝ pierwszy
ruch Alicji musi polegaç na wybraniu al-
bo zbioru jednoelementowego, albo dwu-
elementowego, strategia gwarantujàca wy-
granà jest w przypadku Bolka prosta:
zawsze powinien wybieraç dope∏nienie
zbioru, który wybra∏a Alicja. Zanim za-
czniesz czytaç dalej, mo˝esz rozwa˝yç, czy
ta sama strategia zapewnia Bolkowi zwy-
ci´stwo, gdy n jest wi´ksze od 3.

REKREACJE MATEMATYCZNE

Ian Stewart

Strategia dla podzbiorów

GR¢ W ZABIERANIE PODZBIORÓW mo˝na przedstawiç topologicznie.

Pozycjà poczàtkowà jest czworoÊcian (a). Dwaj gracze, Alicja i Bolek,

wybierajà na przemian podzbiory, a fragmenty czworoÊcianu

usuwa si´ tak d∏ugo, a˝ nic nie zostanie (b–g).

a

POZYCJA POCZÑTKOWA

b

ALICJA WYBIERA {1, 2}

c

BOLEK WYBIERA {2, 3, 4}

f

ALICJA WYBIERA {2}

g

BOLEK WYBIERA {1}

I WYGRYWA!

e

BOLEK WYBIERA {4}

d

ALICJA WYBIERA {3}

BRYAN CHRISTIE

Â

WIAT

N

AUKI

Maj 2000 81

Teraz przejdêmy do topologii, którà

czasami okreÊla si´ jako geometri´ gu-
mowej powierzchni. W celu stworzenia
geometrycznej reprezentacji zabierania
podzbiorów zastosujemy jednà z pod-
stawowych technik topologii – triangu-
lacj´ figury, czyli podzielenie jej na trój-
kàty o wspólnych kraw´dziach. Mówiàc
ÊciÊle, opis ten stosuje si´ tylko do po-
wierzchni, ale to samo podejÊcie mo˝-
na wykorzystaç tak˝e w przypadku
tworów wielowymiarowych, je˝eli za-
stàpimy trójkàty ich n-wymiarowymi
odpowiednikami, tzw. sympleksami.
Na przyk∏ad trójwymiarowy sympleks,
w skrócie: 3-sympleks, jest czworoÊcia-
nem o wierzcho∏kach oznaczonych 1, 2,
3, 4 [rysunek na sàsiedniej stronie]. Ma
on cztery Êciany, szeÊç kraw´dzi i czte-
ry wierzcho∏ki. Âciany sà trójkàtami
(czyli w tej terminologii 2-sympleksa-
mi), kraw´dzie odcinkami (1-symplek-
sami), a wierzcho∏ki punktami (0-sym-
pleksami). Dodatkowo wszystkie te
cz´Êci odpowiadajà dok∏adnie podzbio-
rom zbioru {1, 2, 3, 4}. Sam czworoÊcian

odpowiada ca∏emu zbiorowi {1, 2, 3, 4}.
Âciany odpowiadajà trzyelementowym
podzbiorom {1, 2, 3}, {1, 2, 4}, {1, 3, 4}
i {2, 3, 4}, kraw´dzie podzbiorom dwu-
elementowym {1, 2}, {1, 3}, {1, 4}, {2, 3},
{2, 4} i {3, 4}, a wierzcho∏ki podzbiorom
jednoelementowym {1}, {2}, {3} i {4}.

W istocie, ka˝dy (n – 1)-sympleks

mo˝na uto˝samiç ze zbiorem {1, 2, ..., n},
a jego ró˝ne mniej wymiarowe cz´Êci
z podzbiorami w∏aÊciwymi tego zbio-
ru. Zabieranie podzbiorów mo˝na te-
raz przeformu∏owaç na wymazywanie
podsympleksów. Na poczàtku gracze
majà do dyspozycji sympleks. Ruch
polega na wybraniu w∏aÊciwego pod-
sympleksu i wymazaniu jego wn´trza
oraz wn´trz wszystkich wi´cej wymia-
rowych sympleksów, które go zawiera-
jà. Ruch nie wymazuje jednak brzegu
wybranego sympleksu – na przyk∏ad
pozostawiamy trzy kraw´dzie trójkàt-
nej Êciany lub dwa koƒce wybranego
odcinka.

Mo˝na wykorzystaç t´ reprezen-

tacj´ do analizy wymazywania sym-
pleksów dla 3-sympleksu, który odpo-
wiada zabieraniu podbiorów dla n = 4.
Pozycjà startowà jest 3-sympleks, czy-
li czworoÊcian. Rysunek na sàsied-
niej stronie przedstawia seri´ dopusz-
czalnych ruchów. Systematyczne roz-
wa˝enie wszystkich takich ciàgów wy-
ka˝e, ˝e Bolek zawsze mo˝e zwyci´˝yç
w grze dla n = 4. Podobnie dla n = 5 oraz
n = 6. Gale wysnu∏ przypuszczenie, ˝e
niezale˝nie od wartoÊci n, Bolek dyspo-
nuje strategià gwarantujàcà wygranà.
Z tego, co wiem, przypuszczenie to nie
zosta∏o dotychczas ani udowodnione,
ani obalone.

Jaka jest zatem strategia Bolka dla

n = 4, 5, 6 i wi´kszych? Czy zawsze po-
winien on wybieraç dope∏nienie zbioru
wybranego przez Alicj´ – strategi´, któ-
ra daje mu wygranà w przypadku n = 3?
Gdy n = 4, Alicja mo˝e rozpoczàç par-
ti´, wybierajàc wierzcho∏ek, kraw´dê
lub trójkàtnà Êcian´. Je˝eli wybierze
wierzcho∏ek, a Bolek dope∏nienie, gra
sprowadzi si´ do przypadku n = 3 i
Bolek zwyci´˝y. Je˝eli Alicja wybie-
rze trójkàtnà Êcian´, a Bolek wierzcho-
∏ek dope∏niajàcy, gra znów sprowadzi
si´ do wersji prostszej. Co si´ jednak
stanie, gdy Alicja wybierze kraw´dê,
powiedzmy, kraw´dê odpowiadajàcà
{1, 2}, a Bolek kraw´dê dope∏niajàcà, któ-
rà b´dzie {3, 4}?

Rezultat pokazano na rysunku na gó-

rze po lewej. Je˝eli Alicja zdecyduje si´
na {3}, Bob nie b´dzie móg∏ wybraç do-
pe∏niajàcego zbioru {1, 2, 4}, bo nie po-
zwalajà na to regu∏y gry (w terminach
sympleksu: ta trójkàtna Êciana zosta∏a
ju˝ wytarta). A zatem strategia wybiera-

nia dope∏nieƒ zawodzi. Kilku matema-
tyków wysun´∏o przypuszczenie, ˝e dla
wszystkich n w∏aÊciwa odpowiedê Bol-
ka na pierwszy wybór Alicji polega na
wybraniu zbioru dope∏niajàcego zbiór
przez nià wybrany. Potem jednak Bo-
lek mo˝e zostaç zmuszony do odstàpie-
nia od tej metody wyboru, jak to zaob-
serwowaliÊmy przed chwilà.

A co z biednà Alicjà? Czy to prawda,

˝e Bolek zawsze jà pokona w ka˝dej
wersji zabierania podzbiorów? Poszu-
kiwania komputerowe mogà zarówno
potwierdziç, jak i obaliç t´ hipotez´ dla
n = 7, 8 lub innych niewielkich liczb. Do-
wód dla du˝ych n b´dzie wymaga∏ no-
wego podejÊcia. Wszystkie interesujàce
sugestie czytelników zamieszcz´ w

SPRZ¢˚ENIU ZWROTNYM

.

T∏umaczy∏

Tomasz ˚ak

R

on Menendez z Chatham w stanie
New Jersey zauwa˝y∏ jeszcze jed-

nà interesujàcà w∏asnoÊç trójkàta Sier-
piƒskiego [poni˝ej], który omawia∏em
w artykule „Wszechobecny trójkàt Sier-
piƒskiego” [paêdziernik 1999]. Weêmy
trójkàt równoboczny o wierzcho∏kach
A, B i C, a nast´pnie wybierzmy do-
wolny punkt X z jego wn´trza. Wylo-
sujmy teraz jeden z wierzcho∏ków trój-
kàta – na przyk∏ad rzuçmy kostkà
i niech 1 lub 2 odpowiada wierzcho∏-
kowi A, 3 lub 4 – B, a 5 lub 6 – C.
Znajdêmy Êrodek odcinka ∏àczàcego
punkt X z wylosowanym wierzcho∏kiem:
jest to nowy punkt X. Teraz powtarzaj-
my to post´powanie, wybierajàc za-
wsze losowo wierzcho∏ek i przesuwa-
jàc X do Êrodka odcinka ∏àczàcego
punkt, w którym znajdowa∏ si´ po-
przednio, z wybranym wierzcho∏kiem.
Poza nielicznymi punktami poczàtko-
wymi, dla których ten spacer losowy
„uspokaja si´”, powstajàca chmura
punktów jest trójkàtem Sierpiƒskiego!

Ten zaskakujàcy rezultat wyjaÊnia

teoria samopodobnych fraktali, stwo-
rzona przez matematyka Michaela
Barnsleya. Trójkàt Sierpiƒskiego ma
trzy rogi, które równie˝ mo˝na ozna-
czyç literami A, B i C. Jest on z∏o˝ony
z trzech w∏asnych mniejszych kopii,
a ka˝da ma boki dwa razy krótsze ni˝
bok trójkàta. JeÊli narysuje si´ odci-
nek pomi´dzy dowolnym punktem trój-
kàta oraz A, B lub C, Êrodek tego
odcinka b´dzie tak˝e punktem trój-
kàta. Ta cecha odpowiada regu-
∏om spaceru losowego Menen-
deza. Barnsley udowodni∏, ˝e
ka˝dy taki spacer „zbiega”
do trójkàta Sierpiƒskiego.

SPRZ¢˚ENIE ZWROTNE

1

3

2

4

1

2

4

1

3

2

4

a

ALICJA WYBIERA {1, 2}

b

BOLEK WYBIERA {3, 4}

c

ALICJA WYBIERA {3}

BRYAN CHRISTIE

STRATEGIA DOPE¸NIE¡ zawodzi
w tej wersji zabierania podzbiorów,

poniewa˝ Bolek nie mo˝e wybraç

podzbioru dope∏niajàcego zbiór

wybrany w drugim ruchu Alicji (c).