Kategória: Matek feladatok.
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.)
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.
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?
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!)
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?
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?
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?
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%.
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?
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.
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?
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.
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?
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.
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ő?
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:
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 |
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.
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ő?
Először elemezzük az első kérdést! Ha pusztán azt tennénk fel, hogy lova-e, akkor akár lovagról van szó, akár lókötőről, azt válaszolná, hogy igen, és ennek nem lenne információértéke. Elemezzük a ténylegese kérdést:
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 |
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ő!
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 |
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.
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?
- 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.
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?
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.
Logaritmus szorzat
Mennyi lesz a következő szorzat eredménye?
$\log_23\cdot\log_34\cdot\log_45\cdot\dots\cdot\log_{1023}1024$
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.
Cikcakk vonal
Milyen hosszú az alábbi ábrán a fekete cikcakkos vonal?
(A feladat forrása: https://brilliant.org/courses/puzzles-100/chapter-4/infinite-skyline/)
Lentről indulva az első vízszintes és függőleges szakasz hossza 3+2=5. Ezt követően a vízszintes szakasz hozza megegyezik az azt megelőző függőleges szakasszal, míg a függőleges szakasz hossza az azt megelőző vízszintes szakasz kétharmada. Számoljuk ki a következőt: 3 + az egyenlő szárú háromszögek szárai, tehát 3 + 2*2 + 2*(4/3) + 2*(8/9) + 2*(16/27) + … = 3 + 4 * (1 + 2/3 + 4/9 + 8/27 + …). Tekintsük a zárójeles részt: ez nem más, mint egy harmonikus sor, melynek összege 1/(1-r). Itt r=2/3, tehát a sorösszeg 1/(1-2/3) = 3. Ezt visszahelyettesítve, az eredmény = 3+4*3 = 15.
Az előző megoldáshoz kellett a mértani sor képlete. Enélkül is meghatározható az eredmény.
A barna nagy háromszög két befogója egyforma hosszú. Jelölje ezt x. Mivel a teljes (tehát a kék átlójú) háromszög és a 3 és 2 befogó hosszúságú háromszög hasonló, a befogókra felírhatjuk a következő arányosságot: 3 : 2 = (3+x) : x. Ezt átrendezve: 3x = 6 + 2x, amiből x=6.
A cikcakk vonal két fajta komponensből áll, vízszintesekből és függőlegesekből. A vízszintes komponensek összhossza megegyezik a nagy háromszög alsó szárával (ami 3+x=3+6=9), míg a függőleges komponensek összhossza megegyezik a nagy háromszög jobb oldali szárával (ami x=6). Így az eredmény 9+6=15.
Kockadobós nyeremény
Egy szabályos 6 oldalú dobókockával dobunk. Ha 1-est dobunk, akkor megfeleződik az eddig összegyűjtött pénzünk. Ha legalább kettest, akkor annyi egységnyi pénzt kapunk, amekkora a dobásunk értéke. A dobások száma tetszőleges. Akkor szállunk ki a játékból, amikor a következő dobás várható nyeresége már negatív. Mekkora összegnél következik ez be?
A következő lépés várható nyeresége az alábbi:
$\frac{1}{6} \cdot \frac{-x}{2} + 2 \cdot \frac{1}{6} + 3 \cdot \frac{1}{6} + 4 \cdot \frac{1}{6} + 5 \cdot \frac{1}{6} + 6 \cdot \frac{1}{6} = \frac{-x}{12} + \frac{20}{6}$
Ez a következő x értékig pozitív:
$\frac{-x}{12} + \frac{20}{6} > 0$
$-x + 40 > 0$
$x < 40$
A megoldás tehát 40.
Ami az érdekes ebben az az, hogy valójában ennél magasabb nyereséget is el tudunk érni. Tehát ha a dobás kellően gyorsan történik, pl. véletlen szám generátorral, akkor belőhetünk egy pár százas nyereséget, és akkor állunk meg, ha elértük. 40-nél csak az van, hogy a várható növekmény negatívba fordul (40-nél még pont 0).