Třetí série šestnáctého ročníku KSP

Celý leták, který posíláme také papírově, v PDF.

Řešení úloh

• 16-3-1: Fyzikova blecha
• 16-3-2: Historikova past
• 16-3-3: Genetikova evoluce
• 16-3-4: Ekonomova odměna
• 16-3-5: Botanikova setba
• 16-3-6: Matematikova sonda

---

16-3-1 Fyzikova blecha (Zadání)

---

Tak jak to všechno dopadlo… U některých řešení by se blecha urazila nebo dokonce přímo unudila, než by dostala řešení. Tím myslím především algoritmy s exponenciální časovou složitostí, už daleko lepší byly kvadratické a nejlepší algoritmy byly se složitostí O(N log N). A takový si zde ukážeme.

Jak tento bleší problém vyřešíme? Začneme tím, že si plošinky utřídíme podle y-ové souřadnice. Předpokládejme, že u konců každé plošinky víme, na jakou jinou plošinku z tohoto konce blecha spadne. Budeme probírat plošinky podle stoupající y-ové souřadnice a u každé plošinky si budeme u obou konců počítat nejkratší cestu na podlahu. To provedeme tak, že zkusíme ze zpracovávaného konce plošinky spadnout na nižší plošinku (víme na kterou). Protože plošinka, na kterou dopadneme, je níž než zpracovávaná, už u ní známe nejkratší cestu z obou konců – vybereme si, zda jít doleva nebo doprava, aby byla cesta co nejkratší.

Celý tento postup zvládneme v čase O(N), protože u každé plošinky uděláme jen konstantně mnoho operací (zjistíme na kterou plošinku spadneme, jak bude dlouhá cesta když po dopadu zahneme nalevo, jak bude dlouhá cesta když po dopadu zahneme napravo, vybereme minimum).

Jak tedy budeme u plošinky určovat, na jakou nižší blecha z jejího konce spadne? Použijeme k tomu statický intervalový strom. To je struktura, která si pro každý prvek s indexem 1 až P pamatuje nějaké číslo, přičemž P musí být pevné po celou dobu běhu programu. Intervalový strom umí dvě operace: zjisti hodnotu prvku i a nastav hodnotu prvků v intervalu i…j na co, obě v čase O(log N).

Předpokládejme, že už takovou strukturu známe. Použijeme ji tímto způsobem: Jednotlivé prvky intervalového stromu budou použité x-ové souřadnice plošinek (je jich nanejvýš 2N) a hodnota prvku i (i-tá nejmenší x-ová souřadnice) je číslo nejvýše umístěné plošinky, která se na této x-ové souřadnici vyskytuje. Abychom mohli x-ové souřadnice očíslovat, musíme si je za začátku opět setřídit.

Na začátku dáme do intervalového stromu jen podlahu. Probereme si plošinky opět podle vzrůstající y-ové souřadnice a u každého konce (souřadnice left_x,right_x; předpokládejme, že po očíslování mají indexy left_i,right_i) se intervalového stromu zeptáme, jaká je hodnota prvku left_i a right_i (0 znamená podlaha, jiné číslo je pořadové číslo plošinky). Tím jsme zjistili, na kterou plošinku spadne blecha z levého a pravého konce plošinky. Poté zpracovávanou plošinku „přidáme“ do intervalového stromu, čili (pokud zpracováváme i-ou odspoda) do intervalového stromu zapíšeme hodnotu i do prvků v intervalu left_i…right_i.

Pokud tedy zvládneme naimplementovat popsaný intervalový strom, máme řešení s časovou složitostí O(N log N), protože třídění nás stojí O(N log N) a dále zpracováváme N plošinek a každou v čase O(log N). Paměťová složitost je jako obvykle O(N).

Statický intervalový strom si můžeme představit jako dokonale vyvážený binární strom. Jednotlivé vrcholy odpovídají intervalům z rozmezí 1 až P tak, že listy tohoto stromu jsou jednotlivé prvky (odpovídají intervalům i…i) a každý vnitřní vrchol odpovídá intervalu, který je roven sjednocení intervalů synů tohoto vrcholu. Čili vrchol celého stromu odpovídá intervalu 1…P, jeho levý syn intervalu 1…⌊P/2⌋ a pravý syn intervalu (⌊P/2⌋+1)…P.

U každého vrcholu si budeme pamatovat jednak hodnotu h_i a jednak informaci p_i, zda hodnota h_i odpovídá všem prvkům na intervalu, který tento vrchol reprezentuje (u listů je to vždy true). Zjištění hodnoty nějakého prvku potom provedeme následovně: začneme ve vrcholu. Pokud je p_v true, vrátíme hodnotu h_v. Jinak si vybereme levého nebo pravého syna (podle indexu prvku, jehož hodnotu zjišťujeme), a rekurzíme (určitě se zastavíme, listy mají p_i na true).

Jak dopadne nastavení hodnoty prvků na intervalu i…j? Opět začneme ve vrcholu. Pokud interval, který zkoumaný vrchol v pokrývá, je podinterval i…j, nastavíme p_v na true a h_v na nastavovanou hodnotu. Jinak se spustíme na toho syna (případně na oba), jehož interval má neprázdný průnik s intervalem i…j. (Pozor: Bylo-li p_v true, je třeba nejprve rozdělit vrcholem reprezentovaný interval synům.)

Protože strom je dokonale vyvážený, má logaritmickou výšku. Obě operace závisí na výšce stromu (u nastavování intervalu je si to třeba rozmyslet - někdy se sice spustíme na pravého i levého syna, ale když to nastane, jednoho syna pokryjeme celého – nebudeme se z něj spouštět níže), mají tedy logaritmickou složitost.

Zbývá vyřešit jedinou drobnost – jak si rozumně vytvořit takový binární strom? Použijeme pro to pole o velikosti 2N. Řekneme, že prvek s indexem 1 odpovídá intervalu 1…P. Dále řekneme, že synové prvku i pokrývajícího interval left_i…right_i jsou 2i levý a 2i+1 pravý. Levý syn bude pokrývat interval left_i…⌊left_i+right_i)/2⌋, pravý syn bude pokrývat …(⌊left_i+right_i)/2⌋+1)…right_i. Tímto trikem můžeme chápat pole jako strom, přičemž jednotlivé intervaly, které vrcholy pokrývají, si počítáme až při průchodu tímto stromem/polem.

Program

Tomáš Vyskočil a Milan Straka

---

16-3-2 Historikova past (Zadání)

---

Nejprve se zamysleme nad tím, jak bychom úlohu řešili, kdyby v bludišti nepřekážel Minotauros. V tomto jednoduchém případě potřebujeme pouze najít nejkratší cestu ze startu k cíli.

Využijeme při tom algoritmus vlny. Představme si, že v prvním kroku vylijeme vodu na startovní políčko, což si na něm poznačíme například číslem 1. V druhém kroku nám voda přeteče do políček sousedících se startovním (samozřejmě těch, kde není zeď) a to si na nich poznačíme číslem 2. A tak dále, obecně v i-tém kroku označíme číslem i všechny dosud nezaplavené sousedy políček s číslem i-1. Zjevně číslo přiřazené políčku udává délku nejkratší cesty do něj. Samotnou cestu vypíšeme zpětným průchodem od cíle tak, že z políčka s číslem j popojdeme do libovolného souseda s číslem j-1, případně si můžeme pamatovat matici předchůdců, odkud do políčka voda natekla.

Vlastně se probíráme grafem, kde vrcholy (stavy bloudění) jsou všechny možné přípustné polohy Thesea, hrana mezi dvěma vrcholy vede pokud pozice v bludišti sousedí a hledáme v něm nejkratší cestu ze startu do cíle. Jak podobný přístup použít i za přítomnosti žravého Minotaura?

Stav bloudění je tentokrát určen jak polohou Thesea, tak polohou Minotaura. Všechny přípustné stavy jsou tedy dvojice (poloha Thesea, poloha Minotaura), kde ani jeden zrovna nestojí ve zdi a Minotaurus nežere Thesea. Jakmile se Theseus pohne, umíme jednoznačně určit v čase O(k), jak na to zareaguje Minotaurus. Opět tedy můžeme hledat nejkratší cestu v grafu, jehož vrcholy budou všechny stavy bloudění a hrana povede z (T,M) do (T',M'), pokud T' je sousedem T a Minotaurus na přesun Thesea do polohy T' zareaguje posunem z M na M'. Na tento graf (stavový prostor), kde cílové stavy jsou takové, ve kterých Theseus stojí v cíli, stačí pouze vypustit algoritmus vlny. (Graf si samozřejmě nemusíme pamatovat žádným z populárních způsobů uchovávání grafu v paměti, přecházet mezi vrcholy umíme jednoduše i bez konstrukce hran.)

Zbývá si pouze rozmyslet, jak vlnu efektivně naprogramovat. Zavedeme si frontu na vrcholy, ze který se bude rozlévat voda. Vždy vyzvedneme prvek ze začátku fronty, zaplavíme jeho dosud nezaplavené sousedy a zařadíme je na konec fronty. Tím si zaručíme, že na každý stav (kterých je nyní nejvýše (NM)²) při vlně sáhneme jen konstantněkrát. Přechod mezi dvěma stavy umíme vypočítat v čase O(k), zpětný výpis zvládneme v čase lineárním k počtu stavů, celkový čas výpočtu tudíž bude O(N² M² k). Potřebujeme si zapamatovat matici N×M s bludištěm, stavový prostor velikosti (NM)²) reprezentovaný čtyřrozměrným polem, kam si ukládáme čas zaplavení, stejně mnoho předchůdců pro výpis cesty a opět stejně velkou frontu. Celková spotřebovaná paměť tedy bude O(N² M²).

Program

Tomáš Valla

---

16-3-3 Genetikova evoluce (Zadání)

---

Většina z vás správně uhodla, že hledaná evoluce je vlastně minimální kostrou grafu, jehož vrcholy jsou jednotlivé druhy, hrany mezi nimi možné evoluční skoky a ohodnocení hran (vzdálenost mezi vrcholy) odpovídá počtu mutací mezi jednotlivými druhy.

Stačilo pak opsat kuchařku a řešení mžouralo na svět. Žel, jak při rodinné večeři u Blátošlapů vyšlo najevo, nikoliv optimální. Hned poté, co se Blátošlapovi podařilo umlčet nejmladšího Blátomarcka, (jsa genetikou dosud neinfikován, neustále cosi drmolil o povstávání z bláta), musel zažehnávat hádku s pubertálním vzdorem Blátoťapky - jeho jedinou zábavou toho roku bylo neustále rozvracet genetikův svatý svět (jde přeci o vývoj toho, kdo text čte, nikoliv jen o vývoj textu samotného…). Nejstarší Blátotlačka byla jediná, s kým byla ten den rozumná řeč - a jaká ! Ihned si všimla dvou detailů.

Časová složitost v kuchařce je tak veliká, hlavně kvůli setřídění všech hran a nenápadná zmínka o maximálním počtu sledovaných znaků, ji přivedla na myšlenku třídících algoritmů, které za určitých podmínek pracují rychleji (RadixSort, CountedSort, atd). Při troše péče se pak nechá časová složitost zmenšit až na kvadratickou vzhledem k počtu vrcholů.

Druhý podstatný detail - nepracujeme s obecným grafem, ale jen se speciální podtřídou grafů, kde je každý vrchol spojen s každým, čili počet hran je vždy O(n²). Díky tomu si při použití DFU můžeme dovolit investovat do slití dvou tříd čas O(n) (je to strom, slévat budu n-1 krát), tak abychom byli schopni zjistit reprezentanta třídy vždy v O(1) - nepotřebujeme pak žádné zrychlovací finty, které zachrání amortizovaný čas. Tím se můžeme vyhnout nabobtnalým zdrojákům, ve kterých se vrší chyba na chybě.

A jaké bude naše řešení: víme, že hran je O(n²) , takže je nepravděpodobné, že se někdy dostaneme pod tuto složitost. Nenecháme se zmást narafičenou kuchařkou a vzpomeneme/vyhledáme Prim-Jarníkův algoritmus, který lze implementovat v O(n²).

Jaká je jeho myšlenka: Budeme kostru budovat postupně, podle vrcholů (nikoliv hran). V každém kroku bude budovaný podgraf G souvislý a nebude obsahovat kružnice, tj. bude to strom. Z toho plyne, že po přidání posledního vrcholu budeme mít v rukou kostru původního grafu.

Indukční krok: Další vrchol vybírám z množiny sousedů budovaného podgrafu (tj. takové vrcholy, které sousedí v původním grafu s G, ale dosud do G nebyly zařazeny). Z této množiny vyberu ten, který je „nejbližší“ ke G, tj. vyberu vrchol, který v daném kroku zvýší celkový součet mutací v G minimálním možným způsobem.

V našem případě začneme budovat G vždy od vrcholu, který reprezentuje prvotního předka v evoluci, čímž zaručíme správné pořadí otec → syn při generování evoluce.

To, že je nalezená kostra vskutku minimální by se dokazovalo sporem, a zvídavější povahy nechť hledají např. letošní MOP, kde je důkaz proveden se vší parádou.

Implementační detaily: budeme zařazovat celkově n vrcholů, tedy pro každé zařazení smím spotřebovat maximálně O(n) času. Zavedu si pole min, které pro každý nezařazený vrchol, uchovává nejbližší zařazený(tj.již v podgrafu G). Vyhledání minima v tomto poli jistě v O(n) zvládnu. Aktualizaci pole po zařazení, znamená zkontrolovat, nemá-li nějaký nezařazený vrchol blíže k právě zařazenému - a to v O(n) zvládnu také.

Zjištění velikosti mutace mezi dvěma druhy (bits), je ekvivalentní zjišťování počtu jedniček v XORu znaků jednotlivých druhů. V našem řešení lineární vzhledem k počtu znaků - těch je ovšem konstantně mnoho, i ono proto trvá konstantní čas (existuje však také algoritmus logaritmický vzhledem k počtu znaků). Zjišťování vzdálenosti mezi dvěma vrcholy se bude vícekrát opakovat, takže by bylo možné výpočet urychlit zavedením pomocného pole pro spočtené výsledky. Odnesli bychom to však zhoršením paměťové složitosti ze současných O(n) na O(n²).

Program

Pavel Šanda

---

16-3-4 Ekonomova odměna (Zadání)

---

Většina z Vás sice neodsoudila Dlouhoprsta k smrti, ale zato ho odsoudila k chudobě. A ta je pro zloděje snad ještě horší než smrt. Avšak ne nadarmo se Dlouhoprst zove Dlouhoprstem – brzy přišel na to, jak piráty ožebračit.

Nejprve předpokládejme, že máme stříbrňáků nepočítaně, a zkusme zjistit, kolik nejméně jich potřebujeme k tomu, aby byl Dlouhoprstův návrh přijat. První důležité pozorování je to, že je-li P ≠ 1, tak Dlouhoprst přežije. Pokud Dlouhoprst zaplatí dost, může na svou stranu získat všechny piráty kromě toho s číslem P.

Nejprve si ukažme, jak bude situace vypadat pro malá P:

Pozn.: Poslední číslo na řádku je Dlouhoprstův zisk, –1=†.

Důležité je to, proč pirátům 1,2 stačí v případě P=5 pouze 2 stříbrňáky. Vzhledem k tomu, že situace může v případě P=4 dopadnout dvěma způsoby (buď dostane zaplaceno 1. nebo 2. pirát), nemají tito piráti jistotu, že ony 2 stříbrňáky získají. Proto se při P=5 spokojí s dvěma stříbrňáky (ovšem jeden by jim nestačil - mají naději na dva).

Pokud budeme pokračovat v rozboru dále, zjistíme, že kromě počátačních případů (P ≤ 3) je optimální řešení takovéhle: chceme, aby pro Dlouhoprsta hlasovalo ⌈P/2⌉ pirátů. Pirátovi P nedáme nic, pirátovi P-1 dáme 1 stříbrňák a ze zbylých pirátů 1…P-2 vybereme libovolných ⌈P/2⌉-1 a dáme každému z nich 2 stříbrňáky (pro jednoduchost vybereme např. prvních ⌈P/2⌉-1 pirátů). Celkem použijeme 2(⌈P/2⌉-1)+1 = 2⌈P/2⌉-1 stříbrňáků.

Pokud je tedy S ≥ 2⌈P/2⌉-1, umíme úlohu vyřešit dokonce v konstantním čase a prostoru. Případ P ≤ 3 vyřešíme tabulkou a pro ostatní hodnoty P použijeme popsané rozdělení (pozor na to, že nesmíme vypsat počet stříbrňáků pro každého piráta – to by mělo složitost O(P)).

Situace začne být složitější, je-li S menší než 2⌈P/2⌉-1.
Není totiž pravda, že pak nikdy neexistuje řešení. Např:

Ačkoli se piráti dělí o jediný stříbrňák, pokud je jich 8, Dlouhoprst může přežít. Využije toho, že pro něj zadarmo budou hlasovat piráti 6,7,8, kteří jinak zemřou.

Řešení situace, kdy je S malé, založíme na dynamickém programování. Budeme postupně řešit situaci pro rostoucí P až do zadaného. U každého piráta si budeme pamatovat, jaký počet stříbrňáků má „jistý“ a zda má šanci získat víc než svou „jistotu“. Všimněte si, že dále popsaný postup funguje pro libovolná S, mohli bychom tak řešit (byť pomaleji) i případ dostatečně velkého S.

Řekněme, že známe řešení pro P-1 pirátů a zajímá nás řešení situace s P piráty. Hledáme ⌈P/2⌉ pirátů, kterým zaplatíme nejméně. Pokud budeme chtít, aby pro Dlouhoprsta hlasovali všichni piráti, kteří mají jistých R stříbrňáků, nabídneme jim R+1 stříbrňáků a upravíme jejich „jistotu“. Pokud budeme chtít, aby hlasovali jenom někteří piráti z těch s „jistotou“ R stříbrňáků, nabídneme jim taktéž R+1 stříbrňáků. Nezměníme ovšem jejich „jistotu“, jenom si u nich poznamenáme, že mají šanci získat více než svou „jistotu“.

Nyní si všimneme důležité věci: žádný pirát (kromě toho, který právě navrhuje rozdělení) nemůže dostat více než dva stříbrňáky, neboli „jistota“ každého piráta je menší než dva. To platí proto, že aby měl nějaký pirát jisté dva stříbrňáky, musel by někdy Dlouhoprst nabídnout dva stříbrňáky všem pirátům, kteří měli jistý jeden. Uvažujme nyní situaci, kdy Dlouhoprst poprvé nabízí dva stříbrňáky všem pirátům, kteří mají jistý jeden. V tuto chvíli jsou ještě „jistoty“ všech pirátů menší než dva. Když už by ovšem Dlouhoprst uplácel piráty s jedním jistým stříbrňákem, piráty s nižší „jistotou“ by už museli být uplaceni (jsou totiž levnější). Tedy piráti s „jistotou“ menší než jedna jsou již uplaceni, všichni piráti s „jistotou“ rovnou jedné jsou upláceni a žádní jiní piráti neexistují. Čili Dlouhoprst by uplácel všechny piráty! To je ovšem spor s tím, že Dlouhoprst chce uplatit jen ⌈P/2⌉ pirátů.

Pokud tedy zjišťujeme řešení situace s P piráty ze situace s P-1 piráty, nejprve zjistíme, kterým pirátům bude Dlouhoprst platit. Vzhledem k tomu, že „jistoty“ všech pirátů jsou menší než dva, dokážeme to v konstantním čase (pokud si pamatujeme, kolik pirátů má „jistotu“ rovnu -1 (smrt), kolik jí má nulovou a kolik pirátů má jistý 1 stříbrňák). Poté můžeme jedním průchodem nad piráty 1…P upravit jejich „jistoty“ a šance na získání většího počtu stříbrňáků. To celé zvládneme v čase O(P).

Celý algoritmus bude fungovat tak, že bude zjišťovat, jak dopadnou návrhy pro 1,2,…,P pirátů a poslední z těchto návrhů vypíše. Při výpisu všem pirátům, kteří nemají šanci na nic víc než jejich „jistotu“, zaplatíme. Ovšem pirátům, kteří mají naději na víc, platíme o jeden stříbrňák víc a nemusíme jim platit všem, jenom tolika, abychom uplatili celkem ⌈P/2⌉ pirátů.

Celkem P-krát opakujeme postup o složitosti O(P) a poté výsledky v čase O(P) vypíšeme, čili celková časová složitost popsaného algoritmu je O(P²). Paměťová složitost je O(P). A ačkoliv popsaný algoritmus používáme jen v případě, kdy S < 2⌈P/2⌉-1, funguje korektně pro všechna S.

Program

Milan Straka

---

16-3-5 Botanikova setba (Zadání)

---

V jednorozměrném případě je úloha poměrně jednoduchá:

Udržujeme si dvě proměnné (a_x, b_x), které nám říkají odkud a kam sahá zkoumaný úsek. Pokud úrodnost ve zkoumaném úseku je větší než prozatímní největší, upravíme ji. Pokud je naopak úrodnost menší nebo rovna nule, nevyplatí se nám tento úsek použít, a je lepší na něj zapomenout (tj. a_x = b_x+1). Pokud je součet prvků aspoň jedna, vždy se nám vyplatí a_x ponechat a tyto prvky přidat k naší zkoumané oblasti. Časová složitost tohoto je O(n).

Nyní převedeme dvojrozměrný případ na jednorozměrný:

Projdeme všechny horní řádky a_y. Nyní budeme procházet všechny spodní řádky b_y, a zároveň si udržovat součet všech prvků ve sloupečcích v poli c. Časová složitost této části je O(n²). Na pomocné pole c je nyní možné aplikovat jednorozměrné řešení. Celková složitost tak bude O(n³).

Při implementaci je trochu potřeba dát pozor na matici plnou záporných čísel, ale v této implementaci jsme to zvládli bez speciálního kódu. (Takový případ jde řešit v O(n²), ale kdo by sázel rostlinky se záporným ziskem?)

Vhodným předotočením matice je možné složitost vylepšit pro nečtvercové matice na O(m*n*min(m,n)) (s díky Martinu Dobrouckému).

Program

Pavel Machek

---

16-3-6 Matematikova sonda (Zadání)

---

Kdyby náš matematik byl věděl, jaké nesnáze řešitelům KSP způsobí, asi by kosmický výzkum pověsil na hřebík a raději by pořádal přednášky o pravděpodobnosti nebo okopával na zahrádce integrály. Přišla nám totiž necelá dvě řešení. My si ukážeme celé třetí. Držte se, jedeme s kopce!

Pokud se matematik rozhodne používat pravděpodobnostní strategii, bude jeho (pravda, místy poněkud jednotvárný) život probíhat takto: Osud si nejdříve rozmyslí, kolik pokusů se sondami kupovanými na místním jarmarku bude neúspěšných (to si označíme t-1, čili t-tá kupovaná sonda by už uspěla). Následně matematik spustí svůj algoritmus a ten se v i-tém tahu s pravděpodobností p_i rozhodne, že nastal čas sondu si za K grošů vyrobit, nebo naopak (tedy s pravděpodobností 1-p_i) si ji zajít na jarmark za 1 groš koupit. V průměrném případě tedy za sondy zaplatí

(první suma odpovídá případům, kdy si matematik koupí sondu v i-tém kroku, čili si ji (i-1)-krát koupí za 1, pak zaplatí K za výrobu svépomocí a pak už nic; druhá suma popisuje případ, kdy si ji vždy koupil). Optimální strategie (kterou by použil každý správný věštec) by stála O_t = min(t, K) (pokud je t<K, vyplatí se sondy kupovat, jinak si ji hned na začátku za K vyrobit).

Všimněte si, že každá volba čísel p₁,p₂,p₃,… , kde ∀i  p_i ∈< 0,1 > a ∑_i p_i=1, odpovídá nějaké pravděpodobnostní strategii, a naopak každá p. s. se dá nějakou takovou posloupností popsat. My tedy chceme najít taková p_i, aby relativní cena naší strategie vůči optimální (ať už je na nás Osud sebevíc zlý) – tedy C=max_t A_t/O_t – byla nejmenší možná.

Nejdříve dokážeme, že pro i>K se vyplatí p_i ponechat nulové: Pokud t > t^′≥ K, je také A_t ≥ A_t^′, protože při přechodu od A_t k A_t^′ přejdou v ♥ některá p_i (pro t ≥ i > t^′) z první sumy do druhé, takže se místo K+i-1 budou násobit t^′, což je číslo menší. Pokud bychom ale libovolné p_i>K vynulovali a jeho původní hodnotu přičetli k p_K (tím zůstane ∑_i p_i zachována), všechna A_j<K zůstanou nezměněna, A_{j≥ i} se sníží a A_j pro K≤ j < i se sice zvýší, ale jelikož A_j/O_j = A_j/K ≤ A_i/K = A_i/O_i, určitě si tím nepohoršíme. Takto můžeme postupně vynulovat všechna p_i>K a získat stejně dobrou nebo dokonce lepší strategii.

Situace se tím nekonečněkrát zjednoduší – místo nekonečně mnoha p_i teď stačí najít pouze p₁,… ,p_K a také není třeba uvažovat t>K, jelikož pro taková t se jak náš, tak optimální algoritmus chovají stejně jako pro t=K.

Pokud má naše strategie mít relativní cenu C, musí tedy pro všechna t≤ K být A_t ≤ C·t, což si rozepíšeme pomocí ♠ a místo C použijeme c=C-1, aby se nám lépe počítalo:

Bez újmy na obecnosti budeme předpokládat, že pro všechna t dokonce nastává rovnost (vyzkoušejte si, že kdyby nenastávala, mohli bychom p_i trochu pozměnit a buďto zvětšit počet rovností, nebo dokonce snížit c). Pokud si pak do této rovnosti dosadíte t=1, vyjde, že:

A pokud místo toho rovnost pro t=j+1 odečtete od rovnosti pro t=j, dozvíte se, že:

čili

Tuto rovnost opět odečteme od sebe samé pro j-čka lišící se o jedničku a konečně dostaneme rozumný rekurentní vztah:

z nějž plyne, že:

Tím jsou pro každé c všechna p_i jednoznačně určena, ovšem obvykle nebudou dávat korektní rozdělení pravděpodobností. Musíme proto c nastavit tak, aby platilo:

Jenže jak každý správný matematik ví už od kolébky, výraz (1+1/K)^K se pro rostoucí K blíží k Eulerovu číslu e ≈ 2.718281828459045 a stejně tak (1+1/(K-1))^K, kterýžto výraz je dokonce i pro malá K zaručeně ≥ e. Platí tedy, že c ≤ 1/(e-1), a tudíž C = 1+c ≤ e/(e-1) ≈ 1.5819767068693264. Takže jsme našli pravděpodobnostní strategii pro pořizování kosmických sond, podstatně lepší, než je ta deterministická, a dokonce jsme dokázali, že taková strategie je nejlepší možná. (Tedy alespoň za předpokladu, že Osud a bohyně Fortuna stanovují své úradky „offline“, čili nezávisle na našich experimentech. Zkuste si rozmyslet, že nad online Osudem již neuhrajeme více než deterministický algoritmus.)

Tak končí naše malá sonda do života matematiků. A promiňte, už musím letět, právě mi přistává létající talíř výhodně pořízený od místního hokynáře…

Martin Mareš

Menu