1. Poriadny zástup

Ak máte akékoľvek otázky ohľadom tejto úlohy napíšte Paulínke na [email protected]

Plukovník Abaž očakáva návštevu svojho brata Žabu, a tak sa pre neho rozhodol spraviť veľkolepú vojenskú prehliadku. Všetkých svojich vojakov nechá nastúpiť do radu, aby Žaba videl, aká tvrdá disciplína uňho panuje.

Lenže, usporiadať prehliadku nie je také jednoduché, ako by sa mohlo zdať. Ak by sa dopredu postavil nejaký mamľas, mohol by úplne pokaziť obraz o celom Abažovom pluku. A to Abaž rozhodne nehodlá riskovať.

Našťastie, predvčerom mali vojaci vo svojich kasárňach priateľské majstrovstvá v pretláčaní. Takéto zápasy v pretláčani majú veľmi radi, lebo sa nikdy nestane, že by slabší vojak pretlačil silnejšieho. Na záver takýchto majstrovstiev sa preto vedia vojaci vždy jednoznačne zoradiť od najsilnejšieho po najslabšieho vojaka.

Lenže Abaž velí vojakom z dvoch kasární – južnej a severnej. A tak teraz stojí pred dvoma zástupmi vojakov. Jeden tvoria vojaci severnej kasárne zoradení od najsilnejšieho po najslabšieho a druhí tvoria vojaci vojaci južnej kasárne, taktiež v poradí od najsilnejšieho po najslabšieho.

Rád by z nich spravil jeden rad, v ktorom by boli všetci vojaci oboch kasární a tiež by boli usporiadaný od najsilnejšieho po najslabšieho. Jediné čo mu v tom vie pomôcť je to, že usporiada zápas medzi ľubovoľnými dvoma vojakmi. Takýto zápas však chvíľu trvá a keďže do príchodu Žabu už neostáva veľa času, potrebuje týchto zápasov spraviť čo najmenej.

Úloha

Ku každej z piatich podúloh napíšte slovný popis, v ktorom uvediete ako ste danú podúlohu riešili a dokážete, že vaše riešenie je správne. Nazabudnite na odhady počtu zápasov, ktoré musí Abaž vyhlásiť.

1. (1 bod) Abaž svojho brata dobre pozná a vie, že sa aj tak ďalej ako na začiatok radu nepozrie. Preto by chcel zistiť, ktorý z jeho vojakov je najsilnejší, aby ho mohol postaviť na začiatok. Na koľko najmenej zápasov to vie Abaž zistiť?

2. (2 body) Podceňovať Žabu sa však neoplatí. Čo ak sa pozrie nie len na prvého, ale na prvých troch vojakov? Akým spôsobom môže Abaž zistiť, ktorí traja vojaci z jeho pluku sú najsilnejší? Na koľko zápasov to vie dosiahnuť? A ak sa pozrieme na rady severnej a južnej kasárne (predpokladajme, že v každom je práve 10 vojakov), ktorí vojaci sú vôbec rozumní kandidáti na troch najsilnejších vojakov?

3. (4 body) Z centrály prišla informácia, že okrem Žabu príde na návštevu aj generálka Katka, ktorá je známa tým, že si poriadne vyobzerá všetkých vojakov. Abaž ich preto musí zoradiť všetkých od najsilnejšieho po najslabšieho.

   Predpokladajte, že v severnom aj južnom zástupe je 16 vojakov. Popíšte spôsob, akým má Abaž vyhlasovať súboje, aby sa mu podarilo usporiadať podľa sily všetkých vojakov. Koľko zápasov bude musieť spraviť v najhoršom prípade? Aký by bol počet zápasov, ak by v každom rade bolo \(n\) vojakov?

4. (3 body) Čo by sa stalo, ak by mal Abaž na starosti štyri kasárne, každú s 8 vojakmi, ktorí sú usporiadaní do štyroch zástupov od najsilnejšieho po najslabšieho? Akým spôsobom by mal usporadúvať zápasy, aby ich spravil čo najmenej a usporiadal všetkých vojakov podľa sily? Pokúste sa pri tom využiť riešenie podúlohy c). Vyskúšajte viacero možností, aby ste našli tú s najmenším počtom súbojov.

5. (5 bodov) Nanešťastie, vojakom sa podarilo zabudnúť ako dopadli v kasárňových majstrovstvách. Abaž má preto pred sebou 32 vojakov, o ktorých sile netuší vôbec nič. A jediné čo vie robiť je nechať zápasiť ľubovoľných dvoch vojakov. Ako má postupovať pri ich zoraďovaní? Koľko zápasov bude musieť vyhlásiť v najhoršom prípade? A koľko zápasov by potreboval, ak by bolo vojakov \(n\)?

   Riešenie za 5 bodov by pre 32 vojakov nemalo potrebovať viac ako 160 zápasov ani v najhoršom prípade.