Contents

Blog tags RSS

Sapkakiválasztási axióma

27 October 2007 (programming ISC math) (15 comments)

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?


« Nintendo a seggem 
All entries
 Jönnek a letölthető Wii demók? »


cooldavee 2007-10-28 02:32:12

Legalább kiderült, hogy a magyar Wikipedia-n rossz volt a véges halmaz definíciója, úgyhogy ezt gyorsan ki is javítottam. ;-)

Encsé (http://zsonglor.csokavar.hu) 2007-10-28 18:02:09

Cooldavee: mi itt a Nemzetközi Sötétbentartási Intézeteben éjt nappallá téve dolgozunk, hogy megfúrjuk az axiómákat, te meg kijavítod baszki. De nem baj: a valszám még mindig úgy ahogy van ellentmondásos (nem is csoda, hogy bármit ki lehet hozni belőle), és ezzel a teljesen értelmetlen kiválasztási axiómával is emberek százait vezetjük meg.

ZoliBravo 2007-10-29 16:39:03

1. megoldás: rakjunk a fehérekre fehér sapkát, a négerekre meg feketét

2. megoldás: különben meg ha brazil a börtön, felgyújták az egészet a faszba és lelővik a vicces(nek hitt) börtönőröket

cactus 2007-10-29 20:10:15

That was lovely. Megártott a sok pivo?

Egyébként erről a "matematikus a kannibálok szigetén" jellegű feladványok jutottak eszembe: egy matematikus elkerül egy szigetre, ahol háromféle kannibál él: az egyik mindig hazudik, a másik mindig igazat mond, a harmadik pedig rögtön megeszi azt, aki mindenféle furmányos kérdéseket akar feltenni...

Maya (http://mayablog.blog.hu/) 2007-10-29 23:37:44

Nem akarom itt drága helyet pazarolni, fizikai megközelítésű megoldásomat lásd nálam

Maya (http://mayablog.blog.hu/) 2007-10-29 23:43:17

Na jó, azért megeresztek ide egy stratégiai, ha úgy tetszik rendőrszakmai gondolatmenetet is.

Szerintetek végtelen sok rab adott idő alatt mennyi veszteség mellett hányszor és milyen színűre agyabugyál el akármilyen véges sok őrt?

fake plastic 2008-04-08 21:26:08

végtelen sok tömeg nélküli rab

Danaudioslave 2008-04-25 00:00:59

Na ti beteg állatok! Ez egy primitív feladat, de ti túl kockák vagytok hozzá!

Meg lehet oldani a feladatot úgy, hogy maximum 1 (!!) ember mond rosszat. Felállítanak a rabok egymás között egy sorrendet. Az első kettő ember beáll egymás mellé. Egy harmadik, hogyha a 2 ember sapkája azonos, beáll közéjük, ha különböző, akkor mögéjük. A 4. ember is eszerint jár el, és így tesznek az utolsó emberig, így felépítenek egy sort, ahol az egymást követő embereken ellentétes színű sapka van. Előfordulhat olyan eset, hogy már csak 1 színű sapkások maradtak, azok mindig ugyan azon ember mögé fognak beállni, és ha az összes maradék ember beállt már ugyan azon ember mögé, azok tudni fogják, hogy egyforma színű a sapkájuk. Így mikor az első ember tippel, vagy eltalálja, vagy nem, és ebből a mögötte álló pontosan tudni fogja mit mondjon.

Ennyi....

Encsé (http://gekko.csokavar.hu) 2008-04-25 21:42:05

Danaudioslave: reggel végigvittük ezt az elgondolást, és nyomban kitaláltunk egy egyszerűbbet is. Sétáljon végig az egyik rab az összes többi előtt, és kacsintson egyet a bal szemével, ha az illetőn fekete sapka van. Ha már nem tud többet kacsintani, akkor átálhat a sántításra is.

De most komolyan: ha a rabok kommunikálhatnak, akkor hol a feladat?

(Cactus majd megírja a másik ellenvetésünket is.)

Danaudioslave 2008-04-25 22:03:17

Akkor nincs egyértelműen megfogalmazva a feladat: ugye az a kérdés hogy:"Milyen stratégiát találjanak ki a rabok, hogy biztosan kijussanak?" amit írtam az egy stratégia. Ezek után megkérdezném, hogy egyáltalán összebeszélhetnek előtte a rabok?

vagy minden rabnak magában kell kitalálnia milyen sapka van a fején? Akkor ugyanis már nem stratégiáról beszélünk, hanem tippelésről.

Mégis mi a gond?

Danaudioslave 2008-04-25 22:07:12

Talán hogy semmilyen axiómát, nevezetes matekmatika összefüggést nem tartalmaz, az is kikötés?:P

Bele tegyem Taylort, vagy Fouriert?

cactus 2008-04-25 22:07:38

Ha a rabok tényleg így egyenként sorbaállnak, akkor a sorbaállás pont végtelen ideig tart (arról most nem is beszélve, hogy ha nem párhuzamosan kérdezik meg a tippjeiket, akkor önmagában a kikérdezés is végtelen időt vesz igénybe). Ez viszont azt jelenti, hogy mire kijutnának, addigra pont le is töltötték a büntetésüket...

k 2008-05-12 14:59:59

Ket tuti strategia konstans ido alatt: ;-)

A/

1. a rabok parokba rendezodnek, egymassal szembe allva

2. ha egy rab parjan fekete sapka van a bal kezet emeli fel, kulonben a jobb kezet

B/

1. parokba mint elobb

2. sapkat cserelnek ... X-D

cactus 2008-05-17 00:25:50

Nyilván a feladat úgy szól, hogy amikor megnézik egymás fején a sapkát, akkor már nem kommunikálhatnak...

Kovi :) 2012-05-15 14:17:26

Ezt egy matekórán kérdezték az osztálytól, és jól leégtünk mert senki sem tudta xD annyi tuti, hogy az utolsó rosszul jár, mert neki mindenképpen az előtte álló sapkája színét kell mondania... ennyit megértettem. :D