Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Fórum: Csak logika

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]    [15]    [16]    [17]    [18]    [19]    [20]    [21]    [22]    [23]    [24]    [25]    [26]    [27]    [28]    [29]    [30]  

Szeretnél hozzászólni? Jelentkezz be.
[726] Micimackó2014-01-01 22:42:50

Akkor a kettes megoldás a helyes a feladatra? Harakiri a 100. napon? Az első megoldás úgyis elég elkentnek tűnt.

[725] Maga Péter2013-12-30 22:43:12

A feleséges és szemszínes feladat ugyanaz, függetlenül attól, hogy a polgármester kijelentése előtt is élnek-e a törvények.

1. Annyiban változik, hogy a második, nem a századik napon lesznek öngyilkosok.

2. Igen, lényegében ez játszódik le a fejekben.

3. Van létjogosultsága. Mint látjuk, nemcsak a tények, hanem a tények ismerete is számít. Nyelvileg bonyolultabb, de logikailag ezt iterálni kell. Bár mindenki tudja, hogy legalább 99 kék szemű ember van; és mindenki tudja, hogy mindenki tudja, hogy legalább 98 kék szemű ember van; azt már nem tudja mindenki, hogy mindenki tudja, hogy mindenki tudja, hogy legalább 98 kék szemű ember van. Így joggal játszanak a 98 kék szempár alatti gondolatmenetek.

Előzmény: [724] HoA, 2013-12-30 12:52:45
[724] HoA2013-12-30 12:52:45

Re [723] : Igazad van, [721]-ben tévedtem.

Re [722] : Természetesen a kocsmában mindenki tudja a szabályt: az érintett férjnek nem szólunk. És így persze mindenki tudja, hogy mindenki tudja ...

Re: "ha az összes többi törvény korábban is fennállt" : Éppen emiatt hoztam elő ezt a feladatot. Ha az összes többi törvény korábban is fennállt, akkor a feleségek és a kékszeműek feladata nekem ekvivalensnek tűnik. De ekvivalensek-e, ha a feleségeket csak a polgármester közzététele után kell megölni?

Más. Belenéztem a hivatkozott blog hozzászólásaiba. Sokkal nem lettem okosabb. Néhány kérdést talán érdemes felvetni:

1)Változik-e a helyzet, ha az utazó azt mondja ( amit mindenki tud ) : „Milyen jó, hogy legalább 98 kékszemű ember él a szigeten!” ?

2)Mi van, ha az indukciót felülről kezdjük? Egyenértékű-e a 2. gondolatmenettel az alábbi: Az egyik kékszemű ( K1 ) lát 99 kékszeműt és azt gondolja: ha én nem vagyok kékszemű, akkor

Az egyik kékszemű ( K2 ) lát 98 kékszeműt és azt gondolja: ha én nem vagyok kékszemű, akkor

Az egyik kékszemű ( K3 ) lát 97 kékszeműt és azt gondolja: ha én nem vagyok kékszemű, akkor

. . .

Az egyik kékszemű ( K99 ) lát 1 kékszeműt és azt gondolja: ha én nem vagyok kékszemű, akkor

K100 rájön, hogy ő kékszemű és délben öngyilkos lesz. De mivel ez nem következik be

K99 rájön, hogy ő kékszemű és másnap délben öngyilkos lesz. De mivel ez nem következik be

K98 rájön, hogy ő kékszemű és másnap délben öngyilkos lesz. De mivel ez nem következik be

. . . K1 rájön, hogy ő kékszemű és a 100. napon öngyilkos lesz. Akárcsak a többiek.

3)Mivel bármelyik két kékszeműt kiválasztva kölcsönösen tudják egymásról, hogy a másik legalább 98 kékszeműt lát, van-e jogosultsága egy olyan gondolatmenetnek, amelyben – akármilyen feltételekkel – szerepel olyan feltételezás, hogy valaki 98-nál kevesebb kékszeműt lát?

Erről megint eszembe jut gyerekkorom egy másik feladata: a 3 fekete és 2 kék sapka. Ha valaki nem ismerné: 3 okos embert beültetnek egy szobába. Bemutatnak 3 fekete és 2 fehér sapkát. Eloltják a lámpát, mindenkire ráhúznak egy sapkát. Mindenki látja a másik kettő sapkáját, a sajátját nem. Történetesen mindenkire feketét húznak. Beszélni, jelezni persze tilos. Aki rájön a sapkája színére, emelje fel a kezét. Egy idő után a „legokosabb” jelentkezik. Hogyan jött rá?

Ma már tudom, ez így nem teljesen jó. Mert ha egyformán okosak, mi az, hogy a legokosabb? Hogy jobban hasonlítson a kékszeműekhez, kvantáljuk az időt. Tehát: Felgyújtják a lámpát és 10 másodpercenként megszólal egy gong. A gong megszólalásakor mindenki letesz az asztalra egy „tudom” vagy „nem tudom” cédulát.

A megoldás:

O1 ezt gondolja: ha rajtam fehér sapka van, akkor

O2 ezt gondolja: ha rajtam fehér sapka van, akkor

O3 ezt gondolja: látok két fehér sapkát,

tehát rajtam fekete van, és az első gongra jelez . De mivel ez nem következik be O2 ezt gondolja :

tehát rajtam fekete van, és a második gongra jelez . De mivel ez nem következik be O1 ezt gondolja : tehát rajtam fekete van, és a harmadik gongra jelez.

Itt a 3) kérdés éppen nem merül fel. Bármelyik két ember kölcsönösen tudja egymásról, hogy a másik is legalább egy feketét lát és a gondolatmenet ezzel nincs is ellentmondásban. Mi a helyzet, ha háromnál több okos van? mondjuk 10 ember, 10 fekete és 9 fehér sapka?

(Úgy látom, a fehér sapkák szerepe az, mint a kékszeműeknél a bejelentésé: Deklaráljuk, hogy legalább egyvalaki fején fekete sapka van.)

Előzmény: [723] Maga Péter, 2013-12-30 09:02:50
[723] Maga Péter2013-12-30 09:02:50

,,A két kékszemű az utazó érkezése nélkül is már rég öngyilkos lett volna: Lát egy kékszemű embert és mivel az nem lett öngyilkos, ezért rájön, hogy ő is kékszemű.'' Nem. De akkor először menjünk le az 1 kék szemű szintre. Az utazó megszólalása előtt ő nem lenne öngyilkos, hiszen nem tudja, hogy a 0 kék, 1000 barna vagy az 1 kék, 999 barna felállás a valóság.

Előzmény: [721] HoA, 2013-12-29 23:14:33
[722] Maga Péter2013-12-30 08:49:18

Egyrészt, ez így nem pontos: 'a csalfa feleségekről mindenki tud, csak a férj nem' nem elég. Kell rekurzívan is: mindenki tudja (...); mindenki tudja, hogy mindenki tudja (...) stb. Különben, ha csak egy csalfa feleség lenne, már őt sem ölné meg a férje: bár tudja, hogy van csalfa feleség, és nem tud egyről sem, de ha nem tudja, hogy ő a sajátján kívül az összesről tud, akkor ebből nem tudja levezetni, hogy az övé csalfa.

Másrészt mit változtat ezen, ha a polgármester csak a 'van csalfa feleség a városban' információt dobja be, és az összes többi törvény korábban is fennállt?

Előzmény: [719] HoA, 2013-12-29 22:51:50
[721] HoA2013-12-29 23:14:33

Az "óra indul" különbség arra vonatkozik, hogy a kékszeműeknek eddig is öngyilkosnak kellett volna lenniük, ha rájönnek a szemük színére, a vadnyugati férjeknek viszont nem kellett ölniük.

Hasonlítsuk össze a 100 nő és 100 kékszemű helyett a jobban áttekinthető 2 csalfa nő - 2 kékszemű feladatot. A két kékszemű az utazó érkezése nélkül is már rég öngyilkos lett volna: Lát egy kékszemű embert és mivel az nem lett öngyilkos, ezért rájön, hogy ő is kékszemű. A két csalfa feleség városában a két megcsalt férj tud 1-1 csalfa nőről, de ha nem jelenik meg az ölési utasítás, boldogan élnek, míg meg nem halnak.

Előzmény: [718] Maga Péter, 2013-12-29 22:03:33
[720] HoA2013-12-29 22:54:01

Bocs, egy elírás: A két csalfa nő persze a közzététel utáni második napon kerül a főtérre.

Előzmény: [719] HoA, 2013-12-29 22:51:50
[719] HoA2013-12-29 22:51:50

De az utazó mondata nem tartalmaz információt.

A feladat: Vadnyugati kisvárosban 100 nő csalja a férjét. A férfiak a kocsmában beszélgetnek, a csalfa feleségekről mindenki tud, csak a férj nem. A polgármester megunja és egy este a következőket teszi közzé:

- Van csalfa feleség a városban.

- Mostantól mindenki bezárkózik a házába, további kommunikáció nincs.

- Aki rájön, hogy a felesége csalja, köteles délben a holttestét kitenni a főtérre.

- Este mindenki kimehet a főtérre megnézni a helyzetet.

Mindenki logikai zseni.Kérdés: Mikor hány holttest jelenik meg a főtéren?

A megoldás persze a 2. gondolatmenethez hasonló: Mi lenne, ha csak egy csaló feleség lenne? A férje eddig nem tudott csalfa nőről, most megtudta hogy van ilyen, tehát öl és kiteszi. A többiek - akik egy csalfa nőről tudtak - pont erre számítanak és másnap este elégedetten látják a hullát.

Mi lenne, ha két csalfa asszony lenne? Az ő férjük egyről tud, tehát az előző esetre számít. Mivel a közzététel utáni este nem jelenik meg holttest, hazamennek és a közzététel utáni napon két holttest jelenik meg.

És így tovább. Ha 100 csalfa nő van, a 100 érintett férj csak 99-ről tud, ezért a közzététel utáni 99. nap estéjére várja a holttesteket, és mivel azok nem jelennek meg, a következő napon 100 holttest kerül a térre.

Érdekes, hogy a levezetéshez itt is szükség van arra tényre, amit mindenki tud, nevezetesen, hogy van csalfa nő a városban.

Előzmény: [718] Maga Péter, 2013-12-29 22:03:33
[718] Maga Péter2013-12-29 22:03:33

De ha a 2. gondolatmenet helyes, 'óra indul' itt is van, az utazó mondata.

Előzmény: [716] HoA, 2013-12-29 21:15:22
[717] Maga Péter2013-12-29 21:50:19

Mi ez a 'csalfa feleségek'?

Előzmény: [716] HoA, 2013-12-29 21:15:22
[716] HoA2013-12-29 21:15:22

Összehasonlítva a valószínűleg szintén sokak által ismert "csalfa feleségek a vadnyugati városban" feladattal, szerintem az a lényeges különbség, hogy ott van egy "óra indul" pillanat, és csak onnantól kezdve él az "aki megtudja, az köteles ölni" szabály. Itt már eleve él a szabály, hogy aki megtudja a szeme színét, annak öngyilkosnak kell lenni. Talán ebből vezethető le, hogy miért nem működik itt a második gondolatmenet logikája.

Előzmény: [713] Maga Péter, 2013-12-29 17:03:29
[715] Maga Péter2013-12-29 21:03:46

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'.

Előzmény: [714] Zilberbach, 2013-12-29 20:22:18
[714] Zilberbach2013-12-29 20:22:18

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.

Előzmény: [713] Maga Péter, 2013-12-29 17:03:29
[713] Maga Péter2013-12-29 17:03:29

Akkor mi a hiba a 2. gondolatmenettel?

Előzmény: [712] Zilberbach, 2013-12-29 16:15:08
[712] Zilberbach2013-12-29 16:15:08

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.

Előzmény: [711] Maga Péter, 2013-12-29 15:54:47
[711] Maga Péter2013-12-29 15:54:47

Ő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.

Előzmény: [710] Hajba Károly, 2013-12-29 15:39:58
[710] Hajba Károly2013-12-29 15:39:58

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.

Előzmény: [709] Maga Péter, 2013-12-29 13:44:14
[709] Maga Péter2013-12-29 13:44:14

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 n\geq2, é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?

[708] w2013-03-17 18:43:18

Szerintem nincs, de nem vagyok teljesen biztos benne.

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

Előzmény: [706] Maga Péter, 2013-01-29 15:33:52
[707] lorantfy2013-02-12 10:26:32

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

itt

[706] Maga Péter2013-01-29 15:33:52

,,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.

Előzmény: [701] Micimackó, 2013-01-27 21:13:23
[705] Maga Péter2013-01-28 20:30:41

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.

Előzmény: [704] Maga Péter, 2013-01-28 20:25:14
[704] Maga Péter2013-01-28 20:25:14

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.

Előzmény: [703] Micimackó, 2013-01-28 18:25:31
[703] Micimackó2013-01-28 18:25:31

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.

Előzmény: [702] Maga Péter, 2013-01-28 09:11:08
[702] Maga Péter2013-01-28 09:11:08

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.

Előzmény: [701] Micimackó, 2013-01-27 21:13:23

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]    [15]    [16]    [17]    [18]    [19]    [20]    [21]    [22]    [23]    [24]    [25]    [26]    [27]    [28]    [29]    [30]