Matek feladatok

Fő kategória: matek.

Néhány gyűjtemény, ahonnan én is szemezgettem:

Téglalapok száma a sakktáblán

Számoljuk meg azt, hogy hány téglalap van a sakktáblán!

Sakktábla lefedése dominókkal

Egy sakktábla tetszőleges átlójából vegyünk el két mezőt. Az így megmaradt sakktáblát le tudjuk-e fedni szabályos dominókkal, hézagmentesen?

+ Megoldás (kinyit)

Zsinór égetése

Van két zsinórunk, melyeket ha meggyújtunk, nem lineárisan fél-fél óra égnek el. Hogyan tudunk kimérni velük 45 percet?

+ Megoldás (kinyit)

A légy által megtett út

Van két vonat, az egyik 50 km/h, a másik 70 km/h sebességgel halad egymás felé. A vonatok 120 km-re vannak egymástól. Egy légy elindul a gyorsabb vonat felől a rövidebb vonat felé. Amikor eléri a lassúbb vonatot megfordul a gyorsabb vonat felé, és így tesz egészen az ütközésig. A légy sebessége 100 km/h. Mennyi utat tesz meg összesen a légy?

+ Megoldás (kinyit)

Almák és narancsok

Van három láda: az egyikben 10 darab alma, a másikban 10 darab narancs, a harmadikban pedig vegyesen 5-5 darab alma ill. narancs van. Mindhárom ládán van egy-egy címke: az egyiken egy alma, a másikon egy narancs, a harmadikon pedig egy alma és egy narancs. Csakhogy a címkék felcserélődtek: mindegyik ládán rossz címke van. A feladat az, hogy a címkét áthelyezzük a megfelelő ládára. Ehhez tetszőleges számú mintavételezést hajthatunk végre. Legalább hány mintavételezésre van szükség ahhoz, hogy biztosan meg tudjuk állapítani, melyik címkét melyik ládára kell tenni?

+ Megoldás (kinyit)

12 golyó

Van 12 golyó. Ezek közül 11 ugyanakkora tömegű, a 12. tömege pedig egy picit eltér a többitől, de azt nem tudjuk, hogy több, vagy kevesebb. A feladat annak meghatározása, hogy melyik golyó az eltérő, és milyen irányba. Egy kétkarú mérleg segítségével tetszőleges számú mérést végezhetünk. Mennyi a minimális mérésszám, és milyen módszerrel hajtsuk végre a méréseket?

+ A minimális mérésszám (kinyit)

+ Megoldás (kinyit)

- Megoldás (becsuk)

Első mérés: osszuk 3 részre a golyókat. Jelöljük számokkal: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Tegyük az 1, 2, 3 és 4-es számú golyót a mérleg bal, az 5, 6, 7 és 8-as számú golyót pedig a mérleg jobb oldalára. Lehetséges esetek:

A mérleg nem billen ki: az 1-8 sorszámú golyókról biztos tudjuk, hogy egyik sem eltérő. Második mérés: az 1, 2 és 3-as golyót tegyük a mérleg bal, a 9, 10 és 11-es golyót pedig a mérleg jobb oldalára. Lehetséges esetek:
- A mérleg nem billen ki: ez esetben a 9, 10 és 11 sem eltérő, a 12-es az eltérő. Harmadik mérés: tegyük az 1-es golyót a mérleg bal, a 12-es golyót pedig a jobb oldalára.
  - A mérleg nem billen ki: nem lehetséges.
  - A mérleg balra billen: megoldás: a 12-es golyó könnyebb, mint a többi.
  - A mérleg jobbra billen: megoldás: a 12-es golyó nehezebb, mint a többi.
- A mérleg balra billen: a 9, 10 és 11-es golyó közül az egyik könnyebb. Harmadik mérés: tegyük a 9-es golyót a mérleg bal, a 10-est pedig a jobb oldalára.
  - A mérleg nem billen ki: megoldás: a 11-es golyó könnyebb, mint a többi.
  - A mérleg balra billen: megoldás: a 10-es golyó könnyebb, mint a többi.
  - A mérleg jobbra billen: megoldás: a 9-es golyó könnyebb, mint a többi.
- A mérleg jobbra billen: az előző eset fordítottja.
A mérleg balra billen: ez esetben vagy az van, hogy az 1, 2, 3 és 4-es számú golyók valamelyike nehezebb, vagy az, hogy az 5, 6, 7 és 8-as számú golyók valamelyike könnyebb. Második mérés: tegyük az 1, 2, 3 és 5-ös számú golyót a mérleg bal, a 4, 9, 10 és 11-es számú golyót pedig a jobb oldalára. Tehát a bal oldalon 3 olyan golyó van, amelyek közül az egyik lehet, hogy nehezebb, mint a többi, és egy olyan, ami lehet, hogy könnyebb, a jobb oldalon pedig egy olyan, ami lehet, hogy nehezebb, és három olyan, amiről biztos tudjuk, hogy nem tér el. Lehetséges esetek:
- A mérleg nem billen ki: a mérésből kimaradt golyók egyike lesz a megoldás. A mérésből a 6, 7, 8 és 12 sorszámú golyó maradt ki. A 12-esről tudjuk, hogy nem tér el a többitől, a 6, 7 és 8-as golyóról pedig tudjuk, hogy valamelyike könnyebb, mint a többi. Az első pontban leírt módszer szerint járunk el.
- A mérleg balra billen: mivel a mérleg jobb oldalán levő golyókról azt tudjuk, hogy három biztosan nem eltérő, a negyedik pedig ha eltér, akkor csakis nehezebb lehet, ezért az eltérő golyó nehezebb, mint a többi, és az a mérleg bal oldalán van. Mivel az 5-ös számú, ha eltérő lenne, akkor tudnánk, hogy az könnyebb lenne, így az eredmény csakis az 1, 2 és 3-as számú golyók közül kerülhet ki, ami nehezebb, mint a többi. Erre az esetre már láttunk egy lépéses megoldást.
- A mérleg jobbra billen: mivel az 1, 2 és 3 golyók, ha eltérnének, akkor csakis nehezebbek lehetnének, de ezzel a méréssel ezt az esetet is kizártuk. Így az eltérést vagy a mérleg bal oldalán levő talán a többinél könnyebb 5-ös számú golyó, vagy a jobb oldalán levő 4-es számú, a többinél talán nehezebb okozza. Harmadik mérés: tegyük a mérleg bal oldalára a 4-es, a jobb oldalára pedig az 1-es golyót.
  - A mérleg nem billen ki: megoldás: az 5-ös golyó könnyebb, mint a többi.
  - A mérleg balra billen: megoldás: a 4-es golyó nehezebb, mint a többi.
  - A mérleg jobbra billen: nem lehetséges.
A mérleg jobbra billen: az előző pontban leírt módszert alkalmazzuk, értelemszerű fordításokkal.

A feladatot próbáljuk meg megoldani ugyanennyi lépésszámmal úgy, hogy előre megadjuk a méréseket, és a három mérés eredményéből határozzuk meg az eredményt!

+ Megoldás (kinyit)

Cukorkák

Van 3 csomag cukorkánk. Legalább az egyikben 4 grammosak a cukorkák, s legalább az egyikben 5 grammosak. Ezen kívül van egy szuper pontos mérlegünk. Egyetlen méréssel hogyan állapítjuk meg, hogy melyik csomagban hány grammosak a cukorkák?

+ Megoldás (kinyit)

Érmék

Van 500 darab egydollárosunk, és ezzel 1-től 500 dollárig tetszőleges összeget ki tudunk fizetni. Viszont a magasabb összegeket elég hosszadalmas kiszámolni, ezért elhatározzuk, hogy bezacskózzuk, és a zacskóra ráírjuk, hogy hány darab egy dolláros van benne. Minimálisan hány darab zacskóra van szükség ahhoz, hogy továbbra is tetszőleges összeget ki tudjunk fizetni (a zacskód felbontása nélkül)?

+ Megoldás (kinyit)

Kockadobós játék

Aladár és Bála a következőt játsszák: egymás után dobnak egy szabályos 6 oldalú dobókockával, és az nyer, aki előbb hatost dob. Aladár kezd. Mekkora eséllyel nyer?

+ Megoldás (kinyit)

Nyeremény eldöntése kockadobással

Tudor, Vidor, Morgó, Szundi, Szende, Hapci és Kuka egyetlen dobókocka segítségével ki szeretné sorsolni, hogy kié legyen valamilyen nyeremény. Tudor a következőt javasolja:

Dobjunk háromszor a dobókockával. Az első körben Tudor, Vidor, Morgó, Szundi, Szende vagy Hapci kapjon a dobástól függően 1 pontot. A második körben Tudor, Vidor, Morgó, Szundi, Szende vagy Kuka kapjon pontot. A harmadik körben 1-től 4-ig senki se kapjon pontot, 5-ös esetén Hapci, 6-os esetén pedig Kuka kapjon. Így tehát mindenki pontosan kettő dobásban szerezhet pontot, ugyanakkora eséllyel. A végén az nyer, akinek a legtöbb pontja van. Pontegyezőség esetén egy negyedik dobással döntsünk.

A javaslatot először mindenki elfogadja, viszont valaki azt mondja, hogy neki ez így mégse jó. Ki volt az, és miért?

+ Megoldás (kinyit)

- Megoldás (becsuk)

A látszat ellenére Hapcinak és Kukának kisebb az esélye a győzelemre, ugyanis kevesebbszer jutnak be a "rájátszásra", ráadásul többszor kerülnek hármas csoportba mint kettesbe, összehasoníltva a többi törpével.

Az első 3 dobásnak 216 féle eredménye lehet, egyforma valószínűséggel: 111, 112, 113, …, 665, 666. Háromféle kimenete lehet:

2 ponttal nyer valaki. Mindenki úgy érhet el 2 pontot, hogy abban a 2 dobásban, ahol van elvi esélye nyerni, az ő száma jön ki, és a harmadik kocka bérmi lehet. Pl. Morgó úgy nyerhet, hogy az első 2 kockadobás eredménye 3-3, a harmadiké mindegy. Hapci úgy nyerhet, hogy az első kockadobás eredménye 6, a harmadiké 5, a másodiké mindegy. Tehát az összes lehetőség, hogy 2 ponttal nyerjen valaki, 7*6 = 42.
2 törpe lesz 1 pontos. Ez csak úgy jöhet ki, hogy a harmadik kockadobás eredménye 1 és 4 közötti, ugyanis az első kettő kocka mindenképp pontot ér. Az első két kockadobás eredménye vagy 2 hatos (ez esetben ugyanis Hapci és Kuka kap pontot), vagy nem lehet egyforma. Ez utóbbi lehetőségek száma 2 kocka esetén 6*5. Tehát ebbe a kategóriába 4*(1+6*5)=124 eset tartozik.
3 törpe lesz 1 pontos. Ez úgy lehetőséges, hogy a harmadik kockadobás 5-ös vagy 6-os, az első kettő nem lehet egyforma (különben lenne 2 pontos), valamint a harmadik eredményétől függően vagy az első vagy a második nem lehet hatos (különben Hapci vagy Kuka kétpontos lenne). Az általánosság megszorítása nélkül először vegyük a harmadik kockát, az 2 lehetőséget jelent. Utána vegyük azt a kockát, amelynél nem lehet hatos, tehát ha a harmadik kocka 5-ös, akkor az elsőt, ha 6-os, akkor a másodikat. Ez nem lehet hatos, tehát 5 lehetőség van. Végül vegyük a kimaradó kockát. Annak a dobásnak az eredménye nem lehet ugyanakkora, mint a másik nem harmadik kockáé, azaz itt is 5 lehetőség van. Az összes lehetőségek száma ebben az esetben: 2*5*5=50.

Összeadva a 3 esetet, kijön az összes lehetőséges eredmény: 42+124+50 = 216.

A 2 pontos győzelmek esetén nincs különbség. Elemezzük a második és a harmadik esetet.

2 törpe lett 1 pontos

Ez 124 féleképpen jöhet ki, és összesen 2*124 = 248 továbbjutó van.

Először nézzük meg Tudor, Vidor, Morgó, Szundi és Szende bejutási lehetőségeit. Mivel a valószínűségben nincs eltérés, nézzük meg Vidort! Ő kátféleképpen juthat be olyan rájátszásba: vagy az első kockával 2-est dobtunk, a másodikkal nem kettest, a harmadikkal pedig 1-től 4-ig valamekkorát, vagy az elsővel nem kettest, a másodikkal kettest, a harmadikkap pedig szintén 1-től 4-ig valamekkorát. Az összes esetek száma tehát 2*5*4 = 40.

Hapci és Kuka esete a következő. Nézük meg Kukát! Számára az első kocka dobása érdektelen, a másodiké 6-os kell, hogy legyen, és a harmadik is érdektelen. (Azt beláthatjuk, hogy ha a harmadikban jön ki a száma, akkor nem ketten, hanem hárman jutnak tovább, így az ebben az esetben nem lehetséges.) Az összes továbbjutás száma: 6*4 = 24.

Ellenőrizzük a továbbjutottak számát: 5*40 + 2*24 = 248, tehát kijött a matek.

3 törpe lett 1 pontos

Ez 50 esetben jöhet ki, így az összes tovább jutó ez esetben 150.

Először itt is azt nézzük meg, hogy hány esetben történik ez Tudor, Vidor, Morgó, Szundi és Szende esetében. Válasszuk ki mondjuk Szundit! A harmadik kocka eredménye 5 vagy 6 lehet. Az első kettő dobásból az egyiknek 4-esnek kell lennie, a másik nem lehet 4-es (különben egyből nyerne), ill. a harmadik kocka eredmnyétől függően nem lehet az első kettő közül az egyik 6-os. Azaz az egyik kocka négyese esetén a másik kocka 5 vagy 4-féle eredményt adhat. Így az összes lehetőségek száma: 2*(5+4) = 18.

Hapci és Kuka esete ebben az esetben a következő. Vegyük most Kukát! Kuka kétféleképpen juthat be: vagy a második kocka eredménye 6-os, a harmadiké 5-ös, az elsőé pedig nem lehet 6-os (különben egyből Hapci nyerne), vagy a harmadik dobás eredménye 6-os, a másodiké nem lehet 6-os (különben egybél Kuka nyerne), az elsőé pedig nem lehet ugyanaz mint a második (különben egyből az annak megfelelő törpe nyerne). Az első eset 5 dobás esetén lehetséges, a másidik pedig 5*5 dobás esetén, azaz az összes lehetőségek száma: 5 + 5*5 = 30.

Itt is kijön a matek: 5*18 + 2*30 = 150.

Összesítés

Tudor, Vidor, Morgó, Szundi és Szende összesen 40+18 = 58 esetben jutott tovább, míg Hapci és Kuka 24 + 30 = 54 esetben. Ezzel már önmagában hátrányba kerültek, viszont még ennél is nagyobb hátrányban vannak azáltal, hogy jóval gyakrabban jutnak tovább úgy, hogy hárman vannak a rájátszásban mint kettőben, összehasonlítva azzal, hogy ez hányszor történik Tudor, Vidor, Morgó, Szundi és Szende valamelyikével.

Most vegyünk 4 dobást, ami összesen 6*6*6*6 = 1296 esetet jelent! A rájátszásban 2 továbbjutó esetén döntsün a paritás (páros-páratlan), 3 továbbjutó esetében pedig a felosztás leyen 1-4, 2-5 és 3-6.

Tudor, Vidor, Morgó, Szundi és Szende győzelmeinek száma: 2 pontos győzelmek (6*6) + 2 továbbjutós győzelmek (40*3) + 3 továbbjutós győzelmek (18*2), azaz összesen 6*6 + 40*3 + 18*2 = 192.

Hapci és Kuka győzelmeinek a száma: 2 pontos győzelmek (6*6) + 2 továbbjutós győzelmek (24*3) + 3 továbbjutós győzelmek (30*3), összesen 6*6 + 24*3 + 30*2 = 168.

Végeredmény

A végreredmény tehát az, hogy 4 dobásból Tudor, Vidor, Morgó, Szundi és Szende összesen 192-szer nyer, míg Hapci és Kuka 168-szor. Az eltérés viszont a fentiek alapjén talán meglepő, hogy mindössze 14%.

Program

Leprogramozva is kijön az eredmény:

kockadobások = 4 * [0]
győzelmek = 7 * [0]

def dob(kocka):
    if kocka < 4:
        for i in range(6):
            kockadobások[kocka] = i
            dob(kocka+1)
    else:
        első, második, harmadik, negyedik = kockadobások
        pontszámok = 7 * [0]
        pontszámok[első] += 1
        pontszámok[második if második < 5 else 6] += 1
        if harmadik >= 4:
            pontszámok[harmadik+1] += 1
        if len(kétpontosok := [i for i in range(7) if pontszámok[i] == 2]) > 0:
            győzelmek[kétpontosok[0]] += 1
        else:
            egypontosok = [i for i in range(7) if pontszámok[i] == 1]
            győzelmek[egypontosok[negyedik % len(egypontosok)]] += 1

dob(0)
print(győzelmek) # [192, 192, 192, 192, 192, 168, 168]

Egyszerűsítés

Egyszerűen belátható, hogy nem ugyanakkora a törpök esélye akkor, ha azt a módszert játsszák, hogy Tudor, Vidor, Morgó, Szundi, Szende és Hapci kap pontot az első fordulóban, Kuka a másodikban, ha hatost dob, és döntetlen esetén van egy harmadik dobás. Ha kuka tovább jut, akkor mindenképp lesz ellenfele, míg a másik hat törtpének 5/6 eséllyel nem.

Két fej egymás után

Egy szabályos érmével játszunk fej vagy írás játékot. Akkor állunk meg, ha kétszer egymás után fejet dobtunk. Mekkora a dobások várható száma?

+ Megoldás (kinyit)

Baktériumok

Van egy baktérium faj, melynek egyedei 25% eséllyel meghalnak, 75% eséllyel osztódnak. Kettő darab ilyen baktériummal indul a kolónia. Mekkora eséllyel halnak ki?

+ Megoldás (kinyit)

Kinder tojás

Tegyük fel, hogy a Kinder tojásban négyféle játék van, egyforma előfordulási valószínűséggel. Elhatározzuk, hogy egyesével vásárolunk addig, amíg mind a 4 ki nem gyűlik. Várhatóan hány Kinder tojást kell venni?

+ Megoldás (kinyit)

Kétfejű érme

Van tíz darab érménk: kilenc normális, egy kétfejű. Véletlenszerűen kiválasztunk egy érmét, dobunk vele háromszor, és mindhárom esetben fej az eredmény. Mekkora eséllyel választottuk a kétfejű érmét?

+ Megoldás (kinyit)

Párbaj

Hárman párbajoznak a következő formában. Sorban lőnek, nem egyszerre. $$A$$ lő $$B$$ -re, $$B$$ lő $$C$$ -re és $$C$$ lő $$A$$ -ra. Ha valaki eltalálja a másikat, akkor a kör folytatódik, tehát ha mondjuk $$A$$ eltalálja $$B$$ -t, akkor a következő lépésben $$C$$ lő $$A$$ -ra. Az $$A$$ és a $$C$$ találati esélye $50\%$ , a $$B$$ -é $75\%$ . A párbaj akkor ér véget, ha már csak egy valaki maradt talpon. $$A$$ kezd. Mekkora eséllyel nyeri $$A$$ a párbajt? $\DeclareMathOperator{\nyer}{nyer}\DeclareMathOperator{\kezd}{kezd}\DeclareMathOperator{\halott}{halott}\DeclareMathOperator{\mindenki}{mindenki}\DeclareMathOperator{\el}{\acute{e}l}$

+ Megoldás (kinyit)

- Megoldás (becsuk)

A következőképpen érdemes kiindulni. Írjuk fel $$A$$ kezdése esetén a két lehetőséget, talál vagy vét, majd fejtsük ki az egyes részeket:

$P(A \nyer | A \kezd\land \mindenki\el) = \frac{1}{2}\cdot P(A \nyer | C \kezd\land B \halott) + \frac{1}{2} \frac{1}{2}\cdot P(A \nyer | B \kezd\land \mindenki\el)$
$P(A \nyer | C \kezd\land B \halott) = \frac{1}{2}\cdot 0 + \frac{1}{2}\cdot P(A \nyer | A \kezd\land B \halott) = \frac{1}{2}\cdot (1 - P(A \nyer | C \kezd\land B \halott))$
$\frac{3}{2}\cdot P(A \nyer | C \kezd\land B \halott) = \frac{1}{2}$
$P(A \nyer | C \kezd\land B \halott) = \frac{1}{3}$

$P(A \nyer | B \kezd\land \mindenki\el) = \frac{3}{4}\cdot P(A \nyer | A \kezd\land C \halott) + \frac{1}{4}\cdot P(A \nyer | C \kezd\land \mindenki\el)$

$P(A \nyer | A \kezd\land C \halott) = \frac{1}{2}\cdot 1 + \frac{1}{2}\cdot P(A \nyer | B \kezd\land C \halott) = \frac{1}{2} + \frac{1}{2}\cdot(\frac{3}{4}\cdot 0 + \frac{1}{4}\cdot P(A \nyer | A \kezd\land C \halott))$
$\frac{7}{8}\cdot P(A \nyer | A \kezd\land C \halott) = \frac{1}{2}$
$P(A \nyer | A \kezd\land C \halott) = \frac{4}{7}$

$P(A \nyer | C \kezd\land \mindenki\el) = \frac{1}{2}\cdot 0 + \frac{1}{2}\cdot P(A \nyer | A \kezd\land \mindenki\el) = \frac{1}{2}\cdot P(A \nyer | A \kezd\land \mindenki\el)$

Elkezdve visszahelyettesíteni:
$P(A \nyer | B \kezd\land \mindenki\el) = \frac{3}{4}\cdot * \frac{4}{7} + \frac{1}{4}\cdot P(A \nyer | C \kezd\land \mindenki\el) = \frac{3}{7} + \frac{1}{4}\cdot\frac{1}{2}\cdot P(A \nyer | A \kezd\land \mindenki\el) = \frac{3}{7} + \frac{1}{8}\cdot P(A \nyer | A \kezd\land \mindenki\el)$

$P(A \nyer | A \kezd\land \mindenki\el) = \frac{1}{2}\cdot\frac{1}{3} + \frac{1}{2}\cdot P(A \nyer | B \kezd\land \mindenki\el) = \frac{1}{6} + \frac{1}{2}\cdot(\frac{3}{7} + \frac{1}{8}\cdot P(A \nyer | A \kezd\land \mindenki\el)) = \frac{1}{6} + \frac{3}{14} + \frac{1}{16}\cdot P(A \nyer | A \kezd\land \mindenki\el)$
$\frac{15}{16}\cdot P(A \nyer | A \kezd\land \mindenki\el) = \frac{1\cdot 7 + 3\cdot 3}{42}$
$P(A \nyer | A \kezd\land \mindenki\el) = \frac{16}{15}\cdot \frac{16}{42} = \frac{128}{315}$

Csakhogy ebben a megoldásban van egy bökkenő, amire szerintem a feladvány készítői nem számítottak! Ez inkább játékelméleti, mint közvetlenül matematikai feladattá alakítja a dolgot. Az $$A$$ az esélyeit növelheti azzal, ha először a levegőbe lő, és a kezdés jogát átadja $$B$$ -nek! Ez esetben $\frac{24}{49}$ eséllyel fog ő nyerni (a fentihez hasonló módon kiszámolva), azaz több mint 8 százalékponttal növelheti az esélyét.

De ebben is van egy további bökkenő! Valójában bármelyiknek érdemes először a levegőbe lőnie ahhoz, hogy maximalizálja saját túlélési esélyét, így viszont elvileg a végtelenségig fognak a levegőbe lövöldözni.

De tegyük fel, hogy nem mindenki olyan okos, mint $$A$$ ! Az $$A$$ szempontjából az a legrosszabb, ha $$B$$ is szándékosan a levegőbe lő, a $$C$$ viszont nem számol, hanem céloz. Ez esetben ha az $$A$$ és a $$B$$ tovább folytatja a taktikai pacifizmust, akkor az első lelőtt személy pont $$A$$ lesz. Azaz $$A$$ érdeke az, hogy lelője $$B$$ -t azzal, hogy $$0$$ fölé tornássza a túlélési esélyeit. Ha eltalálja, akkor a fenti $\frac{1}{3}$ esélye lesz a túlélésre, ha nem, akkor még kevesebb, mert a $$B$$ , látva, hogy $$A$$ és $$C$$ is céloz, továbbra is azt a taktikát érdemes alkalmaznia, hogy először a levegőbe lő. Kiszámolható, hogy ez esetben mindössze $\frac{2}{9}$ az $$A$$ túlélési esélye.

Ha $$C$$ rájön arra, hogy nem érdemes céloznia, de $$B$$ nem, az a legjobb $$A$$ -nak. Ez esetben az $$A$$ esélye elméletben $\frac{4}{7}$ , ugyanis - mivel csak $$B$$ céloz, ezért először $$C$$ fog meghalni, majd mivel $$A$$ kezdi a párbajt, $50\%$ -nál nagyobb esélye lesz a végső győzelemre.

Csakhogy mivel $$C$$ okos ebben a forgatókönyvben, nyilván arra is rájön, hogy ha csak $$B$$ céloz ténylegesen, akkor törvényszerű, hogy ő fog először meghalni, tehát - hasonlóan a fenti gondolatmenethez - érdemes neki is lőnie, hogy növelje a túlélési esélyeit. Tehát ebben a forgatókönyvben ott tartunk, hogy $$A$$ okos, és a levegőbe lő, $$B$$ buta, és céloz. $75\%$ eséllyel talál, és utána a párbajban $$A$$ -nak $\frac{4}{7}$ esélye van a győzelemre. $25\%$ eséllyel nem talál. Ez esetben ha feltesszük, hogy $$C$$ rájön arra, hogy $$A$$ nem célzott, $$B$$ viszont igen, akkor célozni fog, $50\%$ eséllyel talál, $50\%$ eséllyel pedig azt a játékot játsszák, hogy $$A$$ nem céloz, $$B$$ és $$C$$ viszont igen. Ebben a forgatókönyvben tehát visszatértünk az $$A$$ levegőbe lő mindaddig, amíg valaki meg nem hal taktikához, és így $$A$$ esélye $\frac{24}{49}$ .

Kockadobás

Egy szabályos hat oldalú dobókockával dobunk. Annyi tábla csokoládét kapunk, amennyi a dobás eredménye. Ha a dobás eredményével elégedetlenek vagyunk, akkor újra dobhatjuk a kockát, de legfeljebb háromszor dobhatunk összesen. Az újradobás kockázatos: ha kisebbet dobunk, akkor is a új dobás az érvényes.
Milyen stratégiával tudjuk maximalizálni a nyereséget, és hány tábla csoki a várható nyeremény?

+ Megoldás (kinyit)

Repülőgép

Van egy 440 férőhelyes repülőgép 440 utassal. Az elsőnek felszálló utas elveszítette a beszállókártyáját, és véletlenszerűen elfoglal egy ülőhelyet. A továbbiakban ha az éppen felszálló utasnak még szabad az ülőhelye, akkor oda ül, egyébként ő is választ véletlenszerűen egy még szabadon levő ülőhelyet.
Az utolsónak felszálló utas mekkora eséllyel találja szabadon a saját ülőhelyét?

+ Megoldás (kinyit)

Dzsinn

Találunk egy csodalámpát, megdörgöljük, megjelenik a dzsinn, mond egy 0 és 100 közötti egyenletes eloszlású véletlen számot, és felkínálja, hogy ad annyi kuvaiti dinárt, amennyi a mondott szám. Egészen pontosan két döntési lehetőséget kínál számunkra:

Elfogadjuk a pénzt. Ez esetben a dzsinn csodalámpástul örökre eltűnik.
Nem fogadjuk el a pénzt. Ez esetben egy évre eltűnik, majd utána ismét megjelenik, és felkínálja ugyanezt, természetesen egy másik 0 és 100 közötti véletlen számmal.

Nincs maximálva az újbóli ajánlatok száma, tetszőlegesen játszhatjuk ezt akármeddig. Mi nyilván maximalizálni szeretnénk a nyereséget: nem kis pénzről van szó (100 kuvaiti dinár jelen árfolyamon közel százezer forintot ér). Ugyanakkor a mai pénz számunkra értékesebb, mint a jövőbeli, hiszen ki tudja, mit hoz a holnap. Tegyük fel, hogy van egy belső 90%-os szorzónk: 100 dinár egy év múlva számunkra annyit ér, mint ma 90; 100 dinár két év múlva annyit ér, mint ma 81 stb. Kicsit formálisabban fogalmazva: a két év múlva megkapott 100 dinár jelenértéke számunkra 81 dinár.

Gondolkodunk az ajánlaton. Elsőként a következő stratégiák jutnak eszünkbe:

Bármit mond, azt elfogadjuk: a várható nyereségünk ez esetben 50 dinár lesz.
Most 50 dinár felett elfogadjuk az ajánlatot, jövőre pedig bármit mond, elfogadjuk: a nyereségünk várható jelenértéke $0,5\cdot 75 + 0,5\cdot 0,9\cdot 50 = 60$ dinár.

A legjobb stratégiánk szerint mennyi a nyereség várható jelenértéke? Milyen stratégiával tudjuk ezt elérni? Pl. most azonnal hány dinár felett érdemes elfogadnunk a dzsinn ajánlatát? Jövőre? Két év múlva?

+ Megoldás (kinyit)

- Megoldás (becsuk)

Először is vegyük észre, hogy minden évben ugyanattól az értéktől érdemes elfogadnunk a pénzt, hiszen nominálisan 0 és 100 közötti az ígéret. Pl. ha a mostanit visszautasítjuk, akkor jövőre is igaz az, hogy az egy évvel későbbi 100 dinár akkor számunkra egyenértékű a pillanatnyi 90-nel.
Jelöljük $$N$$ -nel azt, az értéket, ami felett érdemes elfogadnunk az ajánlatot, de ez alatt nem. Ha pl. ez 60, akkor 40%, hogy elfogadjuk, és ez esetben a várható nyereségünk 80, 60% eséllyel pedig visszautasítjuk, és ez esetben a várható nyereség jelen összeg 90%-a. A várható értéket általában így jelöljük: $$E[X]$$ , ahol $$X$$ a szóban forgó valószínűségi változó. Mivel itt egy valószínűségi változó van, a várható nyereségünk jelenértéke, ezért az egyszerűség érdekében a várható nyereség jelölése legyen $$E$$ . Összefoglalva a jelöléseket:

$$N$$ : ettől az összegtől kezdve érdemes elfogadnunk a pénzt, azaz a feladat második kérdésére a válasz.
$$E$$ : ez a várható nyereség jelenértéke, azaz a feladat első kérdésére a válasz.

A fentieket formálisan felírva:
$E = \frac{100-N}{100}\cdot\frac{N+100}{2} + \frac{N}{100}\cdot 0,9\cdot E$

Átrendezve:

$E - \frac{E\cdot 0,9\cdot N}{100} = \frac{10000-N^2}{200}$
$E\cdot\frac{100 - 0,9N}{100} = \frac{10000-N^2}{200}$
$E = \frac{10000 - N^2}{200}\cdot\frac{100}{100 - 0,9N}$
$E = \frac{10000 - N^2}{200 - 1,8N}$

Ezt szeretnénk maximalizálni. Egy függvénynek ott van maximum pontja, ahol a deriváltja 0. Tehát:
$\left(\frac{10000 - N^2}{200 - 1,8N}\right)' = 0$

Számoljuk ki a deriváltat! Az alábbi összefüggést kell használnunk:
$\left(\frac{f}{g}\right)' = \frac{f'g - fg'}{g^2}$

Tehát:
$\left(\frac{10000 - N^2}{200 - 1,8N}\right)'$
$= \frac{(10000 - N^2)'\cdot (200 - 1,8N) - (10000 - N^2) \cdot (200 - 1,8N)'}{(200 - 1,8N)^2}$
$= \frac{-2N \cdot (200 - 1,8N) - (10000 - N^2) \cdot (-1,8)}{40000 - 360N + 3,24N^2}$
$= \frac{-400N + 3,6N^2 + 18000 - 1,8N^2}{3,24N^2 - 360N + 40000}$
$= \frac{1,8N^2 - 400N + 18000}{3,24N^2 - 360N + 40000}$

Azaz:
$\frac{1,8N^2 - 400N + 18000}{3,24N^2 - 360N + 40000} = 0$

A $$3,24N^2 - 360N + 40000$$ remélhetőleg nem 0, így:
$$1,8N^2 - 400N + 18000 = 0$$

Emlékeztetőül a másodfokú egyenlet megoldóképlete:
$x_{1,2} = \frac{-b\pm\sqrt{b^2 - 4\cdot a\cdot c}}{2\cdot a}$

Ezt alkalmazva:
$N_{1,2} = \frac{400\pm\sqrt{400^2 - 4\cdot 1,8\cdot 18000}}{2\cdot 1,8}$
$= \frac{400\pm\sqrt{160000 - 129600}}{3,6}$
$= \frac{400\pm\sqrt{30400}}{3,6}$
$\approx \frac{400\pm 174,36}{3,6}$

Azt az eredményt kell venni, ami 0 és 100 közé esik, tehát jelen esetben a kivonást:
$N \approx 62,68$

Visszahelyettesítve a várható érték képletébe:
$E = \frac{10000 - N^2}{200 - 1,8N} \approx \frac{10000 - 62,68^2}{200 - 1,8\cdot 62,68} \approx 69,64$

Összefoglalva: 62,68-tól érdemes elfogadni az ajánlatot (egész összegekben gondolkodva: a 62-t még nem érdemes, a 63-at már igen), és ez esetben a várató nyereség jelenértéke 69,64 dinár.

Interjú

Egy titkárnői álláshirdetésre hárman jelentkeznek. Közöttük egyértelmű a sorrend, hogy ki lenne a legjobb titkárnő, és ez már az interjún kiderül. A főnök egyszerre egy valakit hallgat meg. Viszont ez az interjúzási folyamat teljesen speciális, a főnöknek ugyanis azonnal döntenie kell, hogy az éppen interjúztatott jelöltet felveszi-e vagy sem. (Mindhárom jelölt, ha ajánlatot kap, automatikusan elfogadja.) Tehát pl. ha a főnök az első jelöltet visszautasítja, akkor a második jelölt meghallgatása után (amikor egyértelmű, hogy melyik a jobb) nem hívhatja vissza az elsőt, hogy mégis őt venné fel. Ha a második jelölt meghallgatása után ajánlatot ad neki, akkor a harmadik jelölt meghallgatására nem kerül sor (bár lehet, hogy ő lenne a legalkalmasabb).
A főnöknek milyen interjúzási stratégiát kell alkalmaznia ahhoz, hogy maximalizálja annak esélyét, hogy a legjobb jelöltet válassza? Mekkora ez az esély?

+ Megoldás (kinyit)

Metrók

Adott állomásról két metró közlekedik számunkra kedvező irányba, az egyik 3, a másik 5 percenként, egymástól függetlenül. Lemegyünk az állomásra egy véletlen időpontban, és arra a metróra szállunk fel, amelyik előbb jön. Várhatóan mennyit kell várnunk?

+ Megoldás (kinyit)

- Megoldás (becsuk)

Ez a feladat amiatt tetszik nekem, mert egyszerűsége ellenére valójában rendkívül bonyolult. A megoldásnak igazán jó, közérthető levezetésével nem találkoztam. Az alábbi oldalakt találtam:

Itt igyekszem úgy elmagyarázni, hogy lehetőleg ne maradjon ki egyetlen lépés sem. Fokozatosan haladunk a megoldás felé.

Egy metró 3 perces követési idővel

Ha összesen egy metró van, 3 perces követési távolsággal, akkor a várható várakozási idő másfél perc. De miért is?

Elméleti kitérő

A feladat megoldása szempontjából meg kell értenünk néhány valószínűségszámítási alapfogalmat és módszert.

A valószínűségi változókat két fő csoportba oszthatjuk: diszkrét és folytonos. Diszkrét pl. a kockadobás, folytonos pl. az, hogy mennyit várunk a metróra. A diszkrét valószínűségi változókkal valójában egyszerűbb bánni, ebben a feladatban viszont meg kell ismerkednünk mélyebben a folytonossal.

Talán a legkönnyebb megérteni azokat a diszkrét eseteket, ahol a lehetséges kimenetek száma véges. Pl. egy kockadobás esetén 6 lehetséges eredmény van, ugyanakkora, egyenként $\frac{1}{6}$ eséllyel. Az eredeti feladathoz nagyon hasonló lenne az, hogy dobunk egyet egy hatoldalú és egy négyoldalú dobókockával és felírjuk a kisebbet. Mi ennek a várható értéke? Most nem oldjuk meg, de a megoldás adja magát: összesen 24 féle lehetséges eredmény van ugyanakkora valószínűséggel; felírjuk mindet, és a kisebbik számokat átlagoljuk.

Csakhogy folytonos esetben annak a valószínűsége, hogy a valószínűségi változó egy adott értéket vegyen fel, nulla. Itt intervallumoknak van értelmük, pl. annak, hogy mekkora eséllyel kell legalább 20 és legfeljebb 30 másodpercet várni. Csakhogy ha a valószínűség nem lineáris (az egy metróra történő várakozás lineáris, de a kettőre való várakozás már nem az), akkor csak közelíteni tudjuk ezzel a módszerrel. Lehet a 10 másodperces intervallumot 1-re vagy akár egytizedre venni, és azokat átlagolni; a számolás hosszadalmas lesz, de tökéletesen pontos eredményt így sem kapunk.

Folytonos esetben - ellentétben a diszkrét esettel - nem egy adott lehetséges érték bekövetkezési valószínűségét vesszük alapul, hanem azt, hogy mekkora az esélye annak, hogy az eredmény egy adott értéknél kisebb. Például mekkora eséllyel kell kevesebbet várni, mint egy perc. A 3 perces követési idejű metró esetben ennek a valószínűsége $\frac{1}{3}$ , az 5 perces követési idejűé pedig $\frac{1}{5}$ . A kettő együtt már trükkösebb: valójában úgy érdemes kiszámolni, hogy külön-külön meghatározzuk azt, hogy mekkora eséllyel kell legalább 1 percet várni, azt összeszorozzuk (hiszen a két esemény független), majd egyből kivonjuk az eredményt: $1 - \frac{2}{3}\cdot\frac{5}{6} = \frac{4}{9}$ , tehát valamivel kevesebb mint 50% az esélye annak, hogy egy percen belül metróra tudunk szállni. (Ez már kijelöli a megoldás közelítő értékét.)

Persze ezt a módszert diszkrét esetben is alkalmazhatjuk, és ott már van jelentősége annak, hogy szigorú egyenlőtlenséget követelünk meg. Tehát pl. annak a valószínűsége, hogy egy szabályos 6 oldalú kockával 3-nál kisebbet dobunk, $\frac{1}{3}$ .

Lássuk most, hogy hogyan jelöljük az említett fogalmakat!

A valószínűségi változót tipikusan nagybetűvel jelöljük, az ábécé végéről, pl. $$X$$ , $$Y$$ . Diszkrét esetben ez pl. a kockadobás, folytonos esetben pl. a metró érkezéséig eltelt idő.
A valószínűségi változó által felvehető lehetséges értékeket a fenti betű kisbetűs változatával jelöljük, pl. $$x$$ , $$y$$ . Pl. kockadobás esetén ezek az 1, 2, 3, 4, 5 és 6 értékeket jelentik, a metróra való várakozás esetén pedig egy 0 és 3 közötti tetszőleges érték. Valójában itt általánosíthatunk (mindkét esetben) úgy, hogy az x értéke mínusz végtelentől plusz végtelenig terjedhet, mert végül is van annak a kérdésnek értelme, hogy mekkora eséllyel dobunk 10-nél kisebbet a dobókockával, vagy mennyi eséllyel várunk legfeljebb 10 percet (100%), vagy fordítva, mekkora eséllyel dobunk -2-nél kevesebbet, ill. mekkora eséllyel szállunk fel a metróra azelőtt, hogy odaérnénk (0%).
A valószínűség jelölése $$P$$ , és itt zárójelben adjuk meg azt, hogy mire vonatkozik. Pl. diszkrét esetben jelölje $$A$$ azt az eseményt, hogy páros számú lesz a dobás eredménye, akkor $$P(A) = 0.5$$ . Folytonos esetben a metróra történő várakozást formálisan felírva ezt kapjuk $P(x<1) = \frac{1}{3}$ .
Ha felírjuk minden x-re, mínusz végtelentől plusz végtelenig azt, hogy mekkora eséllyel lesz az eredmény kisebb az adott értéknél, akkor az adott valószínűségi változó eloszlásfüggvényét kapjuk eredményül. Ennek a jelölése $F$, ill. mivel függvényről van szó, zárójelben az értelmezési tartományt adjuk meg: $F(x)$. Néhány fontos tulajdonsága:
- Mínusz végtelenben az értéke 0.
- Plusz végtelenben az értéke 1.
- Nem csökkenő.

Abban a példában, amelyben egy metró van, a várakozás egyenletes, tehát ugyanakkora eséllyel kell a szerelvényre várni legalább 20, legfeljebb 30 másodpercet, mint amekkora eséllyel kell legalább 130, legfeljebb 140 másodpercet. Ez nem mindegyik folytonos valószínűségi változó esetén van így, pl. az alapfeladatban sincs így, és ez adja a nehézségét. Valahogyan jó lenne kifejezni azt is, hogy adott érték "körül" kb. mekkora ez a valószínűség. Azt, hogy milyen értékek mentén kisebb ill. nagyobb a valószínűségi változó értéke, sűrűségfüggvénynek nevezzük, és $$f$$ -fel, egészen pontosan $$f(x)$$ -szel jelöljük. A sűrűségfüggvénynek a következő fontos tulajdonságai vannak:

Nem lehet negatív.
A görbe alatti terület értéke pontosan 1.

Ez utóbbi formálisan kifejezve:

$\int_{-\infty}^{\infty}f(x)dx = 1$

Összefüggés az eloszlásfüggvény és sűrűségfüggvény között; az eloszlásfüggvény a sűrűségfüggvény integrálásából adódik:

$F(x) = \int_{-\infty}^{x}f(t)dt$

A sűrűségfüggvény pedig az eloszlásfüggvény deriváltja:

$$f(x) = F'(x)$$

Próbáljuk meg most "kitalálni" az egy metrós feladat eloszlásfüggvényét és sűrűségfüggvényét! Az eloszlás egyenletesen növekszik úgy, hogy 0 percnél 0, 3 percnél 1, azaz $\frac{x}{3}$ , ha $0 \le x \le 3$ , $$0$$ ha $$x < 0$$ és 1, ha $$x > 3$$ .

A sűrűségfüggvény már trükkösebb. 0 alatt és 3 fölött nem lehet, azaz ott 0 lesz, a kettő között pedig egyenletes. Tudva azt, hogy a görbe alatti terület 1, a görbe egy téglalapot ír le, melynek szélessége 3 egység, így ahhoz, hogy kijöjjön területre az 1, a téglalap magassága $\frac{1}{3}$ . A sűrűségfüggvény tehát $\frac{1}{3}$ , ha $0 \le x \le 3$ , $$0$$ ha $$x < 0$$ és ugyancsak 0, ha $$x > 3$$ .

Ez persze az eloszlásfüggvény deriválásával is gyakorlatilag közvetlenül adódik, mivel $\frac{1}{3}\cdot x$ deriváltja $\frac{1}{3}$ .

A várható érték adja általában a feladatok végeredményét. Ennek szokásos jelölése $$E[X]$$ . Itt is induljunk ki először a diszkrét esetből! Mekkora a kockadobás várható értéke? Nyilván 3,5, ami úgy adódik, hogy összeadjuk a lehetséges dobásokat, majd elosztjuk 6-tal, mert mindegyiknek $\frac{1}{6}$ a valószínűsége. Valami hasonló kellene folytonos esetben is, csakhogy ott nem tudjuk venni az összes lehetséges értéket, megszorozni annak valószínűségével és összeadni, ahogy tennénk diszkrét esetben, hanem - sajnos - itt is integrálnunk kell.

$E[X] = \int_{-\infty}^{\infty}x\cdot f(x)dx$

Általában a folytonos valószínűségszámítási feladatokban a legegyszerűbb az eloszlásfüggvényt felírni (ezt a feladatot is így fogjuk megoldani), így azt felhasználva $$dF(x)$$ -szel jelölve az $$F(x)$$ deriváltját, adódik a következő képlet (amit a leírások többnyire levezetés nélkül adnak meg):

$E[X] = \int_{-\infty}^{\infty}x\cdot dF(x)dx$

Két metró, egyenként 3 perces követési idővel

Közelítés a megoldás felé

Talán ez az a legegyszerűbb eset, amin jól láthatjuk, hogy a feladat mennyire nem egyszerű, aminek az oka az "egymástól függetlenül" kitétel. Számunkra az a legkedvezőbb, ha egymástól pontosan másfél perc elcsúsztatással indulnak, és a legkedvezőtlenebb, ha ugyanakkor. (Ha ez nem nyilvánvaló, akkor gondoljunk arra, hogy ha egy faluból naponta összesen két buszjárat van, akkor mi a jobb, ha mindkettő reggel 8-kor indul, agy az egyik reggel 8-kor, a másik este 8-kor.) Az előbbi eset gyakorlatilag felfogható úgy, hogy van egy metrójárat másfél perc követési idővel (nagyjából így működik a budapesti 4-es és 6-os villamos), míg ez utóbbi felfogható kétszeres kapacitású metrójáratként, 3 perces követési idővel. De vannak köztes esetek is, pl. az, hogy a két járat között fél perc eltérés van, vagy hogy egy perc, és valójában végtelen sok ilyen lehetőség létezik.

De vajon mennyi lehet a várakozási idő ez esetben? A problémát a végtelen sok lehetőség okozza. Próbáljuk először megsaccolni! Először tegyük fel, hogy a metró indulási ideje csak 30 másodpercre kerekített lehet! Ez esetben ha az első metró a 0, 180, 360 stb. másodpercben indul, akkor a második az alábbi eltolásokban indulhat, egyenlő valószínűségekkel:

0 másodperc: ez esetben olyan, mintha csak egy lenne, és a várható érték - mint fent láthattuk - 75 másodperc.
30 másodperc: ez esetben $\frac{1}{6}$ eséllyel futunk bele abba, hogy 30 másodpercen belül jön a következő metró, azaz 15 másodperc a várható várakozási idő, $\frac{5}{6}$ eséllyel pedig abba, hogy 150 másodpercen belül érkezik, azaz ez esetben a várható várakozási idő 75 másodperc. Összesen: $\frac{1}{6}\cdot 15 + \frac{5}{6}\cdot 75 = \frac{15 + 375}{6} = \frac{390}{6} = 65$ , tehát a várható várakozási idő 65 másodperc.
60 másodperc: a fentihez hasonlóan, $\frac{1}{3}$ eséllyel lesz a várakozási idő átlagosan 30 másodperc és $\frac{2}{3}$ eséllyel 60 másodperc, ami összesen $\frac{1}{3}\cdot 30 + \frac{2}{3}\cdot 60 = 50$ , tehát 50 másodpercet eredményez.
90 másodperc: ez ekvivalens azzal, mintha egy járat lenne másfél perces követési idővel, azaz 45 másodperc ez esetben a várható várakozási idő.
120 másodperc: ez a 60 másodperc fordítottja, ugyancsak 50 másodperc várható várakozási idővel.
150 másodperc: ez a 30 másodperc fordítottja, szintén 65 másodperc várható várakozási idővel.

A 180 másodperctől ismétlődik. A fenti 6 eset valószínűsége a feltevésünk szerint egyforma, így adódik a teljes várható várakozási idő:

$\frac{1}{6}\cdot 75 + \frac{1}{6}\cdot 65 + \frac{1}{6}\cdot 50 + \frac{1}{6}\cdot 45 + \frac{1}{6}\cdot 50 + \frac{1}{6}\cdot 65 = 58\frac{1}{3}$

Az eredmény tehát közel 1 perc. Valójában minél jobban "finomítjuk" a beosztást (pl. 10 másodperc többszörösével kiszámoljuk, vagy akár minden másodpercre), annál jobban közelítjük az 1 percet. Talán már "érezzük" azt, hogy az eredmény kerek egy perc lesz, de vajon hogyan jön ez ki?

Pontos megoldás integrállal

Eloszlásfüggvény

Először írjuk fel az eloszlásfüggvényt! Azt kell megadnunk, hogy mekkora eséllyel lesz kisebb egy adott értéknél a valószínűségi változó, jelen esetben az, hogy ha két metró jár egymástól függetlenül, egyenként 3-3 perces menetidővel, akkor mekkora eséllyel kell kevesebbet várni adott értéknél. 0 alatti értékekre nyilván ez 0%, 3 feletti értékekre pedig 100%, de mennyi mondjuk 20 másodpercre, egy percre vagy 2,5 percre?

Már ez sem egyszerű! Ezt úgy érdemes megoldani, hogy kiszámoljuk, mekkora eséllyel kell legalább adott ideig várni. Korábban már láthattuk, hogy ezt úgy tudjuk kiszámolni, hogy külön-külön vesszük a két metróra várás várható értékét, és összeszorozzuk. Végül - mivel pont az ellenkezőjét keressük - kivonjuk 1-ből.

Az $$X$$ valószínűségi változó most a két egymástól független, egyenként 3 perces menetidejű metróra történő várakozást jelenti, $$X_1$$ az egyikre, $$X_2$$ pedig a másikra történő várakozást külön-külön. A fenti gondolatmenetet formalizálva:

$F(x) = P(X < x) = 1 - P(X\ge x) = 1 - P(X_1\ge x)\cdot P(X_2\ge x) = 1 - (1 - P(X_1 < x))\cdot (1 - P(X_2 < x)) = 1 - (1 - \frac{x}{3})\cdot(1 - \frac{x}{3}) = 1 - \frac{3 - x}{3}\cdot\frac{3 - x}{3} = 1 - \frac{9 - 6x + x^2}{9} = \frac{6x - x^2}{9}$

Tehát:

$F(x) = \frac{6x - x^2}{9}$

Mindez persze úgy, hogy $0 \le x \le 3$ .

Sűrűségfüggvény

A sűrűségfüggvény az eloszlásfüggvény deriváltja, tehát:

$f(x) = F'(x) = \left(\frac{6x - x^2}{9}\right)' = \frac{1}{9}\cdot(6x - x^2)' = \frac{1}{9}\cdot(6 - 2x) = \frac{6 - 2x}{9}$

Tehát:

$f(x) = \frac{6 - 2x}{9}$

Továbbra is $0 \le x \le 3$ ; más esetben $$f(x) = 0$$ .

Várható érték

A várható érték kiszámítása:

$E[X] = \int_{-\infty}^{\infty}x\cdot f(x)dx = \int_{0}^{3}x\cdot \frac{6 - 2x}{9} dx$

Az $$f(x)$$ függvényértéke $$x < 0$$ és $$x > 3$$ esetén konstans 0, így a határozott integrál ottani része is 0 lesz, emiatt elég csak 0 és 3 között integrálni.

Számoljuk ki az integrál primitív függvényét:

$\int x\cdot\frac{6 - 2x}{9}dx = \int\frac{6x - 2x^2}{9} = \frac{6\cdot\frac{x^2}{2} - 2\cdot\frac{x^3}{3}}{15} = \frac{3x^2 - \frac{2}{3}x^3}{9}$

Az eredeti képletbe visszahelyettesítve és alkalmazva a Newton-Leibniz formulát:

$\int_{0}^{3}x\cdot \frac{6 - 2x}{9}dx = \left[\frac{3x^2 - \frac{2}{3}x^3}{9}\right]^3_0 = \left(\frac{3\cdot 3^2 - \frac{2}{3}\cdot 3^3}{9}\right) - \left(\frac{3\cdot 0^2 - \frac{2}{3}\cdot 0^3}{9}\right) = \frac{27 - 18}{9} - 0 = 1$

Tehát:

$$E[X] = 1$$

Ez a megoldás: ha van két 3 perc menetidejű, egymástól független metró, akkor várhatóan egy percet kell a gyorsabbra várni.

Az eredeti feladat visszavezetése az előzőre

Az eredeti feladatot a következőképpen tudjuk visszavezetni az imént megoldottra. Induljunk ki abból, hogy tetszőleges pillanatban odaérve mekkora az esélye annak, hogy at 5 perc menetidejű metró 3 percen belül ill. 3 percen túl érkezik:

$\frac{3}{5}$ eséllyel érkezik 3 percen belül. Ez esetben visszavezettük a problémát az előzőre, azaz ez esetben 1 perc lesz a várható várakozási idő.
$\frac{2}{5}$ eséllyel érkezik 3 percen túl. Ez ekvivalens azzal az esettel, hogy csak egy metró van, 3 perces követési idővel, és ez esetben másfél perc a várható várakozási idő.

Összegezve (ez esetben $$X$$ az eredeti feladat valószínűségi változója, $$E[X]$$ pedig annak várható értéke):

$\frac{3}{5}\cdot 1 + \frac{2}{5}\cdot 1,5 = \frac{6}{5}$

A feladatnak tehát a megoldása $\frac{6}{5}$ perc, azaz 1 perc 12 másodperc.

Az eredeti feladat közvetlen megoldása

Ennyi bevezetéssel most már közvetlenül is megoldhatjuk! Jelölje $$X$$ az eredeti feladat valószínűségi változóját, $$X_1$$ a 3 perc követési idejű metróra történő várakozás időtartamát, $$X_2$$ pedig az 5 percesét. A fenti gondolatmenettel az eloszlásfüggvény:

$F(x) = 1 - \frac{3 - x}{3}\cdot\frac{5 - x}{5} = 1 - \frac{15 - 8x + x^2}{15} = \frac{8x - x^2}{15}$

Természetesen itt is $0 \le x \le 3$ , ugyanis semmiképpen sem kell többet várni 3 percnél. A sűrűségfüggvény:

$f(x) = \left(\frac{8x - x^2}{15}\right)' = \frac{8 - 2x}{15}$

A várható érték:

$E[X] = \int_{0}^{3}x\cdot \frac{8 - 2x}{15}dx = \int_{0}^{3}\frac{8x - 2x^2}{15}dx = \left[\frac{4x^2 - \frac{2}{3}\cdot x^3}{15}\right]^3_0 = \frac{36 - 18}{15} = \frac{6}{5}$

A feladat megoldása tehát $\frac{6}{5}$ perc.

Megjegyzés: figyeljük meg, hogy az elején belinkelt megoldások nagyjából ennyire részletesek, a fenti magyarázat nélkül.

A különböző fogalmak magyarázata diagramokkal

Idáig túl sok volt a szöveg, és talán sokak nehezen tudják követni a fogalmakat, képleteket. Az eredeti feladat megoldása már kellően általános ahhoz, hogy érdemes legyen diagramokkal is illusztrálni.

Lássuk először az eloszlásfüggvényt!

Ez a fenti definíció alapján azt jelenti, hogy mekkora eséllyel lesz a várakozás kevesebb egy adott $$x$$ értéknél. A diagramból kiolvashatjuk, hogy kb. 30% esélyünk van arra, hogy fél percen belül érkezzen az előbb odaérő szerelvény, és közel 90% arra, hogy 2 percen belül megérkezzen.

A sűrűségfüggvény az alábbi:

Ennek az értelmezése már kicsit nehezebb. Diszkrét esetben kb. azt jelentené, hogy egy-egy értéknek mekkora az esélye. Folytonos esetben ilyen közvetlen értelmezést nehéz adni. Függvény alatti terület 1. Minél kisebb egy adott érték, annál kisebb annak az esélye, hogy az érték közelében következik be az esemény. A diagramból azt olvassuk le hogy a rövidebb várakozási idők valószínűbbek, mint a hosszabbak, és a várható várakozási idő lineárisan csökken. Egy ehhez hasonló diagramok kapnál egyébként akkor, ha intervallumokra osztanánk, pl. max. 10 másodperc várakozási idő, 10-20 másodperc közötti várakozási idő stb., és nagyon sok embert megkérdeznénk, hogy pontosan mennyit várt, ezeknek vennénk az arányát, finomítanánk (pl. 10 másodperces intervallum helyett egy másodpercet vennénk stb.), és a végén úgy rajzolnánk meg a függvényt, hogy az az alatti terület egység legyen.

A várható érték az alábbi függvény alatti terület:

Az értelmezéséhez vegyük ismét a finomodó diszkrét esetet. Ez olyan, mintha a fenti intervallumos példát folytatva felírnánk azt, hogy a pontosan adott ideig váró utasok összesen mennyit vártak (majd azt valahogy normalizáljuk). A sűrűségfüggvény alapján a kis értékek ugyan gyakran fordulnak elő, viszont ott a várakozás mennyiség is kicsi. A nagy értékek viszont ritkán fordulnak elő, így a függvény értéke emiatt alacsony ott. A függvény maximum pontja másfél percnél van, aminek a magyarázata az, hogy még elég valószínű és már elég nagy értéket jelent. A feladat megoldása a függvény alatti terület.

A fenti függvény primitív függvénye az alábbi:

Ennek a függvénynek a deriváltja az előző. Az ábrázolt két végpont a lényeges a mi szempontunkból, melyek különbsége adja a végeredményt.

Megoldás integrálás, deriválás és valószínűségszámítás nélkül?

Hosszasan gondolkodtam, hogy vajon meg lehet-e ezt oldani felső szintű matematika nélkül, de egyelőre nem sikerült ilyen megoldást találnom. A legnagyobb esélyét annak látom, hogy valahogy be tudjuk bizonyítani, hogy két, egyenként 3 perc követési idejű metró esetén a várható várakozási idő 1 perc, de még nem sikerült ezt megoldanom. Ha valakinek van ötlete, kérem, írja meg!

Tojások leejtése

Van két tökéletesen egyforma tojás, amely bizonyos magasságú emeletről leejtve összetörik, ha viszont annál alacsonyabb emeletről ejtünk le, akárhányszor is próbálkozunk, nem törik szét. Van egy 100 emelet magas épületünk. Minimálisan hány dobásra van szükségünk ahhoz, hogy megállapítsuk, melyik az a legmagasabb emelet, melyről leejtve még nem törik össze?

+ Megoldás (kinyit)

- Megoldás (becsuk)

Ez egy nagyon jó interjú kérdés, ugyanis - aki nem ismeri - a legritkább esetben vágja rá a helyes megoldást, és pont emiatt jól megfigyelhető, hogy hogyan jut el a jelölt a megoldásig, ill. mennyire hajlandó figyelembe venni az esetleges segítségeket, mit tesz, ha elakad stb.

A megoldásig vezető út tipikusan a következő lehet. Arra elég gyorsan rájövünk, hogy alapvetően alulról felfelé kell végrehajtani a kísérletet, hogy spóroljunk a tojásokkal. Egy tojás esetén egyesével kell leejteni először az elsőről, majd a másodikról, és így tovább, amíg össze nem törik, és ez esetben legfeljebb 100 lépésre van szükség.

Két tojás esetén, tízes számrendszerben gondolkodva, az előző ötletet tovább fejlesztve, elég gyorsan eljutunk addig a lehetőségig, hogy az egyik tojással megállapítjuk a tízes értéket (leejtve a 10., 20. 30. stb. emeletről; 10 lépés), majd ha az meg van (legyen mondjuk 50 az, ahonnan leejtve még nem tört össze, a 60. pedig az, amelyről leejtve összetört az első tojás), akkor az adott tízesen belül sorban ejtjük le (pl. 51., 52., 53. emelet stb.), amíg el nem törik. Ez utóbbi is max 9 lépést jelent, így legfeljebb 19 lépésből már végre tudjuk hajtani.

De vajon létezik-e ennél jobb megoldás? A fenti legrosszabb eset, csak egy esetben jön ki, a legtöbb esetben ennél kisebb, akár jóval kisebb a dobásszám. Pl. ha a megoldás mondjuk 22, akkor elég csak 6 dobás. Átlagban tehát jóval kisebb lesz a dobások száma, mint a legrosszabb eset. Minthogy a legrosszabb esetre optimalizálunk, nincs olyan megoldás, ami rontja a kisebb dobásszámú értékeket, de javítja a nagyobbakat, csökkentve a legnagyobbat? Egy ötlet a javításra: először ne a 10., hanem a 11. emeletről ejtsük. Ha törik, akkor még 10, azaz összesen 11 ejtésre van szükségünk. Az utolsó ejtés így a 91. emeletről történik, és ha utána számolunk, a legrosszabb esetet 18-ról 17-re csökkentettük.

Meddig tudunk lemenni? Adódik a következő ötlet: ejtsük le valamelyik emeletről, adjunk hozzá eggyel kisebbet, utána még eggyel kisebbet stb. Ha pl. a megoldás 15 lenne, akkor leejtjük a 15. emeletről, utána a 29-ről (15+14), majd a 42-ről (15+14+13), és így tovább, és utána még szükség van max. 14, 13, 12 stb. lépésre, azaz mindegyik esetben max. 15-re. De vajon a 15 jó megoldás-e? elvileg igen, ugyanis a $$15 + 14 + 13 + ... + 2 + 1 = 120$$ , azaz ezzel a módszerrel 15 lépésben 120 emeletről is meg tudnánk állapítani. Ennyi valójában nem kell. Nézzünk még egy lehetőséget, pl. 13: itt $$13 + 12 + 11 + ... + 2 + 1 = 91$$ ; igaz, hogy csak 13 lépés kell, de max. 91 emeletről tudjuk megállapítani, nekünk viszont 100 kell. Nézzük a 14-et: $$14 + 13 + 12 + ... + 2 + 1 = 105$$ , tehát elértük a 100-at, és valójában ez a megoldás.

Viszont meg tudjuk-e oldali próbálgatás nélkül? Legyen a megoldás $$x$$ ! A kérdés az, hogy mi az a minimális egész $$x$$ érték, melyre az $x + (x-1) + (x-2) + ... + 2 + 1 \ge 100$ . Egyszerűsítve: $\frac{x \cdot (x-1)}{2} \ge 100$ . A megoldás 14. Ezzel a képlettel tetszőleges emeletszámra meg tudjuk oldani.

Lányok életkora

Kovácsnak van három lánya. Szabó, a barátja, szeretné tudni a lányok életkorát. A következő párbeszéd zajlik:
- Az életkoruk szorzata 72.
- Ebből még nem tudom megmondani.
- Az életkoruk összege megegyezik a házszámommal.
Szabó kimegy, megnézi a házszámot, majd ezt mondja:
- Még mindig nem tudom megmondani.
- A legidősebb szereti a vaníliafagyit.
- Most már tudom!

Hogy lehet, hogy a vaníliafagyiból tudta meg Szabó, hogy hány évesek Kovács lányai?

+ Megoldás (kinyit)

Melyik a nagyobb?

Melyik a nagyobb: $e^\pi$ vagy $\pi^e$ ? A feladathoz számológépet nem használhatunk, a Négyjegyű függvénytáblázatot viszont igen!

+ Megoldás (kinyit)

Melyik a nagyobb: $999999999^{1000000000}$ vagy $1000000000^{999999999}$ ?

+ Megoldás (kinyit)

i-nek az i-edik hatványa

Mennyi $$i^i$$ ?

+ Megoldás (kinyit)

Időjárás

Egy nap 40% eséllyel napos, 40% eséllyel felhős és 20% eséllyel esős. Az egyes napok időjárásai függetlenek a korábbiaktól. Sorozatnak hívjuk azt, ha egymás utáni napokon ugyanolyan az időjárás. Például a 2 napos, 3 felhős, 1 esős, majd 4 napos időszakban 4 sorozat található. Mekkora a sorozat hossznak várható értéke 10 nap alatt?

+ Megoldás (kinyit)

Kosárlabda

Valaki nagyon szeretne bekerülni egy kosárlabda csapatba. Az edző azt mondja, hogy csak akkor kerülhet be, ha a jelölt dob néhányat kosárra, és legalább fele bemegy. Négyszer vagy hatszor dobhat; a jelölt dönti el, hogy hányszor dob. A jelölt eddigi statisztikája pont 50%. Mit válasszon és mekkora esélye van bekerülni a csapatba?

+ Megoldás (kinyit)

- Megoldás (becsuk)

Első ránézésre egy 50% teljesítménnyel és 50%-os minimumelvárással 50%-os esélye van bekerülni a csapatba, és ez függetlennek tűnik a dobások számától. Ám ez nem így van!

Tegyük fel, hogy kettőt dob! Ebben az esetben 4 lehetőség van, mindegyik 25%-os eséllyel:

mindkettőt kihagyja,
az első kihagyja, a másodikat bedobja,
az első bedobja, a másodikat kihagyja,
mindkettőt bedobja.

Igazából csak az első esetben nem kerül be a csapatba, ami 25%, a maradék 75%-ban bekerül.

4 dobás esetén 16 lehetőség van:

mindhármat kihagyja,
egyed bedob, amit négyféleképpen érhet el: az elsőt, a másodikat, a harmadikat ill. a negyediket dobja be,
kettőt dob be, kettőt nem, ami hatféleképpen lehetséges (0 jelenti a sikertelenséget, 1 a sikert): 0011, 0101, 0110, 1001, 1010, 1100,
hármat bedob, egyet ront, ami négyféleképpen lehetséges,
mind a négyet bedobja.

Mivel 50%-os a találati arány, mindegyiknek ugyanakkora az esélye. A 16 esetből számunkra a kedvező esetek száma 6+4+1=11, ami 68,75%-os arány.

Az alábbi diagramnak az ún. Pascal háromszöget ábrázolja, amely azt mutatja meg, hogy melyik lehetőségből hányféle van:

0:               1
1:             1   1
2:          1   2   1
3:        1   3   3   1
4:      1   4   6   4   1
5:    1   5  10  10   5   1
6:  1   6  15  20  15   6   1

Tehát

0 dobás esetén egyféle eredmény jöhet ki, a 0.
1 dobás esetén kétféle eredmény jöhet ki: a 0 és az 1.
2 dobás esetén háromféle eredmény jöhet ki: a 0, az 1 és a 2, de az 1 kétféleképpen.
3 dobás esetén négyféle eredmény jöhet ki: 0 egyféleképpen, 1 háromféleképpen, 2 háromféleképpen, 3 egyféleképpen.
stb.

Érdemes megfigyelni, hogy a háromszögben mindegyik szám a felső kettő összege.

A 4 dobást már megvizsgáltuk. 6 dobás esetén hétféle eredmény jöhet ki, melyből számunkra 4 a kedvező. Összesen 64 lehetőség van, melyek közül a kedvező esetek száma 20+15+6+1=42, így ezt választva 65,625% eséllyel kerül be a jelölt a csapatba.

Mivel a 68,75% esély picivel magasabb mint a 65,625%, a 4 dobást érdemes választani.

Tegyük fel, hogy 80% eséllyel sikeres a dobásunk. Ez esetben a 4-et vagy a 6-ot érdemes választanunk?

+ Megoldás (kinyit)

Az, hogy hányat dobunk, két ponton egészen biztosan lényegtelen: a 0 és a 100% találati arány esetén. Azt az előzőekben láttuk, hogy 50%-os találati arány esetén érdemes a kevesebb dobást választani, míg 80%-os találati arány esetén a nagyobbat. Minden bizonnyal van valahol az 50% és a 80% között egy dobási arány, ahol mindegy, hogy melyiket választjuk, a 4 vagy a 6 dobást. Mi ez a találati arány?

+ Megoldás (kinyit)

Kalózok

Öt kalóz (Amaro, Bart, Charlotte, Daniel, Elizabeth) talál egy kincsesládát amiben 100 aranytallér van. A kapitány (kezdetben Amaro) tesz egy javaslatot a zsákmány elosztására, amire mindenki "yarr"-al (igen) vagy "nay"-jal (nem) szavaznak (tartózkodás nincs). Ha a "yarr"-ok száma nagyobb vagy egyenlő, mint a "nay"-ok száma, akkor a javaslat el van fogadva. Ellenkező esetben a kapitányt bedobják a tengerbe és a soron következő kalóz lesz az új kapitány és ő tesz új javaslatot.

Mindegyik kalóz elsődleges célja életben maradni.
Mindegyik kalóz másodlagos célja, hogy a legtöbb aranyat kapja.
Mindegyik kalóz úgy igyekszik szavazni, hogy az aktuális kapitányt a tengerbe dobják.
Mindegyik kalóz ismeri a preferenciákat, tökéletesek logikai gondolkozásban és ezt tudják is egymásról.
Nem beszélhetnek össze egymással.

Kérdés: milyen javaslatot tegyen Amaro, hogy életben maradjon és a lehető legtöbb aranyat kapja?

+ Megoldás (kinyit)

Borítékok

Van két lezárt boríték, mindkettőben egy-egy különböző pozitív valós szám. A szám bármi lehet 0 és végtelen között, még a nagyságrendjét sem tudjuk. Az egyik boríték tartalmát megnézhetjük, majd anélkül, hogy a másikat megnéznénk, el kell döntenünk, hogy a felnyitott vagy a lezárt borítékot választjuk. Akkor nyerünk, ha a nagyobb számot tartalmazó borítékot választjuk.
Milyen stratégiát érdemes követnünk ahhoz, hogy a várható nyerési esélyünk több legyen mint 50%?

+ Megoldás (kinyit)

"Csak igen" barkochba

András gondol egy számra 1-től 20-ig. Balázs barkochba kérdéseket tesz fel. A válaszokat csak Csaba kapja meg (a kérdéssel együtt), de csak akkor, ha a válasz igen. Milyen stratégiát érdemes Bálintnak követnie, hogy a lehető legkevesebb kérdést tegye fel, és Csaba biztos kitalálja? (Balázs és Csaba egyáltalán nem kommunikálhatnak. További megszorítás a feladat körbejárása részben.)

+ A feladat körbejárása (kinyit)

- A feladat körbejárása

Triviális megoldás, hogy Béla egyesével rákérdez az összes értékre, így 20 kérdésből Csaba mindenképp ki tudja találni.

Ami alá biztosan nem lehet menni az az 5: ugyanis normál barkochba játék esetén is legrosszabb esetben ennyi kérdésre van szükség.

Ebből adódik egy 10 lépéses megoldás: tegye fel Balázs a normál barkochba kérdést és annak ellenkezőjét is. Pl. "a szám legfeljebb 10?" ill. "a szám 10-nél nagyobb"? Utána már trükkösen kell kérdenie, ugyanis Balázs nem tudja a választ. Szóval a következő kérdése lehetne az, hogy "a szám benne van az {1, 2, 3, 4, 5, 11, 12, 13, 14, 15} halmazban?" ill. "a szám benne van a {6, 7, 8, 9, 10, 16, 17, 18, 19, 20} halmazban?".

A 10 lépést viszonylag egyszerűen le lehet csökkenteni 9-re: a 4 lépéses negyedelés után elég egyesével rákérdezni: "a szám benne van az {1, 6, 11, 16} halmazban?", "a szám benne van az {2, 7, 12, 17}"halmazban?" stb.

Tulajdonképpen még egy lépést is le lehet faragni. Az egyszerűség érdekében tegyük fel, hogy a szám 1 és 5 közötti. Ekkor 4 kérdéssel, a halmazokra rákérdezve: {1, 2, 3}; {3, 4, 5}; {1, 4}; {2, 5} egyértelmű eredményt ad, és ez 8 lépés.

Tovább gondolva: 3 kérdésből lehet harmadolni. Pl. 6 szám esetén a kérdések ezek lehetnének: {1, 2, 3, 4}; {1, 2, 5, 6} és {3, 4, 5, 6}, és ebből egyértelmű, hogy {1, 2}, {3, 4} vagy {5, 6}. És ez valamivel jobb, mint 4 kérdésből negyedelni.

Másik irányból megközelítve: Balázs megkéri Andrást, hogy írja fel a gondolt számot kettes számrendszerben, majd egyesével rákérdez a bitekre, hogy az egyes-e. Ez 5 kérdést jelent, és Csaba csak az egyeseket kapja meg. Itt a valóságban persze Csaba feltételezheti, hogy Balázs feltette az összes bitre vonatkozó kérdést és a többi bit 0, de a feladat szempontjából ez szabálytalan. Trükkösen - hatodik kérdésként - felteheti Balázs azt, hogy "a gondolt szám mindegyik bitjére rákérdeztem?", és ezzel Csaba megkapja az információt. Sőt, mindegyik kérdés szólhatna úgy, hogy "Sorra rákérdezek a szám kettes számrendszerbeli alakjának bitjeire, a legkisebb helyi értéktől kezdve. Az első (második, harmadik, negyedik, ötödik) helyi értéken egyes van?" És mivel legalább van egy egyes, Csaba minden információ birtokában van, 5 kérdésből.

A feladatnak ez egy "nem szép" megoldása. Így kössük ki azt, hogy Balázs csak számhalmazokat tehet fel Andrásnak, sőt, azt is, hogy a számok sorrendje csakis növekvő lehet, hogy bármilyen metakommunikáció ki legyen zárva. Tetszőleges számú eleme lehet a halmaznak. A kérdések számát kell úgy minimalizálni, hogy Csaba az igen válaszokat megkapva egyértelműen tudja a választ.

+ Megoldás (kinyit)

Kincs

Kalandozásaid során megtaláltad az ősi alvilági kincset: 100 darab érme, mindegyiknek az egyik oldala aranyból a másik oldala ezüstből van. A kincs őrzője viszont nem enged el téged, amíg meg nem oldod a rejtvényét. Az érméket két kupacba kell szervezned úgy, hogy mindkét kupacban egyenlő számú érme legyen az ezüst oldalával fölfelé. Hogy ne legyen olyan könnyű dolgod, a fáklyák kialszanak, szóval mindezt sötétben kell megtenned.

Az egyetlen dolog amire emlékszel, hogy kezdetben 20 érme volt az ezüst oldallal fölfelé.
A kupacok méretének nem kell megegyezni.
Az érméket megfordíthatod.

Hogyan oldod meg a rejtvényt?

+ Megoldás (kinyit)

Szobák

Egy királylány egy 100 szobás kastélyban él, melyben a szobák egymás mellett vannak sorban. Minden éjjel, pontban éjfélkor kilép a szobából, és átmegy valamelyik mellette levőbe, majd ott tölti a következő 24 órát.
A királyfi meg szeretné találni a királylányt. Ehhez minden délben benyithat egy véletlenszerűen kiválasztott szobába, de naponta csak egybe.
Milyen stratégiát alkalmazzon a királyfi, hogy egy éven belül biztosan megtalálja a királylányt?

+ Megoldás (kinyit)

- Megoldás (becsuk)

A megoldáshoz vezető úton lássuk be az alábbiakat:

Első gondolat lehet az 1, 1, 2, 2, 3, 3, …, 99, 99, 100, 100. Viszont ha a királylány a 6, 5, 4, 3, 2, 1, 2, 1, … módszert választja, akkor elkerülik egymást.
Akármennyi egymásutáni szobalátogatásra tudunk ellenpéldát adni. Pl. az 1, 1, 1, 2, 2, 2, 3, 3, 3, … esetében ha a királylány a 8, 7, 6, 5, 4, 3, 2, 1, 2, 1, … szobákat látogatja, szintén elkerülik egymást.
Következő ötlet: menjünk végig egyesével: 1, 2, 3, …, 98, 99, 100. Ha a királylány páratlan sorszámú szobából indult, akkor belátható, hogy muszáj találkozni. Ha párosból, akkor ugyancsak 1-től kell végigmenni, de előtte "el kell lőni üresbe" egy látogatást (pl. ismét benézni a 100-asba). Tehát az 1, 2, 3, …, 98, 99, 100, 100, 1, 2, 3, …, 98, 99, 100 egy helyes megoldást ad, legfeljebb 201 lépéssel.
Picit tovább gondolva, a paritás úgy is biztosítható, hogy elmegyünk 1-től 100-ig, majd 100-tól 1-ig. Ha a királylány páratlan sorszámú szobából indult, akkor már az első sorozatban találkoznak; ha párosból, akkor a másodikban. Tehát a sorozat 1, 2, 3, …, 98, 99, 100, 100, 99, 98, …, 3, 2, 1, azaz legfeljebb 200 lépésből találkoznak.
Tulajdonképpen ha jobban belegondolunk, ez a megoldás már 199 lépésben eredményre vezet. A második sorozatban ugyanis a királylány párostól indít, és ha megpróbál minél távolabb maradni a királyfitól, akkor az 1 és 2 szobák között vándorol, és belátható, hogy legkésőbb a 2-es szobában találkoznak. Pl. úgy, hogy ha az 1-es szobában találkoznának a végén, akkor már találkoztak eggyel korábban a kettesben.
Viszont ha jobban belegondolunk, akkor elég a 2-es mezőről indulni, és eljutni a 99-es mezőig, majd vissza a 99-től 2-ig, és ez is garantálja a találkozást, mégpedig 196 lépésben. Próbájuk meg belátni! Ha nem megy, akkor javaslom, hogy kezdjük a 4 szobás változatot, a 2, 3, 3, 2 stratégiával. (Ki is lehet próbálni a https://www.geogebra.org/m/KC2rfwkb oldalon, ahol németül van levezetve ez a feladat.) Majd a 6 szobásat 2, 3, 4, 4, 3, 2 stratégiával stb.

A feladat megoldása tehát a következő: ha a királyfi a 2, 3, 4, 5, …, 97, 98, 99, 99, 98, 97, …, 5, 4, 3, 2 sorrendben látogatja meg a szobákat, akkor legfeljebb 196 lépésben megtalálja a királylányt.

Szabadulás a börtönből

Van egy börtön, benne 100 jó magaviseletű rabbal, akiknek esélyt adnak az azonnali szabadulására, a következő formában. Mindegyik rabnak van egy száma 1-től 100-ig. Van egy szoba 100 darab sorba rendezett dobozzal, melyekben számok vannak összekeverve 1-től 100-ig.
A rabok egyesével bemennek, egyszerre egy. Egy adott rab kiválaszthat 50 dobozt. Ha közte van a saját száma, akkor nyert, ha nincs, akkor vesztett. (Nem nehéz belátni: akárhogy is választ, 50% esélye van arra, hogy nyerjen, és 50%, hogy veszítsen.) Mielőtt kimegy, pontosan úgyanúgy kell visszatennie a dobozokat, ahogy találta, és semmilyen módon nem kommunikálhat a többiekkel a későbbiekben.
Mind a 100 rab bemegy egyesével. A rabok akkor szabadulnak, ha mindenki nyert, azaz mindenkinek sikerült a saját sorszámát is kiválasztania. Ha csak egyvalaki veszít, akkor mindenki marad a börtönben. (Itt nem nehéz belátni, hogy ha mindenki véletlenszerűen választ dobozt, akkor 2 rab után 25%, 3 rab után 12,5% stb. esélyük van a szabadulásra, 100 rab után gyakorlatilag nulla.)
Tehát miután kijöttek, nem kommunikálhatnak, de mielőtt bemennek, megbeszélhetnek egy stratégiát. A kérdés: milyen stratégiát válasszanak ahhoz, hogy elérje a nyerési esélyük a 30%-ot?

+ Megoldás (kinyit)

- Megoldás (becsuk)

Ez a videó magyarázza el a megoldást: https://www.youtube.com/watch?v=iSNsgj1OCLA, ahol a történet picit más. Az optimális stratégia a következő: mindenki válassza ki először a saját sorszámához tartozó dobozt, majd azt a dobozt, amelyik szám benne van az általa választott dobozban, és így tovább. Ha nem lenne az 50-es limit, akkor előbb-utóbb mindenképp körbe érne, és a kör utolsó lépése lenne a saját száma, azaz az a doboz, melyben az a szám van, amit először választott.
Belátható, hogy a 100 doboz ilyen körökre, ciklusokra van osztva. Ez lehet egy nagy kör, de ha mindegyik dobozban a saját száma van, akkor 100 kis kör is. A fenti stratégiával ha van olyan kör, melynek hossza több mint 50, akkor vesztettek a rabok, egyébként nyertek.
Most számoljunk valószínűségeket. Az belátható, hogy az összes lehetőség száma $$100!$$ . Ezek közül a 100 hozzá, tehát teljes ciklusok száma a következő. Első lépésben 99 lehetőség közül választhatunk (a doboz saját számát nem választhatjuk, mert egyből bezáródna a kör), másodikban 98 lehetőség közül (az első és az adott doboz sorszámát nem választhatjuk) stb.; az utolsó előtti és az utolsó lépésben már csak egyet-egyet választhatunk, hogy ne záródjon be a kör. Az összes olyan kör tehát, mely teljes, $$99!$$ . A teljes körök aránya tehát $\frac{99!}{100!}=\frac{1}{100}$ . Annak az esélye tehát, hogy egy kör teljes, $\frac{1}{100}$ (Ezen a ponton szerintem hibás a videóban a bizonyítás.)
Annak az esélye, hogy van egy pontosan 99 hosszú kör, hasonlóan adódik. Először válasszuk ki azt, amelyik rögzített, ezt 100 féleképpen tudjuk megtenni. Utána 98 féleképpen tudunk választani (saját magát és az elsőt nem választhatjuk), majd 97 féleképpen stb., összesen tehát az arány $\frac{100\cdot 98!}{100!}=\frac{1}{99}$ . Hasonlóan adódik tetszőleges $1\le n\le 100$ értékre, hogy annak az esélye, hogy van $$n$$ hosszú ciklus, $\frac{1}{n}$ .
A rabok akkor nyernek, ha nincs legalább 51 hosszú ciklus. A bukás esélye tehát $\frac{1}{51}+\frac{1}{52}+\frac{1}{53}+\dots+\frac{1}{100}$ . Programmal kiszámolva adódik az érték: kb. 0,688. A nyerési esély tehát 0,312, azaz 31,2% körüli, tehát egy meglepően magas érték.

Hogyan változik a nyerési esély a rabok számnak növelésével?

+ Megoldás (kinyit)

Tegyük fel, hogy egy jóakaró esély kap arra, hogy kinyithatja az összes dobozt, és felcserélhet kettőt. Mit tegyen, hogy növelje a nyerési esélyeket?

+ Megoldás (kinyit)

Tegyük fel, hogy egy rosszakaró úgy változtatja a dobozok tartalmát, hogy legyen benne 50-nél hosszabb ciklus. Mit tehetnek ez esetben a rabok?

+ Megoldás (kinyit)

Hűtlenség

Van egy falu, ahol 50 házaspár él. A következőket tudjuk:

Mindenki minden vasárnap ott van a templomban, és mindenki rendszeresen gyón.
Minden asszony megcsalja a férjét.
A megcsalást mindenki tökéletes titokban tartja a házastársa előtt.
Viszont mindenki mindenki másról tudja, hogy a többi feleség megcsalja a férjét.
A faluban az a szokás, hogy ha egy férj rájön arra, hogy a felesége megcsalja, akkor a következő vasárnapi szentmisén kiáll az oltár elé, és nyilvánosan kijelenti, hogy őt megcsalják.
Ez fordítva nem igaz.
Ilyen viszont az elmúlt időszakban nem történt, mivel az összes asszony tökéletes titokban tartja a dolgot.
A pap mindenről tud, mivel mindenki rendszeresen gyón.

A papot zavarják a romlott erkölcsi közállapotok, de nem tehet semmit, mivel őt köti a gyónási titoktartás. Egyszer viszont úgy dönt, hogy a vasárnapi prédikációban kijelenti: a faluban van házasságtörés. Ezzel mit ér el?

+ Megoldás (kinyit)

Lovagok és lókötők

Egy szigeten lovagok és lókötők élnek. A lovagok mindig igazat mondanak, a lókötők mindig hazudnak. Találkozunk két emberrel. Odalépünk az egyikhez és megkérdezzük:
- A mellett álló lókötő?
A választ odasúgja a mellette állónak. Megkérdezzük a mellette állót:
- Azt súgta, hogy igen?
- Nem.
Tudjuk-e ebből bármelyikükről biztosan, hogy lovag vagy lókötő?

+ Megoldás (kinyit)

A	B	A tényleges válasza	Amit B mond
lovag	lovag	nem	nem
lovag	lókötő	igen	nem
lókötő	lovag	igen	igen
lókötő	lókötő	nem	igen

Most 11-en vannak a szigeten, egy sorban állva. Az elsőről nem tudunk semmit, a maradék tízről pedig azt tudjuk, hogy fele lovag, fele lókötő. Odalépünk az elsőhöz?
- Ha megkérdezném, hogy lovag vagy-e, az lenne a válaszod, hogy igen?
A választ a sorban következőnek súgja. Odalépünk a következőhöz és megkérdezzük:
- Azt súgta, hogy igen?
A választ tovább súgja, és mi tovább megyünk, egészen a sorban 11. emberig. Az utolsó ember válasza:
- Igen.
Az első ember lovag vagy lókötő?

+ Megoldás (kinyit)

A	Lovag vagy?	Ha megkérdezném, hogy lovag vagy, az lenne a válaszod, hogy igen?
lovag	igen	igen
lókötő	igen	nem

A	A kapott válasz	A továbbadott válasz
lovag	igen	igen
lovag	nem	nem
lókötő	igen	nem
lókötő	nem	igen

10 emberből nem tudjuk, hogy mennyi a lovag és mennyi a lókötő. Az emberek sorban ezt mondják:
- Közülünk legalább egyvalaki lókötő.
- Közülünk legalább ketten lókötők.
- Közülünk legalább hárman lókötők.
- Közülünk legalább négyen lókötők.
- Közülünk legalább öten lókötők.
- Közülünk legalább hatan lókötők.
- Közülünk legalább heten lókötők.
- Közülünk legalább nyolcan lókötők.
- Közülünk legalább kilencen lókötők.
- Közülünk legalább tízen lókötők.
Hány lovag és hány lókötő van?

+ Megoldás (kinyit)

Repülőút

Egy repülőre 440 utas fér fel, és egy adott járaton telt ház van. Az elsőként felszálló utas elveszítette a beszállókártyáját, így véletlenszerűen választ egy helyet, ahova leül. A többi utas mindegyike megpróbál a saját helyére leülni. Ha már foglalt, akkor ugyancsak véletlenszerűen választ a szabad helyek közül. Mekkora annak az esélye, hogy az utolsóként felszálló utas pont a saját eredeti helyét foglalja el?

+ Megoldás (kinyit)

Pénz

Egy gép felajánl neked véletlenszerűen egy 0 és 10.000 Ft közötti összeget (a véletlen szám eloszlása folytonos egyenletes). Ha elfogadod, akkor a gépet soha többé nem látod. Ha nem fogadod el, akkor legközelebb (ami pár hónap múlva lesz) ismét felkínál egy összeget ugyanebből az intervallumból, és akkor is ugyanez lesz a döntési lehetőséged.
A mai pénz természetesen értékesebb, mint a jövőbeli. A szorzó legyen 0,9: a következő 10.000 Ft annyit ér, mint ma 9000 Ft, a kettővel ez utáni 10.000 Ft annyit ér, mint ma 8100 Ft stb.
Maximalizálni szeretnéd a nyereségedet. Milyen stratégiát érdemes alkalmaznod? Hány forinttól érdemes elfogadnod az első alkalommal? Mennyitől a második alkalommal?

+ Megoldás (kinyit)

- Megoldás (becsuk)

Jelölje $$x$$ a megoldást, $$v$$ pedig a várható nyereség jelenértékét. Továbbá az egyszerűség érdekében normalizáljuk mindkettőt [0, 1] közé, így az eredményt a végén meg kell szorozni tízezerrel. (Az eredeti feladatban 100-zal, ott ugyanis maximálisan 100 dollárt ad.)

A dolog egyik kulcsmozzanata az, hogy ha nem fogadjuk el az ajánlatot, akkor a következő lépésben ugyanazt a stratégiát alkalmazzuk az optimális eredmény érdekében. Tehát:

Ha elfogadjuk, azaz az ajánlat nagyobb vagy egyenlő mint $$x$$ , akkor a nyereség a tulajdonképpeni ajánlat. Ebben az esetben a várható érték az egyenletes eloszlás miatt $$x$$ és a maximális érték fele, és azáltal, hogy normalizáltuk $$x$$ -et, ez a $\frac{1+x}{2}$ -re egyszerűsödik. Valamint ennek az esélye - ugyancsak a normalizálás miatt $$1-x$$ .
Ha nem fogadjuk el az ajánlatot, akkor a várható nyereség $0.9\cdot v$ , aminek az esélye $$x$$ .

Összefoglalva:

$v = (1-x)\cdot\frac{1+x}{2} + 0.9\cdot x\cdot v$

Szorozzuk meg mindkét felét oldalt:

$$10v = 5(1-x)(1+x) + 9xv$$

Átrendezve:

$$v(10-9x) = 5 - 5x^2$$

Kifejezve $$v$$ -t:

$v = \frac{5 - 5x^2}{10 - 9x}$

Itt valójában arra vagyunk kíváncsiak, hogy a $$v$$ hol veszi fel a maximumot. Ezt deriválással tudjuk eldönteni. Deriváljuk tehát $$x$$ szerint a fenti függvényt! Emlékeztetőül, az osztás deriváltja:

$\left(\frac{f}{g}\right)' = \frac{f'g - fg'}{g^2}$

Itt:

$$f(x) = 5 - 5x^2$$
$$f'(x) = -10x$$

$$g(x) = 10 - 9x$$
$$g'(x) = -9$$

Az eredeti függvény deriváltja tehát:

$\left(\frac{5 - 5x^2}{10-9x}\right)' = \frac{(5 - 5x^2)'(10 - 9x) - (5 - 5x^2)(10 - 9x)'}{(10 - 9x)^2} = \frac{-10x\cdot(10-9x) - (5-5x^2)\cdot(-9)}{100 - 180x + 81x^2} = \frac{-100x + 90x^2 + 45 - 45x^2}{81x^2 - 180x + 100} = \frac{45x^2 - 100x + 45}{81x^2 - 180x + 100}$

Az eredeti függvénynek ott van szélsőértéke, ahol a derivált nulla:

$\frac{45x^2 - 100x + 45}{81x^2 - 180x + 100} = 0$

Azaz:

$$45x^2 - 100x + 45 = 0$$

Osztva 5-tel:

$$9x^2 - 20x + 9 = 0$$

Ezt a másodfokú egyenlet megoldóképletével tudjuk megoldani. Emlékeztetőül a megoldóképlet:

$x_{1,2} = \frac{-b\pm\sqrt{b^2-4ac}}{2a}$

Behelyettesítve:

$x_{1,2} = \frac{20\pm\sqrt{20^2 - 4\cdot 9\cdot 9} }{18} = \frac{20\pm\sqrt{400 - 324} }{18} = \frac{20\pm\sqrt{76}}{18}$

Itt $$x$$ értéke 0 és 1 közé kell, hogy essen, és ez a kivonás esetén következik be. Tehát:

$x = \frac{20-\sqrt{76}}{18} \approx 0.626789$

Mivel az elején osztottunk tízezerrel, most vissza kell szoroznunk. A megoldás így 6267,89.

A feladat ugyan nem kérdezi, de visszahelyettesítve, a várható nyeremény jelenértéke:

$v = \frac{5 - 5x^2}{10 - 9x} = \frac{5 - 5\left(\frac{20-\sqrt{76}}{18}\right)^2}{10 - 9\left(\frac{20-\sqrt{76}}{18}\right)} \approx 0.696432$

Itt is meg vissza kell szorozni tízezerrel, hogy megkapjuk az eredeti feladat eredményt: 6964,32

A teljességhez még két dolog hozzátartozik:

Meg kell győződni arról, hogy a nevező nem nulla.
Meg kell győződni arról, hogy a szélsőérték valóban maximum és nem minimum.

Összefoglalva: kb. 6268 forinttól érdemes elfogadni az ajánlatot, és így a várható nyereség jelenértéke kb. 6964 forint.

EGYSZERŰSÍTÉS

(Köszi, Simon Dani!)

A deriválás elkerülhető! Tegyük fel, hogy ismerjük $$v$$ értékét. Valójában ennek 90%-a felett érdemes elfogadni az ajánlatot, ez alatt ugyanis lesz egy $$v$$ ajánlatunk a következőben, ami ma $$0.9v$$ -t ér. Tehát: adódik ez az összefüggés:

$$x = 0.9v$$

A deriválás előtt itt tartottunk:

$v = \frac{5 - 5x^2}{10 - 9x}$

Helyettesítsük be a felső képletbe a lenti $$v$$ -t:

$x = 0.9\frac{5 - 5x^2}{10 - 9x}$
$$x(10 - 9x) = 0.9(5 - 5x^2)$$
$$10x - 9x^2 = 4.5 - 4.5x^2$$
$$4.5x^2 - 10x + 4.5 = 0$$
$$9x^2 - 20x + 9 = 0$$

Ezzel elérkeztünk a fenti másodfokú egyenlethez. Az $$x$$ -et a fent levezetett módon határozzuk meg, a $$v$$ pedig egyszerűbben adódik.

Hunyadi és a törökök

Mehemed szultán ostromolja a várat, Hunyadi védekezik. A törökök egy lépcsőn haladnak felfelé, minden lépésben minden katona egy lépcsőfokot. Mehemed taktikája az, hogy minden lépésben kettéosztja a katonáit. Hunyadi tetszése szerint kiválasztja az egyik ellenséges csoportot, és ott mindenkit lekaszabol, viszont a másik csoport érintetlen marad. A törökök akkor győznek, ha legalább egy katonájuk felér a legfelső lépcsőfokra. Hunyadi akkor győz, ha minden támadó török katona meghal.

A támadás adott konfigurációból indul, pl. 0, 1, 1, 3, 2, 4 ami azt jelenti, hogy a legfelső (Mehemed számára nyerő) szinten 0 katona van, az másodikon és a harmadikon 1-1, a negyediken 3 stb.

Mi a legjobb stratégiája Mehemednek és mi Hunyadinak? Mikor van Mehemednek és mikor Hunyadinak nyerési stratégiája?

+ Megoldás (kinyit)

oldalváltozat: 53, utoljára szerkesztve: 26 Oct 2023 20:30

Szerkesztés Rate (0) Címkék Vita Előzmények Fájlok Nyomtatás Eszközök + Opciók

Faragó Csaba

Téglalapok száma a sakktáblán

Sakktábla lefedése dominókkal

Zsinór égetése

A légy által megtett út

Almák és narancsok

12 golyó

Cukorkák

Érmék

Kockadobós játék

Nyeremény eldöntése kockadobással

Két fej egymás után

Baktériumok

Kinder tojás

Kétfejű érme

Párbaj

Kockadobás

Repülőgép

Dzsinn

Interjú

Metrók

Tojások leejtése

Lányok életkora

Melyik a nagyobb?

i-nek az i-edik hatványa

Időjárás

Kosárlabda

Kalózok

Borítékok

"Csak igen" barkochba

Kincs

Szobák

Szabadulás a börtönből

Hűtlenség

Lovagok és lókötők

Repülőút

Pénz

Hunyadi és a törökök