Fórum: Csak logika

Ez egyrészt nem pontos, ugyanis mindenki két lehetséges esetre tudja szűkíteni az általad felsorolt hármat:

egy kék szemű szerint a két lehetséges eset a 99 kék, 901 barna, illetve a 100 kék, 900 barna szemű lakó;

egy barna szemű szerint a két lehetséges eset a 100 kék, 900 barna, illetve a 101 kék, 899 barna szemű lakó.

Másrészt nem magyaráztad meg, hol van a hiba. Te azt mondod, hogy 'a saját szemének színét senki nem tudja, tehát...', a 2. gondolatmenet pedig éppen azt vezeti le, hogy 'néhány nap elteltével mindenki tudja'.

A második gondolatmenet azért nem jó, mert mindenki csak annyit tud, hogy 3 lehetséges eset van:

1.) 99 kék-szemű és 901 barna-szemű él a szigeten

2.) 100 kék-szemű és 900 barna-szemű él a szigeten

3.) 101 kék-szemű és 899 barna-szemű él a szigeten

És mivel a saját szemének színét senki nem tudja, senki nem tud dönteni, hogy a fönti 3 lehetséges esetből melyik igaz.

Akkor mi a hiba a 2. gondolatmenettel?

Kicsit egyszerűbben fogalmazva: a stabilitást az biztosítja, hogy senki nem tudja a saját szem-színét. A látogató búcsúszavai ezen nem változtatnak, tehát az 1. sz válasz a helyes.

Ők nem tudják, hogy 100 kék szemű, 900 barna szemű (tehát nem tudják az arányukat sem). Ők csak azt tudják, hogy mindenki szeme kék vagy barna, valamint mindegyikük tudja az összes társának szemszínét.

Szerintem ez stabil alapfelállás.

Ha a szigetlakók ismernék a kék és barna szeműek arányát, akkor már rég az összes öngyilkos lenne a 2. gondolatmenet alapján. S mivel eme gondolatmenetből minden kék szeműnek következik, hogy n vagy n-1 a kék szeműek aránya, ezért még az utazó érkezése előtt harakirit kellett volna csinálni az egész szigetnek 2 nap leforgása alatt.

Azaz az alapfelállás nem stabil. Ilyen alaphelyzet nem működik, alapból önellentmondásos.

Az alábbi feladatot szintén Terry Tao blogján találtam. Elnézést kérek, ha már szerepelt itt.

Egy szigeten 1000 bennszülött él egy törzsben, közülük 100 kék szemű, 900 barna szemű. Mind ismerik a többiek szemszínét, de a sajátjukat nem. Sőt, a vallásuk azt is előírja, hogy ha valamelyikük megtudja a saját szemének színét, akkor a következő délben az egész törzs előtt öngyilkos legyen (ezért a szemük színéről sohasem beszélgetnek). A szigetlakók nagyon okosak és nagyon vallásosak; tudják egymásról, hogy nagyon okosak és nagyon vallásosak; tudják egymásról, hogy tudják egymásról, hogy nagyon okosak és nagyon vallásosak; és így tovább.

Egy nap egy utazó érkezik a szigetre, és egy darabig a törzzsel él. A búcsúvacsorán a következőt mondja az egész törzs előtt: 'nagy meglepetésemre szolgál, hogy a világ ezen részén is találkozni kék szemű emberrel'.

Mi történik ezután?

1. gondolatmenet: semmi. Ugyanis a szigetlakók eddig is tudták, hogy vannak közöttük kék szeműek, tehát az utazó nem közölt velük semmit, amit eddig ne tudtak volna.

2. gondolatmenet: a búcsúvacsora utáni 100. napon minden kék szemű bennszülött öngyilkos lesz. Ugyanis: állítjuk, hogy ha n kék szemű ember van, akkor azok az n. napon (a búcsúvacsora után) öngyilkosok lesznek; viszont ha n-nék több kék szemű ember van, akkor azok nem lesznek öngyilkosok az n. napon. Ezt teljes indukcióval bizonyítjuk. Ha n=1, akkor az egyetlen kék szemű ember az utazótól (látva a többiek barna szemét) megtudta a saját szemszínét, így öngyilkos lesz, rögtön az első napon. Az is világos, hogy ha egynél több kék szemű ember van, akkor azok nem lesznek öngyilkosok az első napon, hiszen az utazó kijelentése után egyik kék szemű sem biztos benne, hogy az utazó rá gondolt, amikor a kék szemű emberekről beszélt. Most tegyük fel, hogy n2, és az állítás n-1-ig igaz. Mivel n kék szemű ember van, ezek az n-1. napot túlélik. Viszont az n kék szemű ember mindig is tudta, hogy csak n-1 vagy n kék szemű ember lehetett, tehát mivel az öngyilkosságok elmaradtak az n-1. napon, mindegyik megtudta, hogy n kék szemű ember van, melyek egyike éppen ő. Tehát az n. napon mind az n kék szemű öngyilkos lesz. Ezzel az indukció kész. Tehát a 100 kék szemű ember a 100. napon öngyilkos lesz. Könnyű meggondolni, hogy a 101. napon a többiek is öngyilkosok lesznek.

Mi az igazság? Hol a hiba valamelyik gondolatmenetben?

Szerintem nincs, de nem vagyok teljesen biztos benne.

Már egy hónap eltelt, szerintem lelőheted.

Nem is akart játékot feltalálni!

itt

,,Módosítás a feladathoz: Ki tudnak-e találni egy olyan stratégiát, amelynek segítségével legfeljebb c ember hal meg? (azaz van-e olyan c, amivel igen a válasz; ha van, akkor mi a legkisebb)''

Ha nem tolonganak az érdeklődők, akkor nemsoká lelövöm, és abból indulóan van további kérdésem.

Még az jut eszembe, hogy azt is gyakran szokták hangsúlyozni, hogy a következők ekvivalensek: kiválasztási axióma, Zorn lemma, jólrendezési tétel, Teichmüller-Tukey lemma. Ahol az ekvivalencia úgy értendő, hogy ZF axiómái mellett bármelyikből belátható az összes többi. Itt még láthatunk egy regiment ekvivalens állítást.

Nem egészen értek egyet.

Abban teljesen igazad van, hogy használunk más axiómákat is.

Ugyanakkor a kiválasztási axiómát egy kicsit szokás külön kezelni. Nem vagyok sem halmazelmélész, sem logikász, de azt ellestem a halmazelmélészektől és logikászoktól, hogy a 'kivax' azért speciális. Nem értek hozzá, nem tudom, miért van így, de ha valami megy kiválasztási axióma nélkül, akkor azt igyekeznek nélküle megcsinálni, és csak akkor használják a kiválasztási axiómát, ha muszáj. Több tétel állítását is hallottam már úgy, hogy 'kiválasztási axióma mellett igaz az, hogy ...' -- a többi axiómát nem hangsúlyozva.

Egy egyetemi emlékem a következő. Móri Tamás tanár úr (pedig ő valószínűségelmélész, tehát nem a matematika alapjaival foglalkozik) egy valószínűségszámítási tételnél megjegyezte, hogy kiválasztási axiómával könnyen kijön, aztán nekiállt egy nehezebb bizonyításnak, mondván hogy az a pofonegyszerű kiválasztási axiómás érvelés ,,úri huncutság''. A végtelen halmazok sohasem zavarták.

-----

Ott van Wedderburn tétele: minden véges ferdetest kommutatív. És ha valaki megkérdezné tőlem, hogy ez min múlik, akkor azt mondanám, hogy a végességen. Pedig ugyanúgy szükségünk van a ferdetest axiómáira, de azok inkább a nyelvét teremtik meg a tételnek. A feladat megoldása ZFC-ben történik, és igazából C-n múlik; ZF nélkül a feladatot el se tudnánk mondani, arra már a terminológia miatt is szükségünk van (ha nem is ZF összes axiómájára).

És persze ebben van önkényesség.

Ez a példa csak akkor megrázó, ha az ember elvárja hogy a végesben megszokott dolgok végtelenben is működjenek. És ez a feladat is olyan, hogy ha valaki meghallgatja a megoldást is, nem csak az eredményt, már egyből természetesebbnek tűnik, hogy így van (persze az előtt én is a másikra tippeltem volna).

Én sosem tartom jogosnak amikor az ilyesmit a "kiválasztási axióma következményének" titulálják. A bizonyítás sok másik axiómát is felhasznál, amiket ilyen alapon ugyanúgy lehetne vitatni. Például a végtelenségi axióma sokkal kevésbé szemléletes (bizonyos értelemben antiszemléletes, mert nincsenek végtelen dolgok igazából), mégis mindenki elfogadja. Szóval tessék csak megbékélni az axiómákkal és nem bolygatni őket.

Egy megjegyzés. További érdekesség, hogy sehol nem használjuk azt, hogy két lehetőség van minden egyes sapka színére. Tehát ha mindenki homlokára akár egy valós számot írnak, és mindenkinek a saját számára kell tippelnie, akkor is elérhető, hogy csak véges sokan tévedjenek. Ez már végképp sokkoló.

Számomra ebben a feladatban elsőre az volt az igazán meglepő, hogy az ártatlannak és szemléletesnek kinéző kiválasztási axiómának ilyen természetellenes következményei vannak. A kiválasztási axiómát olyan dolgokra használjuk általában, hogy 'minden vektortérnek van bázisa', vagy hogy 'van nem Lebesgue-mérhető halmaz a számegyenesen'. Ez a példa azoknál sokkal megrázóbb, pedig sokkal egyszerűbb.

Az a lényeg, hogy a "csak véges sokban tér el" ekvivalencia reláció, így osztályokra bonthatjuk a sapka kiosztásokat úgy, hogy egy csoportban a kiosztások csak véges sokban térnek el.

Ezek után minden ilyen osztályból kitüntetünk egy elemet (ezt megtehetjük, ennek halmazelméleti okai vannak). Mikor egy játékos szétnéz, akkor el tudja dönteni melyik osztályba esik a kiosztás. Azt a színt tippeli, amilyen színű a sapkája az osztály kitüntetett kiosztásában. Mivel így pont az osztály kitüntetett kiosztását fogják tippelni, és az csak véges sokban tér el az aktuális kiosztástól, így csak véges sokan tévednek.

Módosítás a feladathoz: Ki tudnak-e találni egy olyan stratégiát, amelynek segítségével legfeljebb c ember hal meg? (azaz van-e olyan c, amivel igen a válasz; ha van, akkor mi a legkisebb)

Ez a megoldás! Leírod egy kicsit részletesebben, hogy más is megértse?

No igen, ez már jogosnak tűnik. Akkor mivel időközben azt is elárultad, hogy van stratégia, ahhoz egy ötlet: ha valaki véges sok kéket lát, mondjon pirosat, ha véges sok pirosat, akkor mondjon kéket. Ez megoldja az ilyen eseteket. A többi esetben is valami ilyesmit kéne csinálni: venni kitüntetett helyzeteket, és ha attól csak véges sokban tér el amit látsz, akkor ahhoz igazodva mondasz (ilyen volt a spec esetben a csupa kék és a csupa piros).

Tegyük fel, hogy X alkalmaz valami stratégiát!

Az 1/2 valószínűség [691]-es hozzászólásod értelmében az, hogy

P(X  túlél|X  a  többieken  ...-ot  lát)=1/2.

Hogyan következik ebből, hogy

P(X  túlél)=1/2?

A [691]-ben előbbi mellett érvelsz, aztán [697]-ben utóbbit használod. Pedig az 'X a többieken ...-ot lát' olyan események ('...' befutja az összes lehetségest), amik mind 0 valószínűségűek, tehát nem lehet csak úgy utóbbira következtetni az előbbiből.

(Attól mert nem valószínűségszámítás feladat, használható a megoldásban valószínűség számítás.) Természetesen nem függetlenek az elbukási események, ezt sosem állítottam. De a bukási esélyek 0.5-ök fejenként. Így érvényes amit írtam: Annak az esélye, hogy "végtelen sok 0.5-os esemény közül csak véges sok esemény következik be" maximum 0.5 lehet (a feladat meg azt kérdezi lehet-e ez a biztos esemény, ami pedig 1 valószínűségű).

Minden rab csak annyit lát, hogy kinek mi van a fején, és ha egyszerre tippelnek, és nem jelezhetnek egymásnak, akkor függetlenül tippelnek. Mindenki tehát max. azt szűri le, hogy milyen színből van több, és azt tippeli, ezzel mindenki a többször szereplő színt tippeli be, és többen szabadulnak, mint halnak. (Az sem túl stabil, hogy végteleneket hasonlítgatunk össze, de ez mellékes.) Viszont az is lehet, hogy kékből és pirosból is végtelen sok van (lásd modulo 3 maradékosztályok), és akkor végtelen sokan halnának meg. Tehát nincs jó stratégia? Az én részemről szabad a gazda.

Akár egymástól függetlenül sorsolják a sapkákat, akár nem, az elképzelt stratégiában a rabok nyilván nem egymástól függetlenül* tippelnek. Emberünk persze -- mint mindenki más -- 1/2 eséllyel elbukik, de ezek az elbukások nem független események.

* 'nem egymástól függetlenül': a valószínűségi értelemben értendő; a szabályoknak megfelelően persze nem használják egymás tippjeit, tehát ebben persze egymástól függetlenül, de nem erről beszélek

-----

A nagy félrecsúszás elkerülése céljából: ez egy logika (vagy tetszés szerint halmazelmélet) feladat, nem valószínűségszámítás. Kicsit sok volt a Monty Hall, ennek a feladatnak semmi köze a valószínűségekhez. Nyilván egy valószínűségi módszert használó rossz megoldás valószínűségi hibát vét, csak azért valószínűségeztem, hogy ezt elmagyarázzam.

Hopsz, ezzel a válasz lelőttem, de az talán már a [690]-es hozzászólásomból is sejthető volt. De a feladat lényegi része még nyitva maradt...

Ha véges számú rabról van szó, akkor minden stratégiára igaz, hogy tetszőleges sapkakiosztás után véges sokan veszítenek. A konkrét stratégiát is le lehet hozni véges sok ember esetére (bár elég semmitmondó lesz).

Az talán nem számít lelövésnek, ha elárulod: Az - egyelőre ismeretlen - megoldás érvényes marad-e, ha véges számú rabról van szó?

Szerintem ez mindenképpen igaz, ha feltesszük, hogy a sapkákat egymástól függetlenül sorsolják (amit feltehetünk): Ekkor emberünk a többiek fején lát valamit, ez alapján tippel valamit (mondjuk kéket), de 0.5 eséllyel piros van a fején.