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.

Jelöljük a két szereplőt A-val és B-vel. Vegyük észre, hogy összesen négyféle lehetőség van. Ezeket rendezzük táblázatba:

Mivel két esetben szerepel a nem válasz, melyek közös tulajdonsága az, hogy A lovag, így elmondható, hogy ebből a beszélgetésből azt tudhatjuk biztosan, hogy A lovag.

Tehát ezzel a kérdéssel valójában bárkiről megtudhatjuk, hogy lovag-e, vagy lókötő.

Próbáljuk meg megoldani az előző módszerrel! A 10 ember 10! = 3.628.800 féleképpen állhat sorban. Mivel a lovagok és a lókötők belső sorrendjét nem különböztetjük meg, ezt el kell osztani kétszer 5!-ral: $\frac{10!}{5!\cdot5!} = 252$. Tehát a feladat elméletileg megoldható úgy, hogy felrajzolunk egy 252 sorból és 22 oszlopból álló táblázatot. Ez nyilván nem életszerű.

Ehelyett nézzük meg, hogy mi történik, ha a kérdést lovag kapja, és mit, ha lókötő!

Ebből megállapíthatjuk, hogy a lovagok továbbítják a választ, a lókötők pedig megfordítják. Összesen tehát van 5 továbbítás és 5 megfordítás, melyek belső sorrendje mindegy. Mivel páratlan számú fordítás van, ha a végén a válasz igen, akkor az első ember lókötő, ha pedig nem a válasz, akkor lovag.

• Kezdjük a tizedikkel! Ő valójában azt állítja, hogy mindenki lókötő. Ez csak úgy lehetne igaz, hogy ő maga is lókötő, viszont akkor nem mondhatja igazat. Az állítás tehát nem igaz, azaz ő lókötő.
• Most nézzük meg a sorban első ember állítását! Mivel a tizedik ember lókötő, igaz az az állítás, hogy legalább egyvalaki lókötő, tehát a sorban első helyen álló egy lovag.
• A következő lépésben nézzük meg a kilencediket! Azt állítja, hogy legalább kilencen lókötők. Mivel az elsőről tudjuk, hogy lovag, az állítás csak úgy lehet igaz, hogy ő maga is lókötő. Ez esetben viszont nem mondhat igazat, tehát ő lókötő.
• Most nézzük meg a másodikat! Mivel a kilencedikről és a tizedikről tudjuk, hogy lókötő, ezért a második igazat mondott, azaz ő lovag.

A sort folytatva:

• A nyolcadik lókötő.
• A harmadik lovag.
• A hetedik lókötő.
• A negyedik lovag.
• A hatodik lókötő.
• Az ötödik lovag.

Összesen tehát 5 lovag és 5 lókötő van.

A válasz 1/2. A dolog ugyanis eldől, ha valaki, aki véletlenszerűen választ, vagy az elsőként beszálló utas helyét választja (ez esetben minden további beszálló a saját helyére ül), vagy az utolsóként beszálló utas helyét foglalja el (ez esetben az utolsóként felszálló utas nyilván nem tud a saját helyére ülni). Abban a pillanatban, amikor ez bekövetkezik, 1/2 az esélye annak, hogy az elsőként beszálló utas helyét foglalja el, és szintén 1/2 annak, hogy az utolsóét.

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.

Sorszámozzuk be a lépcsőfokokat fentről. A legfelső, Mehemed számára győzelmet jelentő lépcsőfok legyen az 1-es, eggyel alatta a 2-es stb. A katonák értéke legyen ½ⁿ, ahol n a lépcsőfok sorszáma. Mehemednek az a legjobb stratégiája, ha igyekszik úgy kettéosztani a katonáit, hogy a kettő különbsége a lehető legkisebb legyen, Hunyadinak pedig az, hogy a nagyobb értékű csapatot kaszabolja le. Mehemednek akkor van nyerési stratégiája, ha a katonák összértéke >=1, Hunyadinak pedig akkor, ha ez <1. A gondolatmenet kulcsgondolata: minden egyes lépésben megduplázódik az élve maradt katonák értéke.

Vegyük a következő logaritmus azonosságot:

$\log_ab = \frac{\log_nb}{\log_na}$

Ezt alkalmazva:

$\log_23\cdot\log_34\cdot\log_45\cdot\dots\cdot\log_{1023}1024 = \frac{\log_n3}{\log_n2}\cdot\frac{\log_n4}{\log_n3}\cdot\frac{\log_n5}{\log_n4}\cdot\dots\cdot\frac{\log_n1024}{\log_n1023} = \frac{\log_n1024}{\log_n2} = \log_21024 = 10$

A megoldás tehát 10.