10. príklad - Vzorové riešenie

Tento príklad bol fakt ťažký. Nikomu sa nepodarilo vyriešiť ho na plný počet bodov, aj keď viacerí ste od toho nemali ďaleko (fun fact: z vašich riešení by sa dokopy dalo vyskladať 10-bodové, čiže každému do úplného riešenia chýbalo niečo iné, ale na každý potrebný krok k riešeniu prišiel aspoň niekto :)).

Na druhej strane, pri takýchto príkladoch dokáže veľmi pomôcť skúsenosť a nejaká všeobecná predstava o tom, ako k takýmto príkladom vôbec pristupovať. Tento vzorák teda bude vyzerať tak, že si vysvetlíme, ako takéto úlohy riešiť vo všeobecnosti a akými úvahami sa dalo dôjsť k riešeniu. Len malá časť z toho je samotné riešenie (to, čo máte vy odovzdať), takže na konci si zhrnieme, čo z toho tvorí samotné riešenie, bez tej omáčky okolo. Ak vás zaujíma len to, môžete kľudne preskočiť až tam, ale ak ste úlohu skúšali vyriešiť a nevedeli ste si rady, môže byť fajn prečítať si to celé.

Najprv si teda poďme povedať, čo presne od nás zadanie vlastne chce.

Čo vlastne chceme spraviť?

Zadanie sa nás pýta, na koľko najmenej pokusov vieme zistiť všetky hĺbky. To znamená, že musíme vlastne spraviť dve veci:

1. nájsť nejaký postup, ako tie hĺbky vieme zistiť (tomu sa hovorí konštrukcia, lebo chceme skonštruovať = nájsť riešenie), ale tiež
2. overiť a dokázať, že tento spôsob je naozaj najlepší, teda že sa to nedá na menej pokusov (tomu sa hovorí dolný odhad, lebo odhadneme, koľko najmenej pokusov budeme potrebovať).

Naozaj potrebujeme obe tieto veci: ak by sme mali len konštrukciu, tak je možné, že nie je optimálna, a dá sa to aj na menej pokusov, a ak máme dolný odhad, tak nevieme, či sa na toľko pokusov naozaj dajú zistiť všetky hĺbky (len že sa to nedá na menej). Veľa z vás napríklad spravilo konštrukciu na \left\lceil 2:3 \cdot n\right\rceil (to znamená najbližšie väčšie/rovné celé číslo ako 2:3 \cdot n​), ktorá fungovala, ale nebola optimálna. Na toľko pokusov by ste teda dolný odhad nenašli.

Napríklad, konštrukcia na n​ pokusov by mohla byť, že zistím hĺbku každej studne osobitne (ale tá nie je optimálna), a dolný odhad na 1 pokus môže byť, že keď neurobím žiadny pokus, tak predsa nič nezistím, takže je jasné, že treba aspoň jeden (ale na jeden pokus sa to väčšinou nedá spraviť). To nám moc nepovie. Keď ale máme dolný odhad aj konštrukciu na ten istý počet pokusov, vieme, že to musí byť najlepšie riešenie: na menej pokusov to nejde a na viac pokusov by to nebolo lepšie riešenie.

Vo veľa prípadoch sa konštrukcia a dolný odhad úplne líšia, takže sa oplatí vymýšľať aj písať úplne osobitne, aby bolo jasné, ktorá časť riešenia hovorí o čom. Tak, a teraz sa už pozrime na samotné riešenie tejto úlohy.

Dolný odhad

Začneme dolným odhadom. To síce väčšinou býva tá ťažšia časť riešenia, ale bez toho nevieme, na koľko krokov sa snažíme urobiť konštrukciu, takže ak aj nejakú vymyslíme, nebudeme vedieť, či je to to najlepšie riešenie. Na druhej strane, ak nájdeme dobrý dolný odhad, môžeme skúsiť k nemu vymyslieť konštrukciu, kde využijeme to, čo sme zistili pri dolnom odhade.

Chceme teda zistiť, v čom nás pravidlá skúšania obmedzujú, a z toho by sme chceli vedieť, že budeme určite potrebovať aspoň niekoľko pokusov. Čo teda môže byť problém? Vieme ľahko zistiť hodnoty všetkých hĺbok (tak, že hodíme pražce naraz do všetkých studní), ale tak nevieme od seba jednotlivé studne rozoznať. Skúsme teda prísť na to, ako musíme pražce hádzať, aby sme studne rozoznať vedeli.

Tu využijeme druhú vec, ktorú nám hovorí zadanie, že naraz musíme hádzať pražce vždy do susedných studní. To, či sú nejaké studne susedné, bude teda zjavne dôležité, tak sa pozrime na to, ako by sme dve susedné studne vedeli rozoznať. Keď sa pozeráme len na tieto dve studne, tak máme len týchto pár možností, ako vieme spraviť pokus:

1. pražec nehodíme pražec ani do jednej zo studní,
2. hodíme pražec do oboch studní, alebo
3. hodíme pražec len do jednej z nich.

Ak by sme robili pokusy 1 a 2, tak určite studne nevieme rozoznať, lebo pri každom pokuse buď nedostaneme ani jednu z ich hĺbok, alebo obe naraz, takže nevieme, ktorá hĺbka patrí ku ktorej studni. Pre každú dvojicu susedných studní teda musíme spraviť taký pokus, že hádžeme iba do jednej z týchto studní.

Čo to ale znamená? Keďže vždy hádžeme do susedných studní, každý pokus má nejaký ľavý a pravý koniec, teda miesto medzi dvomi studňami (alebo pred prvou/za poslednou studňou), a hádžeme pražce do všetkých studní medzi týmito koncami. Môžeme si to predstaviť ako na obrázku pre n=5:

Pre každý predel (teda miesto medzi dvomi studňami alebo na kraji) teda musíme urobiť taký hod, ktorý má jeden z koncov v tomto predeli. Prečo to platí medzi studňami, sme už vysvetlili, a platí to aj na kraji, lebo ako by sa na niektorom kraji nekončil žiadny úsek, tak potom vôbec nevieme hĺbku krajnej studne.

No a čo nám toto hovorí o počte pokusov? Tak každý pokus má konce v najviac 2​ nových predeloch a predelov je n + 1​ (na začiatku a potom za každou studňou), takže potrebujeme aspoň (n+1):2 pokusov. Keďže počet pokusov musí byť celé číslo, tak môžeme rovno povedať, že to musí byť aspoň \left\lceil\left(n+1\right):2\right\rceil, teda najbližšie väčšie alebo rovné celé číslo.

Konštrukcia

Tak teraz už vieme, že potrebujeme aspoň toľko pokusov, skúsme teda nájsť spôsob, ako na toľko pokusov aj naozaj zistiť všetky hĺbky.

Jedna možnosť je, že využijeme to, na čo sme prišli pri dolnom odhade. Keďže každý predel musí byť ľavý alebo pravý koniec nejakého pokusu, môžeme si povedať, že napríklad ľavá polovica predelov budú ľavé konce a pravá polovica pravé konce (ak je nepárny počet predelov, nevieme ich rozdeliť na polovicu, ten v strede teda bude aj aj).

Pokusy potom budú vyzerať tak, že spojíme prvý ľavý koniec s prvým pravým, druhý ľavý s druhým pravým, a tak ďalej, ako na obrázku pre n=5​:

Hĺbka nejakej studne v ľavej polovici je potom tá, ktorú sme dostali v pokuse začínajúcom tou studňou, ale nie v tom, ktorý začína o jednu studňu vpravo; pre studne v pravej polovici je to to isté, ale symetricky opačne: hĺbka nejakej studne je tá, ktorá je v pokuse končiacom tou studňou, ale nie v pokuse o jednu studňu vľavo. Môžeme to vidieť na obrázku:

Týmto spôsobom teda vieme zistiť všetky hĺbky, a keď ich spočítame, zistíme, že ich je naozaj práve \left\lceil\left(n+1\right):2\right\rceil.

Zhrnutie

Tak to bol dosť dlhý vzorák :) ale povedali sme tam veľa vecí, ktoré nakoniec neboli priamo dôležité pre riešenie. Teraz si teda zhrňme, čo boli tie veci, ktoré sme nakoniec využili. Riešenie, ktoré nám vy odovzdáte, by malo vyzerať ako nejaké takéto zhrnutie. Tak poďme na to:

Všetky hĺbky vieme zistiť na N=\left\lceil\left(n+1\right):2\right\rceil​ pokusov.

Dolný odhad: Nech predel je miesto medzi dvoma studňami alebo za studňou na kraji radu. Každý pokus teda tvoria studne medzi dvoma predelmi. Ak existuje predel, v ktorom nezačína ani nekončí žiadny úsek, potom všetky pokusy obsahujú buď obe studne vedľa tohto predelu, alebo ani jednu, a tak hĺbky týchto studní nevieme rozlíšiť. V každom predeli teda musí mať krajný bod nejaký pokus. Keďže predelov je n + 1​ a každý pokus má dva krajné body, pokusov musí byť aspoň N.

Konštrukcia: Očíslujme si studne 1 až n​. Pre každé k​ od 1​ po N​ urobíme pokus, v ktorom hodíme pražce do studní k, k+1, \ldots, k+\left\lceil n : 2 \right\rceil-1. Ak chceme zistiť hĺbku studne číslo k, je to presne tá hĺbka, ktorú dostanme v pokusoch číslo k-\left\lceil n : 2 \right\rceil+1 až k a v žiadnom inom. Budeme chcieť zisťovať studňu najviac n​, na ktorú potrebujeme pokusy s číslom najviac N​, takže tieto pokusy nám určite budú stačiť.

Tak, a to je všetko. Vidíte, nakoniec to riešenie nie je také hrozné, aj keď nie je ľahké na to prísť :)