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.
[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
[701] Micimackó2013-01-27 21:13:23

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)

Előzmény: [700] Maga Péter, 2013-01-27 10:52:08
[700] Maga Péter2013-01-27 10:52:08

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

Előzmény: [699] Micimackó, 2013-01-27 10:21:14
[699] Micimackó2013-01-27 10:21:14

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

Előzmény: [698] Maga Péter, 2013-01-26 21:26:33
[698] Maga Péter2013-01-26 21:26:33

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.

Előzmény: [697] Micimackó, 2013-01-26 19:00:40
[697] Micimackó2013-01-26 19:00:40

(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ű).

Előzmény: [695] Maga Péter, 2013-01-26 18:33:06
[696] w2013-01-26 18:38:24

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.

Előzmény: [694] Maga Péter, 2013-01-26 18:18:35

  [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]