Az egész egy ártatlannak tűnő fejtörővel kezdődött, amit András hozott a brigádnak. A feladat így szól:
Egy börtönben megszámlálhatóan
végtelen rab raboskodik. Az unatkozó börtönőrök azt találják
ki, hogy mindegyik rab fejére piros vagy kék sapkát húznak, úgy,
hogy senki se lássa, a saját fejére milyen színű kerül, majd
miután a rabok jól megnézték egymást (minden rab a sajátján
kívül az összes többi rab sapkáját látja), mindegyiküktől
megkérdezik, milyen színű sapka van a fején. Ha legfeljebb véges
számosságú rossz válasz születik, a rabokat mind
elengedik. Milyen stratégiát találjanak ki a rabok, hogy
biztosan kijussanak?
Sajnos szerdán közölte a feladatot, és én először csütörtökön
voltam dolgozni, úgyhogy addigra Encsének már volt egy
(tudottan rossz) megoldás-vázlata. A következőek miatt fontos
megismernünk ezt a megoldást, és azt is, hogy miért rossz.
Tegyük fel, hogy a rabok előre sorba rendeződnek, és
megállapodnak egy algoritmusban, ami megszámlálhatóan végtelen
hosszú piros/kék sorozatokat állít elő. Amikor minden rab fején
sapka van már, mindegyik rab elkezdi futtatni az algoritmust, és
megnézik, vajon az első, második, ... sorozatra igaz-e, hogy
legfeljebb véges esetben adna hibás választ, ha az
n. rab válasza az aktuális sorozat
n. tagja lenne. A saját sapkájukat nem ismerve is
mindannyian ugyanara a sorozatra fogják először megállapítani,
hogy megfelelő. Ezekután valamennyi rab e szerint a sorozat
szerint fogja a ráeső sapka-színt válaszolni.
Ha az őrök ki tudják kérdezni a rabokat, és meg is tudják
állapítani, hogy legfeljebb véges rossz válasz született, akkor
ezeket a műveleteket megengedettnek vehetjük (használhatjuk a
börtönőrök algoritmusait), vagyis a végtelen sorozatok
előállítását és egyes sorozatok ellenőrzését elvégezhetik a
rabok.
A megoldás mégsem helyes, mivel könnyen látható (közvetlenül Cantor
módszerével, vagy pl. a sapka-sorozatokat
kettedesjegy-bitsorozatként értelmezve, a [0,1]-beli valós
számokkal azonosítva), hogy a lehetséges sapkasorozatok kontinuum
számosságúak, ezért nem sorolhatóak fel, vagyis egy mégoly
erős algoritmus, amelyet a feladat, mint láttuk, implicit
megenged, és könnyedén előállít végtelen bitsorozatokat, sem
tudná valamennyi lehetséges sorozatot előállítani.
De vajon szükség van-e valamennyi sorozat előállítására? Nyilván
nem, hiszen sok olyan sorozat van, amelyek közül egy adott
sapka-leosztás esetén bármelyikre is jutnak a rabok az
algoritmust futtava, a rossz válaszok száma legfeljebb
véges. Definiáljunk ugyanis egy olyan binér relációt a
megszámlálhatóan végtelen hosszú bitsorozatok felett, amelyben
két sorozat relációban van, ha van olyan index, amelytől
megegyeznek, vagyis legfeljebb véges tagjuk tér el. Ez a reláció
nyilván ekvivalencia-reláció, és a raboknak elegendő egy olyan
algoritmus, amely minden ekvivalencia-osztályból előbb-utóbb
előállít legalább egy sorozatot.
Mármost vizsgáljuk meg az ekvivalencia-osztályok számát! Sajnos
azt kapjuk, hogy ezek továbbra sem megszámlálhatóak, hiszen
egy-egy osztálya úgy áll elő, hogy vesszük egy reprezentánsát,
majd hozzávesszük azokat az egyéb sorozatokat, amelyek tőle egy
tagban térnek el (ilyenből nyilván megszámlálhatóan végtelen
van), amelyek két tagban (szintén), és így
tovább. Megszámlálhatóan végtelen darab megszámlálhatóan
végtelen halmaz uniója azonban még mindig csak
megszámlálhatóan végtelen. Mivel az osztályok uniója, vagyis az
összes sorozat megszámlálhatatlan, nyilván az osztályok száma is
az.
A fenti gondolatmenet alapján tehát bárki meggyőzhető, hogy az
ismeretett megoldás hibás. Csakhogy András egy ehhez nagyon
hasonló megoldást ismertetett kanonizáltként (mint kiderült, a
feladatot, és a megoldását ő matek-szakos hallgatóktól
hallotta): a rabok megállapodnak ekvivalenciaosztályonként
egy-egy reprezentánsban, és amikor az őrök kikérdezik őket,
mindannyian a látott sapkák által meghatározott osztály
reprezentánsának tagjaival válaszolnak.
Persze amikor ezt András előadta, kitört a pokol, mert átverve
éreztük magunkat. Ugyan hogyan tudnának megállapodni a rabok az
ehhez szükséges ℝ→ℝ függvényben, ha
általában még a valós számok egy részhalmazára sem adható
kiszámítható szelektorfüggvény? Mint kiderült, a forrásnak
számító matekhallgatókat ez a részlet egyáltalán nem zavarta.
Aztán rákerestünk a neten, és kiderült, amit már akkor éreztem a
zsigereimben, amikor a "megoldást" hallottuk: a
megoldás valójában a kiválasztási axiómán függ, nem is
lehetne konstruktív. Persze a linkelt oldallal ellentétben én
nem gondolom, hogy ebből a kiválasztási axióma valamiféle
értékelését vonhatjuk le, viszont szerintem az eredeti
feladatban szereplő rabokon fikarcnyit sem segít bármilyen,
nem-konstruktív módszer.
És innentől válik a kérdés filozófiaivá, és itt dobom be a
gyeplőt a leendő kommentelők közé: szerintetek mi a helyzet?