Zadanie
Milý denníček,
ako sa ukázalo, babička „červenej čiapočky“ býva v paneláku, takže len jej adresa mi je nanič.
Babičkin panelák má prízemie a \(n\) poschodí. Medzi poschodiami sa dá chodiť po schodisku. Babičke trvá prekonanie vzdialenosti medzi dvoma susednými poschodiami konštantne celočíselný počet \(v\geq1\) sekúnd a prechod zo schodiska do vlastného bytu opäť celočíselný počet \(h\geq1\) sekúnd. Ja však tieto konštanty nepoznám.
V košíku „červenej čiapočky“ však bol špeciálny ďalekohľad, ktorým môžem každú sekundu sledovať jedno konkrétne poschodie paneláku. Kvôli stenám a iným zábranám však ďalekohľadom nedovidím na schodisko – to znamená, že babičku uvidím na prízemí a potom až vtedy, keď sa na svojom poschodí poberie do svojho bytu.
Uvidel som babičku vojsť na schodisko. Vzhľadom na \(n\) nájdite najmenšie možné \(h\) také, že viem s istotou určiť, kde babička býva, bez ohľadu na hodnotu \(v\).
Uvedomme si najprv, čo sa vlastne snaží vlk dosiahnuť. Snaží sa pozorovať poschodia tak, aby zaručil, že babičku niekedy uvidí. Potom bude vedieť, že na tom poschodí býva. Nemôže sa ale stať, že by zistil, kde babička býva, aj bez toho, aby ju priamo uvidel? Napríklad že bude pozorovať všetky poschodia až na jedno, a pokiaľ ju neuvidí, vie, že na tom jednom býva? Nie, pretože kým babičku neuvidí, nemôže si byť istý, že to nebude len tým, že babička ešte na poschodie nedorazila, a teda ľubovoľný tip, ktorý spraví, môže byť nesprávny...
Teraz teda poďme na odhad odpovede samotný: Ak nepoznáme hodnotu \(v\), babička sa vie na poschodí číslo \(k\) ukázať po ktoromkoľvek násobku \(k\) sekúnd. Inak povedané, pre poschodie s číslom \(k\) platí, že po uplynutí nejakého násobku \(k\) sekúnd existuje také číslo \(v\), že babička sa na tom poschodí teraz objaví. To znamená, že po uplynutí \(n!\) sekúnd sa môže babička ukázať na ľubovoľnom poschodí, a až do tohto momentu nemusíme vôbec tušiť, kde sa nachádza. Predstavme si, že babička bude potom na chodbe menej ako \(n\) sekúnd. V tomto prípade sa určite počas týchto menej než \(n\) sekúnd nestihneme pozrieť na každé poschodie, a keďže babička môže byť na ktoromkoľvek, nemáme záruku, že ju uvidíme. Preto vlk stratégiu pre \(h < n\) nemá.
Ukážme teraz, že stačí nech \(h = n\), aby vlk vedel víťazstvo zaručiť. Naozaj jednoducho, stačí mu prejsť v priebehu \(n\) sekúnd všetky poschodia, a toto opakovať, kým babičku neuvidí. Babička sa nikdy nestihne prešmyknúť, keďže na každé jedno poschodie sa vlk pozrie každú \(n\)-tú sekundu, a teda nikdy sa nenájde \(n\) po sebe idúcich sekúnd, kedy vlk nejaké poschodie nevidí a babička by sa tam mohla vtedy objaviť bez povšimnutia. Preto vlk má stratégiu pre \(h \geq n\).
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.