Első ránézésre lehetetlen feladatnak tűnik, mert semmi logikát nem találunk, és arra gondolhatunk, hogy iszonyatosan hosszú ideig tart a kiszámolása. Pedig van egy egyszerű ötlet:

• Vegyük az összes csúcsot, ami 9*9=81.
• Mindegyik csúcsból 64 téglalap átló húzható.
• Mindegyik téglalap átlóját négyszer húztuk meg.
• Az eredmény tehát 81*64/4 = 1296.

Nem ugyanis két egyforma színű mezőt vettünk ki, és egy dominó két ellentétes színű mezőt fed le. Azaz az egyik színű mezőkből 32, a másikból 30 maradt, 31 dominóval viszont csak úgy tudnánk lefedni, ha mindkét színből 31 lenne.

Meggyújtjuk az egyik zsinórt. Ha leégett, meggyújtjuk a másik zsinór mindkét felét egyszerre.

A feladat egyszerűbb mint gondolnánk! A két vonat egymáshoz viszonyított sebessége 120 km/h, és mivel 120 km-re vannak egymástól, egy óra telik el az ütközésig. A légy 100 km/h sebességgel halad egy órán keresztül, így összesen 100 km-t tesz meg.

Meglepő módon elég egy is. A feladat kulcsa az, hogy mindegyiken rossz címke van. Valójában a gyümölcsök darabszáma érdektelen. Abból a ládából, amelyen az alma és narancs címke található, ki kell vennünk egyet. Ha az narancs, akkor arra a ládára kell tenni a narancs címkét, alma esetén az almát. Ahonnan levettük a címkét, oda a harmadik ládáról át kell tenni a címkét, azaz első esetben az alma, a második esetben pedig a narancs címkét, végül a harmadik ládára tesszük az almát és narancsot ábrázoló címkét.

Minimálisan elegendő 3 mérés.

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.

Elvileg nem lehetetlen, ugyanis 3-at mérünk, és minden mérésnek 3 lehetséges eredménye lehet, ami összesen 27 kombinációt eredményez, a megoldások lehetséges száma viszont ennél kevesebb: 24 (a 12 golyó mindegyike lehet nehezebb vagy könnyebb).

A 3 mérés legyen a következő:

• 1. mérés: 1, 2, 3, 4 és 5, 6, 7, 8.
• 2. mérés: 1, 2, 5, 9 és 3, 4, 10, 11.
• 3. mérés: 3, 7, 9, 10 és 1, 4, 6, 12.

A lehetséges 27 eset (E: egyenlő, B: balra billen, J: jobbra billen):

• EEE: nem lehetséges.
• EEB: a 12-es könnyebb.
• EEJ: a 12-es nehezebb.
• EBE: a 11-es könnyebb.
• EBB: a 9-es nehezebb.
• EBJ: a 10-es könnyebb
• EJE: a 11-es nehezebb.
• EJB: a 10-es nehezebb.
• EJJ: a 9-es könnyebb.
• BEE: a 8-as könnyebb.
• BEB: a 6-os könnyebb.
• BEJ: a 7-es könnyebb.
• BBE: a 2-es nehezebb.
• BBB: nem lehetséges.
• BBJ: az 1-es nehezebb.
• BJE: az 5-ös könnyebb.
• BJB: a 3-as nehezebb.
• BJJ: a 4-es nehezebb.
• JEE: a 8-as nehezebb.
• JEB: a 7-es nehezebb.
• JEJ: a 6-os nehezebb.
• JBE: az 5-ös nehezebb.
• JBB: a 4-es könnyebb.
• JBJ: a 3-as könnyebb.
• JJE: a 2-es könnyebb.
• JJB: az 1-es könnyebb.
• JJJ: nem lehetséges.

Azt gondolom, hogy a fenti, iteratív módszer talán jobban érthető, viszont ezt könnyebben meg lehetne valósítani számítógépes programként.

Jelöljük a csomagokat 1, 2 és 3-as számokkal. Az egyesből vegyünk ki egyet, a kettesből 2-t, a hármasból 4-et, és ezt a 7 szem cukorkát helyezzük a mérlegre. A lehetséges eredmények (mért tömeg grammban: első, második és harmadik csomag cukorkák tömege):

• 29: 5, 4, 4
• 30: 4, 5, 4
• 31: 5, 5, 4
• 32: 4, 4, 5
• 33: 5, 4, 5
• 34: 4, 5, 5

Kettő hatványokban érdemes gondolkodnunk: 1, 2, 4, 8, 16, 32, 64, 128, és az utolsóba beletesszük a maradék 245-öt, így 9 zacskóra (egységre) van szükség.

Általánosabban: kettes alapú logaritmus az adott szám, felfelé kerekítve. Tehát pl. 5000 érme esetén a megoldás 13 lenne.

Tegyük fle, hogy $p$ valószínűséggel nyer Aladár! Ekkor a valószínűség a következkből adódik:

• Ha egyből hatos dob, akkor $\frac{1}{6}$.
• Ha nem dob hatost (aminek $\frac{5}{6}$ az esélye), akkor $\frac{1}{6}$ eséllyel kerül rá ismét a sor, és ekkor "újraindul" a játék, azaz ekkor is $p$ eséllyel nyer.

Összefoglalva:

$p = \frac{1}{6} + (\frac{5}{6})^{2}\cdot p$

Kifejezve ebből $p$-t:

$p = \frac{\frac{1}{6}}{1-(\frac{5}{6})^{2}}$

Kiszámolva a végeredményt:

$p = \frac{6}{11} \approx 0.545$

Ennek a megoldásnak a különlegessége az, hogy a megoldás megjelenik az egyenlet jobboldalán is.

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.

A feladatot rekurzív megoldással oldjuk meg. A megoldás alapötletét az adja, hogy ha írást dobunk, akkor újra indul a számlálás. Jelölje $x$ a végeredményt. Elemezzük ki az első egy ill. két dobást:

• Az első dobás írás: ennek a valószínűsége $\frac{1}{2}$, és a megoldás ez esetben $x+1$.
• Az első dobás fej, a második dobás írás: ennek a valószínűsége $\frac{1}{4}$, a megoldás ez esetben $x+2$.
• Az első és a második dobás is fej: ennek a valószínűsége $\frac{1}{4}$, a megoldás ez esetben $2$.

A fentiekkel lefedtük az összes esetet, így számoljunk!

$x = \frac{1}{2} \cdot (x + 1) + \frac{1}{4} \cdot (x + 2) + \frac{1}{4} \cdot 2$
$x = \frac{1}{2} x + \frac{1}{2} + \frac{1}{4} x + \frac{2}{4} + \frac{2}{4}$
$x - \frac{1}{2} x - \frac{1}{4} x = \frac{1}{2} + \frac{1}{2} + \frac{1}{2}$
$\frac{1}{4} x = \frac{3}{2}$
$x = 6$

Átlagosan tehát 6 dobásból kapunk egymás után két fejet.

A feladat amiatt tetszik nekem, mert első ránézésre könnyű, másodikra kifejezetten nehéz, viszont ha "megerőszakoljuk" az agyunkat, akkor ismét leegyszerűsödik. A megoldás ötlete hasonló a kockadobós játékhoz.

Egy adott baktérium kihalása független a többitől. Legyen ez az érték (tehát az, hogy egy adott baktérium meghal, vagy osztódik ugyan, de előbb-utóbb az összes leszármazottja kihal) $x$. Az $x$ értéke:

• $25\%$ eséllyel $100\%$
• $75\%$ eséllyel $x^2$

Összevonva:

$x = 0.25 + 0.75\cdot x^2$

Megszorozva 4-gyel és átrendezve:

$3x^2 - 4x + 1 = 0$

Behelyettesítve a másodfokú egyenlet megoldóképletébe:

$x=\frac{4\pm\sqrt{(-4)^2-4\cdot 3\cdot 1}}{2\cdot 3}$

Megoldva:

$x=\frac{4\pm 2}{6}$

Az egyenlet két megoldása $x_1 = 1$ és $x_2 = \frac{1}{3}$. A helyes megoldás az $x = \frac{1}{3}$-ból adódik. Mivel a feladatban két induló baktérium volt, és a túlélésük vagy kihalásuk egymástól független, az eredeti feladat megoldása:

$x = \frac{1}{3}\cdot\frac{1}{3} = \frac{1}{9}$

A baktérium kolónia $\frac{1}{9}$ eséllyel hal ki.

Általánosítsuk a feladatot!

Vegyünk észre két dolgot:

• Ha $n$ darab valamit gyűjtünk, és ebből $k$ darab van meg, akkor $\frac{n-k}{n}$ esélyünk van arra, hogy a következő vásárlás számunkra kedvező lesz, és ez azt is jelenti, hogy átlagban $\frac{n}{n-k}$ darab vásárlásra van szükségünk. (Ez az előző feladatok megoldásánál bemutatott módszerrel is kiszámolható, de pl. könnyen belátható az, hogy ha pl. egy kockával ötöst vagy hatost szeretnénk dobni, tehát $\frac{1}{3}$ eséllyel dobunk számunkra kedvezőt, akkor átlagosan hármat kell dobnunk ahhoz, hogy kijöjjön. Ami persze lehet, hogy egy lesz, és lehet, hogy 15.)
• A vásárlási ciklusok függetlenek egymástól. Az elején nyilván veszünk egyet. Utána addig vásárolunk, amíg az elsőtől különböző nem lesz, és így tovább. Ha pl. már meg van 6, akkor mindegy, hogy pontosan melyik 6 van meg, a hetedik megvásárlásának a hosszát nem befolyásolja.

Általános esetben tehát a lépések száma a következő:

$\frac{n}{n} + \frac{n}{n-1} + \frac{n}{n-2} + ... + \frac{n}{2} + \frac{n}{1}$

4-re behelyettesítve:

$\frac{4}{4} + \frac{4}{3} + \frac{4}{2} + \frac{4}{1} = \frac{25}{3} =8\frac{1}{3}$

A megoldás tehát 8 és 9 között van, és mivel felfelé érdemes kerekíteni, fogadjuk el a 9-et!

Általánosan ez a kupongyűjtő probléma (https://en.wikipedia.org/wiki/Coupon_collector's_problem). A megoldás $n\cdot \log(n)$-nel arányos.

A feladatot a Bayes-tétel segítségével oldjuk meg,a mi a következő:
$P(A|B)=\frac{P(B|A)\cdot P(A)}{P(B)}$

Itt $P(A)$ az $A$ esemény bekövetkezésének a valószínűségét jelenti, $P(A|B)$ pedig azt, hogy mekkora az $A$ esemény bekövetkezésének a valószínűsége feltéve, hogy $B$ esemény bekövetkezik.

Az események legyenek az alábbiak:

• $A$: a kétfejű érmét választottuk.
• $B$: három fejet dobtunk egymás után.

Így a feladat tehát pont a $P(A|B)$ kiszámítása. Lássuk a valószínűségeket!

• $P(B|A)$: ez azt jelenti, hogy mi a valószínűsége annak, hogy három fejet dobunk egymás után, ha a kétfejű érmével dobunk. A valószínűség nyilván $100\%$, azaz $1$.
• $P(A)$: ez azt jelenti, hogy mi a valószínűsége annak, hogy a kétfejű érmét választjuk. Mivel tíz érméből egy a kétfejű, a valószínűség $10\%$, azaz $\frac{1}{10}$.
• $P(B)$: ez azt jelenti, hogy mi a valószínűsége annak, hogy három fejet dobunk egymás után. Ezt kétféleképpen tudjuk elérni. Egyrészt kilenctized eséllyel választunk szabályos érmét, és ekkor egynyolcad eséllyel lesz az eredmény három fej: $\frac{9}{10}\cdot\frac{1}{8} = \frac{9}{80}$, másrészt egytized eséllyel választjuk a kétfejű érmét, és ekkor $100%$, hogy három dobásból mindhárom írás lesz $\frac{1}{10}\cdot 1 = \frac{1}{10} = \frac{8}{80}$. A kettőt összeadva adódik a valószínűség: $\frac{9}{80} + \frac{8}{80} = \frac{17}{80}$.

Helyettesítsünk be a Bayes-formulába:

$P(A|B)=\frac{1\cdot \frac{1}{10}}{\frac{17}{80}} = \frac{80}{170} = \frac{8}{17} \approx 0.47 = 47\%$

Tehát a megoldást az, hogy körülbelül 47% eséllyel választottuk a kétfejű érmét.

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}$.

Induljunk ki abból, hogy egyetlen dobás esetén a várható nyereség $3,5$! (Egyhatod eséllyel jön ki az egyes, kettes stb., a valószínűségekkel vett szorzatuk összege $3,5$.)
Ha két dobásunk lenne, és az első dobás legfeljebb 3, akkor érdemes újra dobni, mivel egy dobás várható nyeresége $3,5$. Ha az első dobás legalább négy, akkor viszont érdemes megállni, mert azt nem érdemes elcserélni egy alacsonyabb várható értékű nyereséggel. Ha legalább négyest dobtunk, az egyharmad eséllyel jelent négyest, egyharmad eséllyel ötöst és egyharmaddal hatost, melynek a várható értéke öt. Azaz két dobás esetén a várható nyereség $0,5\cdot 3,5 + 0,5\cdot 5 = 4,25$.
Három dobás esetén ha a dobás 1, 2, 3 vagy 4, akkor érdemes újra dobnunk, mert két dobás esetén a várható nyereség $4,25$, ami magasabb mint 4. Ellenben 5 és 6 esetén érdemes megállnunk. Ez utóbbi esetben a várható nyereség $5,5$. Tehát 3 dobás esetén a várható nyereség $\frac{2}{3}\cdot 4,25 + \frac{1}{3}\cdot 5,5 = \frac{14}{3}$, azaz 4,66.

Ezt a gondolatmenetet folytatva egyébként azt is meghatározhatjuk, hogy mennyi az a minimális dobásszám, amely esetén már csak a hatost érdemes első dobásként elfogadnunk. Négy dobás esetén is az ötösnél érdemes megállni; a várható nyereség a fenti gondolatmenettel $\frac{89}{18} \approx 4,94$.
Öt dobás esetén is tehát még érdemes az ötnél megállni, mivel négy dobásnál kisebb a várható érték ötnél, és így a várható nyereség $\frac{277}{54} \approx 5,13$ lesz.
Hat dobás esetén viszont már nem éri meg elfogadni az ötöst, mivel öt dobás esetén a fölé mehet a várható érték. Tehát hat dobástól kezdve csak a hatost érdemes elfogadnunk.

Az első utas $\frac{1}{440}$ eséllyel foglalja el a saját helyét, $\frac{1}{440}$ eséllyel az utolsó utas helyét, és $\frac{338}{440}$ eséllyel egy másikat. A probléma tehát $\frac{2}{440}$ eséllyel eldől már az első lépésben, és feltéve, hogy eldől, 50% eséllyel ül a saját helyre, és 50% eséllyel az utolsó utas helyére, azaz 50% annak az esélye, hogy az utolsó utas szabadon találja az ülőhelyét.

Ha nem dől el, akkor ugyanez a játék folytatódik a következő utasokkal. Általában: ha még $n$ szabad hely van, és az aktuálisan felszálló utas helye foglalt, akkor $\frac{1}{n}$ eséllyel ül le az aktuálisan felszálló utas az elsőként felszálló utas helyére, $\frac{1}{n}$ eséllyel az utolsó utas helyére, és $\frac{n-2}{n}$ eséllyel egy másikra. De ha ezen a ponton eldől, akkor ugyancsak 50% eséllyel ül az első utas helyére, és 50% eséllyel az utolsó utas helyére, azaz általános esetben 50% eséllyel lesz üres az utolsónak felszálló utas helye.

A probléma legkésőbb akkor eldől, amikor az utolsó előtti utas száll fel; ez esetben - mivel a feltételezés szerint még nem dőlt el - az utas azt tapasztalja, hogy a saját helye foglalt, így a két szabadon marad ülőhely közül $\frac{1}{2}$ eséllyel fogja az első utasét választani, így $\frac{1}{2}$ eséllyel marad szabadon az utolsóként felszálló utas ülőhelyre.

Összefoglalva: a megoldás 50%.

Ez két szempontból is kicsit paradoxon jellegű feladat:

• Az ember az gondolná, hogy ha egy valaki elrontja, akkor "borul az egész", és nagyon pici annak az esélye, hogy az utolsó utasnak pont megmarad a saját helye, ráadásul minél nagyobb a repülő, ez annál valószínűbb. A valóságban viszont 50%, és ez független a mérettől.
• A feladatot első ránézésre sokkal nehezebbnek gondolnánk, pl. feltételes valószínűségű sorösszegek felé indulnánk el, ami természetesen zsákutca

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.

Először is járjuk körbe kicsit a feladatot! Ha pl. azt a stratégiát választja, hogy mindhárom jelöltet meghallgatja, akkor tudni fogja a sorrendet, de mindenképp a harmadikat kell felvennie, és $\frac{1}{3}$ lesz az esélye annak, hogy pont ő a legjobb. Hasonlóan $\frac{1}{3}$ jön ki akkor is, ha rögtön az első jelöltet felveszi, de soha nem fogja megtudni, hogy jól választott-e. Vajon az egyharmadnál van jobb megoldás?

Igen, van! Ha úgy dönt, hogy az elsőt meghallgatja, de mindenképpen elutasítja, majd ha a második jelölt jobb volt, mint az első, akkor őt veszi fel, különben a harmadikat, akkor a következő esetek lehetségesek (1: legrosszabb, 2: középső, 3: legjobb; +: a legjobbat választotta; -: nem a legjobbat választotta):

• 123: -
• 132: +
• 213: +
• 231: +
• 312: -
• 321: -

A 6 esetből 3 számunkra kedvező, így 50% annak az esélye, hogy ezzel a módszerrel a legjobbat választja.

Érdemes a megoldáshoz hozzátenni, hogy ezzel $\frac{1}{3}$ eséllyel választja a középsőt és $\frac{1}{6}$ eséllyel a legrosszabbat. Ez mindenképpen jobb, mint az $\frac{1}{3} : \frac{1}{3} : \frac{1}{3}$.

De mi a helyzet akkor, ha nem 3, hanem 10 vagy 100 jelölt van, ill. általánosan, $N$ számú. Ez esetben milyen stratégiát érdemes alkalmazni, és mekkora lesz az esély a legjobb jelölt kiválasztására? Ez egy típus feladat, az ún. titkárnő probléma: https://en.wikipedia.org/wiki/Secretary_problem. Levezetés nélkül: $\frac{N}{e}$ jelöltet érdemes meghallgatni, de mindet automatikusan visszautasítani, majd az első olyan jelöltet választja, aki jobb volt minden korábbinál. Ez esetben, ha $N$ tart végtelenbe, akkor $\frac{1}{e}$, azaz kb. 37% eséllyel lesz a végső választás a legjobb. Minden bizonnyal ennél jóval kisebbre tippeltünk volna.

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:

• https://math.stackexchange.com/questions/2812710/operatorname-e-left-min-left-x-1-x-2-right-right-where-x-1-sim-u-0?rq=1
• https://www.reddit.com/r/askmath/comments/6f76no/what_is_eminxy_where_x_uniform05_y_uniform03/

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!

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.

Ha felbontjuk a 72-t 3 egész szám szorzatára (pl. 3*4*6, 2*4*9 stb.), majd mindegyik esetben összeadjuk a számjegyek összegét, akkor egy olyan eset van, ahol két összeg ugyanakkora: 2+6+6 és 3+3+8. (A házszám tehát 14.) Csak ez az egy lehetőség van arra, hogy Szabó a szorzatból és az összegből még nem tudhatja pontosan a lányok életkorát. A vanília fagyis információban azt olvashatjuk ki, hogy van egy egyértelmű legidősebb, így a 3+3+8 kombináció maradt. (Most tekintsünk el attól, hogy ikrek esetén is van legidősebb…)

A feladat egyszerűnek tűnik, de valójában nem az! Ha közeli számokkal próbálkozunk, az nem ad támpontot, pl. $2^3 < 3^2$; de $3^4 > 4^3$.

Általánosítsuk a kérdést: melyik a nagyobb, $a^b$ vagy $b^a$? Tegyük fel, hogy $a$ és $b$ is pozitív. Vegyük mindkét oldal természetes alapú logaritmusát:

$\ln a^b <> \ln b^a$

Emeljük ki a kitevőt!

$b \cdot \ln a <> a \cdot \ln b$

Osszuk el mindkettőt $a\cdot b$-vel:

$\frac{\ln a}{a} <> \frac{\ln b}{b}$

Legyen

$f(x) = \frac{\ln x}{x}$

Számoljuk ki a deriváltját! A tört deriválási szabálya:

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

Ezt felhasználva:

${\left(\frac{\ln x}{x}\right)}^{'} = \frac{(\ln x)'\cdot x - \ln x \cdot x'}{x^2} = \frac{\frac{1}{x} \cdot x - \ln x \cdot 1}{x^2} = \frac{1 - \ln x}{x^2}$

Vizsgáljuk meg ezt a függvényt ott, ahol x>0! Mivel $\ln e = 1$:

• $x < e$: pozitív
• $x = e$: nulla
• $x > e$: negatív

Most "pörgessük vissza" a dolgokat! Ezt felhasználva az $f(x)$ függvény elemzéséhez:

• $x < e$: növekszik
• $x = e$: itt van maximum értéke
• $x > e$: csökken

Ez a levelezés nem alkalmas arra, hogy az $a < e < b$ eseteket általánosságban megoldja, de az eredeti feladatban nem ez az eset áll fenn. Tehát $a$ és $b$ is az $e$-nek "ugyanazon a felén vannak". Ez esetben a $\frac{\ln a}{a} <> \frac{\ln b}{b}$ egyenlőtlenségnek az az oldala lesz a nagyobb, amelynél a konstans közelebb van az $e$-hez. Tegyük fel, hogy az $a$ van közelebb! Visszatérve a $a^b ? b^a$ kérdésre, 3 esetek különböztetünk meg:

• ha $b < a < e$, akkor $a^b > b^a$
• ha $a = e$, akkor - mivel itt van az $f(x)$ függvény maximuma, $a^b > b^a$
• ha $b > a > e$, akkor is $a^b > b^a$

Az eredeti feladat megoldása ez alapján:

$e^\pi > \pi^e$

A feladatot kétféleképpen oldjuk meg! Az első a fenti továbbgondolása: mivel e < 999999999 < 1000000000, ezért a fenti feladat levezetéséből adódik, hogy $999999999^{1000000000}$ nagyobb mint $1000000000^{999999999}$.

A másik megoldás viszont szerintem elegánsabb. A feladatot a következő formában oldjuk meg: melyik a nagyobb: $a^{a+1}$ vagy $(a+1)^a$ úgy, hogy tudjuk, $a$ egy nagy pozitív szám.

Osszuk el mindkét oldalt $a^a$-nal! Ekkor az egyik oldal:

$\frac{a^{a+1}}{a^a} = \frac{a^a \cdot a}{a^a} = a$

A másik oldal:

$\frac{(a+1)^a}{a^a} = \left({\frac{a+1}{a}}\right)^a = \left({1 + {\frac{1}{a}}}\right)^a \approx e$

Tehát a bal oldal értéke $a$, azaz az eredeti feladatban 999999999, a jobb oldalé pedig $e$, ezért nyilvánvaló, hogy $a > e$, így az is igaz, hogy $a^{a+1}$ nagyobb mint $(a+1)^a$.

Meglepő, de ez egy valós szám. Az Euler-képletből indulunk ki:

$e^{i\cdot x} = \cos x + i\cdot\sin x$

Ha $x = \frac{\pi}{2}$, akkor

$e^{i\cdot\frac{\pi}{2}} = \cos\frac{\pi}{2} + i\sin\frac{\pi}{2} = i$

Fordítsuk meg, és emeljük $i$-edik hatványra:

$i^i = \left(e^{i\cdot\frac{\pi}{2}}\right)^i = e^{i\cdot\frac{\pi}{2}\cdot i} = e^{i\cdot i\cdot\frac{\pi}{2}} = e^{-1\cdot\frac{\pi}{2}}$

Tehát:

$i^i = e^{-\frac{\pi}{2}}$

Habár az összes kombináció nem elképzelhetetlenül magas ($3^10 = 59.049$), és számítógéppel pillanatok alatt kiszámolható, segítség nélkül lehetetlen lenne ennyit átnézni. Ehelyett induljunk ki az alábbiból. Egy nap biztos, hogy 1 lesz a várható érték. Vizsgáljuk meg a két napot! A következő lehetőségek vannak:

• napos → napos: 16% eséllyel, 1 sorozat
• napos → szeles: 16% eséllyel, 2 sorozat
• napos → esős: 8% eséllyel, 2 sorozat
• szeles → napos: 16% eséllyel, 2 sorozat
• szeles → szeles: 16% eséllyel, 1 sorozat
• szeles → esős: 8% eséllyel, 2 sorozat
• esős → napos: 8% eséllyel, 2 sorozat
• esős → szeles: 8% eséllyel, 2 sorozat
• esős → esős: 4% eséllyel, 1 sorozat

Összegezve:

• 16% + 16% + 4% = 36% eséllyel lesz a sorozat 1 hosszú
• 16% + 8% + 16% + 8% + 8% + 8% = 64% eséllyel lesz a sorozat 2 hosszú

Ezt próbáljuk meg általánosítani! A második naptól kezdve (amikor már volt előző nap):

• napos és szeles: 60% eséllyel növeli eggyel a sorozat hosszát, 40% eséllyel nem változik
• esős: 80% eséllyel növeli eggyel a sorozat hosszát, 20% eséllyel nem változik.

Mivel a napos és a szeles időjárás esélye 40%-40%, az esősé pedig 20%, annak az esélye, hogy eggyel nő a sorozat hossza: $0,4\cdot 0,6 + 0,4\cdot 0,6 + 0,2\cdot 0,8 = 0,64$, azaz 64%. 1 nap esetén 1 a várható érték, 2 nap esetén 1.64, 3 nap esetén 2,28 stb., általában $n$ nap esetén $1 + (n-1)\cdot 0,64$. 10 nap esetén a megoldás [[1 + 9\cdot 0,64 = 6,76]].

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.

Az előzőek alapján könnyen rávágjuk hogy a négyet. De számoljuk csak!

4 dobás esetén, 80%-os találati arány esetén:

• Annak az esélye, hogy mind a 4 bemegy: $0.8^4 = 0,4096 = 40,96%$
• Annak az esélye, hogy 3 bemegy, 1 nem: $0.8^3 \cdot 0.2 = 0,1024 = 10,24%$
• Annak az esélye, hogy 2 bemegy, 2 nem: $0.8^2 \cdot 0.2^2 = 0,0256 = 2,56%$

Figyelembe véve a lehetőségek számát, a teljes valószínűség:

$6\cdot 2,56% + 4\cdot 10,24% + 40,96% = 97,28%$

Most nézzük meg a 6 dobást! Egyszerűbb azt kiszámolni, hogy mekkora eséllyel nem veszik be a csapatba:

• Mind a 6-ot kihagyja: $0.2^6 = 0,000064 = 0,0064%$, ami egyféleképpen fordulhat elő.
• 1 bemegy, 5 nem: $0.8\cdot 0.2^5 = 0,000256 = 0,0256%$, ami hatféleképpen fordulhat előt, tehát a teljes valószínűség $6\cdot 0,0256% = 0,1536%$
• 2 bemegy, 4 nem: $0.8^2\cdot 0.2^4 = 0,001024 = 0,1024%$, ami tízféleképpen lehetséges, tehát a teljes valószínűség $10\cdot 0,1024% = 1,024%$

A három lehetőséget összeadva: $0,0064% + 0,1536% + 1,024% = 1,184%$

Vonjuk ki ezt a 100%-ból, hogy megkapjuk a legalább 3 pontot elérés valószínűségét: $100% - 1,184% = 98,816%$

Mivel a 98,816% nagyobb mint a 97,28%, ezért a 80%-os találati arányt elérőknek inkább érdemes választani a 6 dobást.

Ez nem nehéz, csak hosszú.

Jelentse $x$ azt a valószínűséget, hogy a jelöltet nem veszik be a csapatba. Az eredmény tehát $1-x$ lesz.

Annak az esélye, hogy 4 dobásnál nem dob legalább 2 pontot:

$x^4 + 4x^3(1-x) = x^4 + 4x^3 - 4x^4 = -3x^4 + 4x^3$

Annak az esélye, hogy 6 dobásnál nem dob legalább 3 pontot:

$x^6 + 6x^5(1-x) + 10x^4(1-x)^2 = x^6 + 6x^5 - 6x^6 + 15x^4 - 30x^5 + 15x^6 = 10x^6 - 24x^5 +15x^4$

A két valószínűséget kell egyenlővé tenni:

$-3x^4 + 4x^3 = 10x^6 - 24x^5 +15x^4$

Rendezzük jobb oldalra:

$0 = 10x^6 - 24x^5 + 18x^4 - 4x^3$

Mivel mindenképp van olyan megoldás, ami 0,5 és 0,8 közötti, osszuk el $x^3$-nal:

$10x^3 - 24x^2 + 18x - 4 = 0$

Ez egy harmadfokú egyenlet, ami zárt képlettel kiszámolható. A https://www.calculatorsoup.com/calculators/algebra/cubicequation.php oldalon beírva az értékeket, a 3 eredmény 0,4, 1 és 1. Számunkra a 0,4 az érdekes, így a végeredmény 1-0,4=0,6.

Azaz 60%-nál lényegtelen, hogy 4-et vagy 6-ot dob a jelölt.

Magának ad 98-at, Charlotte-nak és Elizabeth-nek egyet-egyet, Bart-nek és Danielnek semennyit.
Levezetés:

• Ha az első 4 kalóz halott, akkor az ötödiké a teljes zsákmány. Ez tehát nem érdeke a többieknek.
• Ha az első 3 kalóz halott, akkor a negyedik tesz egy 100:0 javaslatot, amit 1:1 arányban elfogadják, így a teljes zsákmány az övé.
• Ha az első 2 kalóz halott, akkor ha a harmadik is meghal, akkor neki nem jut semmi. Így bármennyit is kap, neki érdeke megszavazni. Így egy 99:0:1 arányt meg fog szavazni a harmadik és az ötödik is.
• Ha az első kalóz halott, akkor tudjuk, hogy ha a második is meghal, akkor 99:0:1 lesz az eredmény. Így elég meggyőznie a negyedik kalózt, és tennie egy 99:0:1:0 ajánlatot, amit 2:2-re meg fognak szavazni.
• Így az első kalóz azt látja, hogy ha ő meghal, akkor a harmadiknak és az ötödiknek semmi sem jut. Tesz egy ilyen ajánlatot: 98:0:1:0:1, amit az első, a harmadik és az ötödik kalóz meg fog szavazni.

Mindegyik számhoz rendeljünk egy valószínűséget, hogy mekkora eséllyel választjuk azt a számot. Tehát létre kell hoznunk egy szigorúan monoton növekvő függvényt, ami a pozitív valós számok halmazát képezi a (0,1) intervallumra: $\mathbb{R}^+\to(0,1)$. Ha a borítékban $x$ szám van, akkor $p_x$ valószínűséggel fogadjuk el, és $1-p_x$ eséllyel a másikat.
Tegyük fel, hogy az egyikben $a$ van, a másikban $b$, és $a>b$. 50% eséllyel nyúlunk az $a$-t tartalmazó borítékhoz; ez esetben $p_a$ eséllyel választjuk azt. Ugyancsak 50% eséllyel nyúlunk a $b$-t tartalmazó borítékhoz, és ez esetben $1-p_b$ eséllyel választjuk az $a$-t tartalmazót. A kettőt összegezve, annak az esélye, hogy az $a$-t választjuk:

$\frac{1}{2}\cdot a + \frac{1}{2}\cdot (1-p_b) = \frac{1}{2}\cdot a + \frac{1}{2} - \frac{1}{2}\cdot p_b = \frac{1}{2} + \frac{1}{2}\cdot (p_a - p_b)$

Mivel a $p(x)$ függvény szigorúan monoton növekvő és $a>b$, ezért $p_a > p_b$, amiből az is következik, hogy $\frac{1}{2}\cdot(p_a-p_b)>0$, azaz $\frac{1}{2} + \frac{1}{2}\cdot(p_a - p_b) > \frac{1}{2}$. Ezzel a stratégiával tehát 50%-nál nagyobb eséllyel választjuk a nagyobbat.

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.

A feladatra egy 6 kérdéses kombinatorikai megoldást adunk. Vegyük az A, B, C, D, E és F értékeket, és válasszunk ki elem hármasokat! Egy 6 elem halmazból 3 elemet $\frac{6\cdot 5\cdot 4}{3\cdot 2\cdot 1} = 20$, azaz húszféleképpen tudunk kiválasztani. Itt már sejthető, hogy nem véletlen az, hogy András 1-től 20-ig gondolhatott egy egész számra. Feleltessünk meg minden számnak egy-egy betűkombinációt:

• 1: ABC
• 2: ABD
• 3: ABE
• 4: ABF
• 5: ACD
• 6: ACE
• 7: ACF
• 8: ADE
• 9: ADF
• 10: AEF
• 11: BCD
• 12: BCE
• 13: BCF
• 14: BDE
• 15: BDF
• 16: BEF
• 17: CDE
• 18: CDF
• 19: CEF
• 20: DEF

A 6 kérdést pedig képezzük a következőképpen. Az első legyenek azok a számok, melyekben szerepel A, a második az, melyben szerepel B stb. Így a 6 kérdés az alábbi:

• A: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
• B: {1, 2, 3, 4, 11, 12, 13, 14, 15, 16}
• C: {1, 5, 6, 7, 11, 12, 13, 17, 18, 19}
• D: {2, 5, 8, 9, 11, 14, 15, 17, 18, 20}
• E: {3, 6, 8, 10, 12, 14, 16, 17, 19, 20}
• F: {4, 7, 9, 10, 13, 15, 16, 18, 19, 20}

Akármelyik számra is gondolt András, Csaba pontosan 3 igen választ, azaz 3 halmazt kap. Tetszőleges 3 halmaznak pontosan egy metszete van.

Válassz ki 20 darabot, és fordítsd meg őket! (Gondold végig, hogy akármennyi érme is van az ezüst oldalával fölfelé a kiválasztottak között, ez minden esetben helyes megoldást ad!)

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.

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.

A fenti összeget integrállal közelítve: $\int_{51}^{100}\frac{1}{x}\,dx$, általánosítva $\int_{n+1}^{2n}\frac{1}{x}\,dx$. A primitív függvény $\ln x$, a határozott integrál tehát $\ln 2n - \ln (n+1) = \ln 2 + \ln n - \ln (n+1) \rightarrow \ln 2$, ha $n$ tart végtelenbe. A nyerési esély tehát $1-\ln 2$, azaz kb. 30,685%.

Belátható, hogy legfeljebb egy olyan ciklus lehet, ami hosszabb 50-nél. Ez esetben úgy kell felcserélni kettőt, hogy ez a hosszú kör két közel egyenlő részre szakadjon. Ha pl. 60 hosszú a ciklus, akkor az elsőt és a 31. elemet kell felcserélni.

Választanak egy véletlen egész számot, és azt hozzáadják a dobozok sorszámához úgy, hogy a túlcsordulásnál 1-től veszik. Ha pl. a választott szám 5, akkor az 1-esből lesz a 6-os a 2-esből a 7-es, a 95-ösből a 100-as, a 96-osból az 1-es, a 100-asból pedig az 5-ös. Ez alapján tehát képzeletbe átsorszámozzák a dobozokat. Ez esetben visszaáll az esély a fentire.

Meglepő, de 50 hét után minden férj rá fog jönni arra, hogy őt megcsalják. Gondolatmenet:

• Ha egyetlen házaspárról lenne szó, akkor a férj a következő vasárnapi szentmisén felállna.
• Ha két házaspárról lenne szó, akkor jelöljük a férjeket A-val és B-vel. Mivel A meg van arról győződve, hogy őt nem csalják meg, arra vár, hogy a következő vasárnap B feláll, és kijelenti, hogy őt megcsalják. Ez viszont nem következik be. Ugyanekkor B is arra vár, hogy A álljon fel. Viszont mivel egyikük sem állt fel, a következő héten mindketten fel fognak állni.
• Ha három házaspárról lenne szó, akkor jelöljük a férjeket A-val, B-vel és C-vel. A C a fenti logikával arra számít, hogy a második vasárnap A és B feláll. Mivel ez nem következett be, rájön, hogy őt is megcsalják, így a harmadik héten ő fel fog állni. De hasonló gondolatmenettel az A és a B is fel fog állni.
• Négy házaspár esetén a fenti gondolatmenetet követve mindenki feláll a negyedik héten.
• Öt házaspár esetén, az ötödik, hat házaspár esetén a hatodik, hét házaspár esetén a hetedik héten stb.
• Ötven házaspár esetén az ötvenedik héten fog mindenki felállni, és kijelenteni, hogy őt megcsalják, így a pap 50 hét elteltével eléri a célját.