8. Kilá Maťko Skúša vzorové riešenie



Skúsme sa na začiatok zamyslieť nad jednoduchšou úlohou. Čo ak by Maťko chcel nájsť len najťažšie závažie? Možno ste sa s takouto úlohou stretli. Po nejakom čase rozmýšľania nie je náročné prísť na to, že to Maťko zvládne na \(41\) vážení. Napr. môže porovnávať vždy doposiaľ najťažšie závažie. Dokázať, že na menší počet vážení to nejde, je o niečo náročnejšie. Môžeme využiť, že každé závažie sa musí niekedy vážiť. To nám dá však len príliš slabý odhad, lebo na to nám stačí len \(21\) vážení. Pre dokázanie správneho odhadu si môžete každé závažie predstaviť vo vlastnej skupinke. Pri každom porovnaní závaží ich skupinky spojíme. Pre určenie najťažšieho závažia potrebujeme dostať len jednu skupinku. Detaily riešenia tejto úlohy nechávame na vás.

Čo ale ak chceme nájsť aj najťažšie, aj najľahšie závažie? Asi dosť rýchlo nám napadne, že môžeme na \(41\) vážení nájsť najťažšie závažie a potom spomedzi zvyšných \(41\) závaží vieme na \(40\) vážení nájsť najľahšie. Je to ale najlepšie, čo vieme? Musíme najťažšie a najľahšie hľadať takto separovane? Nevieme to nejako skombinovať? Môžeme nad tým pouvažovať. Alebo sa môžeme pustiť do dokazovania, prečo je toto optimálny počet vážení. Vtedy zistíme, že nám to moc nejde dokázať. Predsa len vieme nejaké váženia ušetriť, ak toto skombinujeme.

Opis správneho spôsobu váženia

Kľúčovou myšlienkou je správna deľba práce. Najskôr si rozdeľme závažia do \(21\) dvojíc a každú dvojicu odvážme. Dostaneme tak \(21\) závaží, ktoré z vážení vyšli ako ťažšie – niekde medzi nimi sa musí nachádzať aj najťažšie. Zoberme si ľubovoľné z nich ako favorita a postupne pre každé zo zvyšných \(20\) závaží spravíme nasledovné: závažie porovnáme s aktuálnym favoritom a ak bude ťažšie ako favorit, tak ním nahradíme doterajšieho favorita. Takto po \(20\) váženiach bude favoritom určite najťažšie závažie. Podobne, medzi zvyšnými \(21\) závažiami, ktoré vyšli z prvých vážení ako ľahšie, sa musí nachádzať najľahšie závažie. Podobným spôsobom vieme nájsť aj to na \(20\) vážení. Týmto spôsobom sme našli najľahšie a najťažšie závažie na \(21 + 20 + 20 = 61\) vážení.

Ako dokázať, že to lepšie nejde?

Pri úlohách toho typu to zvykne bývať tá ťažšia časť. No napriek tomu sa k tomu dá pristúpiť hravo. Môžeme sa vžiť do role Maťkovho nepriateľa. V tomto prípade si za jeho nepriateľom môžeme predstaviť váhu alebo osud. Ako Maťkov nepriateľ môžeme voliť také situácie, aby sme mu čo najviac znepríjemnili život. Môžeme si to predstaviť tak, že na začiatok určíme hmotnosti závaží. Keď nám to bude vyhovovať, tak môžeme nejakému závažiu zmeniť hmotnosť, pokiaľ tým nenarušíme žiaden predošlý výsledok váženia. Totiž pri týchto nových hmotnostiach závaží by Maťko postupoval presne rovnako, lebo by dostával rovnaké výsledky vážení. Takúto zmenu hmotnosti nemá ako rozlíšiť. Tento prístup využijeme aj my.

Najskôr však sa zamyslime nad niečím, čo nám ponúkne správny pohľad na to, čo presne sa v tejto úlohe deje. Pozrime sa, čo sa dozvieme z jedného váženia. Jedno závažie bude ľahšie a druhé ťažšie. O tom ľahšom vieme povedať, že rozhodne nebude najťažším. Podobne, ťažšie závažie isto nebude najľahším. Preto si po každom vážení na ťažšie závažie napíšeme znak \(T\) a na ľahšie závažie znak \(L\). Keď na \(41\) závažiach budeme mať znak \(L\), tak vieme, že jediné zostávajúce závažie musí byť najťažšie. (Vyskúšajte si to na našej stratégii opísanej vyššie, príp. na iných stratégiách.) Dôležité však je, že to platí aj opačne, čo si teraz ukážeme.

Označme si najťažšie závažie \(M\) (to isto nemá znak \(L\)). Čo ak okrem neho nejaké závažie \(A\) tiež nemá znak \(L\)? Ak zvýšime hmotnosť závažia \(A\) nad hmotnosť závažia \(M\), tak sa \(A\) stane najťažším závažím. Zjavne sme tým žiaden výsledok váženia neporušili, lebo závažie \(A\) vyšlo z každého váženia ako ťažšie (lebo nemá znak \(L\)) a ostatné váženia touto zmenou neovplyvníme. V takejto situácii teda môže byť závažie \(A\) rovnako dobre najťažším, preto Maťko nevie určiť, ktoré to je. Teda na určenie najťažšieho závažia Maťko potrebuje, aby \(41\) závaží malo znak \(L\). Analogicky, na určenie najľahšieho závažia Maťko potrebuje, aby \(41\) závaží malo znak \(T\). Teda celkovo Maťko potrebuje \(82\) znakov.

Pozrime sa, koľko znakov môže Maťkovi pribudnúť, keď odváži závažia \(A\) a \(B\):

1. \(A\) aj \(B\) sú neoznačené. Potom vždy dostane jedno znak \(T\) a druhé \(L\). Maťkovi pribudnú dva znaky.

2. \(A\) má znak \(T\) (príp. \(T\) a \(L\)) a \(B\) je neoznačené. Keďže \(B\) je neoznačené, nebolo ani vážené. Preto môžeme zmeniť jeho hmotnosť tak, aby bolo ľahšie ako \(A\). Váha tak Maťkovi povie, že \(B\) je ľahšie, čím mu pribudne len jeden znak \(L\) na závažie \(B\).

3. \(A\) má znak \(L\) a \(B\) je neoznačené. Podobne ako vyššie zariadime, nech je \(B\) je ťažšie. Maťkovi pribudne jeden znak.

4. \(A\) má znak \(T\) a \(B\) má znak \(L\). Ako sme už ukázali, závažie \(A\) bez symbolu \(L\) môžeme zmeniť na závažie s najvyššou hmotnosťou. Vtedy sa Maťko dozvie, že \(A\) je ťažšie ako \(B\) a žiaden nový znak tým nezíska.

5. Vo všetkých ostatných prípadoch majú závažia \(A\), \(B\) aspoň tri znaky. Preto bez ohľadu na výsledok váženia Maťkovi pribudne najviac jeden znak.

Vo všetkých prípadoch okrem prvého pribudne Maťkovi najviac jeden znak. Avšak každý prírastok dvoch nových znakov (1. prípad) stojí Maťka dve neoznačené závažia. Preto dva znaky nám môžu pribudnúť najviac pri \(42/2 = 21\) váženiach. Vo zvyšných váženiach vie Maťko získať len jeden. Aby získal \(82\) znakov, tak potrebuje spraviť ešte aspoň \(82 - 2\cdot21 = 40\) vážení. Tým sme dokázali, že na nájdenie najťažšieho a najľahšieho závažia Maťko potrebuje aspoň \(21 + 40 = 61\) závaží. Tým je naše riešenie úplné.

Pohľad na úlohu cez teóriu grafov

V niektorých úlohách o vážení a porovnávaní vie prísť vhod predstaviť si situáciu pomocou orientovaného grafu. Závažia budú vrcholy grafu. Zakaždým, keď zistíme, že závažie \(A\) je ťažšie ako závažie \(B\), tak do grafu pridáme orientovanú hranu z vrcholu \(A\) do vrchola \(B\). Ak ste sa s grafmi ešte nestretli, ide o matematický pojem, ktorý priamo zodpovedá mnohým našim náčrtom. Závažia si vieme kresliť ako body (vrcholy) na papier. Nakresliť hranu z \(A\) do \(B\) znamená nakresliť šípku z \(A\) do \(B\).

Na dokazovanie, že menej ako \(61\) vážení Maťkovi nestačí, sa vieme opäť pozrieť ako na hru. Maťko si vyberie dva vrcholy a my medzi ne nakreslíme orientovanú hranu nami vybraným smerom. Pri tom nám stačí dodržať, aby sme v našom grafe nevytvorili orientovaný cyklus (teda taký cyklus, v ktorom sú všetky hrany orientované jedným smerom). Ak toto dodržíme, tak existenciu hmotností závaží, ktoré budú konzistentné so všetkými váženiami, nám zaručuje existencia topologického usporiadania: Ak máme orientovaný graf bez orientovaných cyklov, tak jeho vrcholy možno zoradiť do postupnosti tak, že pre každú orientovanú hranu z vrchola \(A\) do vrchola \(B\) platí, že vrchol \(A\) sa nachádza v postupnosti skôr ako \(B\). Takáto postupnosť sa nazýva topologické usporiadanie orientovaného grafu. Môžete si skúsiť toto tvrdenie dokázať, nie je to náročné. Zdôrazňujeme však, že graf, tak ako ho berieme, musí mať konečný počet vrcholov.

S využitím grafov vieme vyriešiť aj spomínanú jednoduchšiu úlohu. Rozmyslite si, že aby sme vedeli jednoznačne určiť najťažšie závažie, náš graf po odmyslení orientácie hrán musí byť súvislý – medzi každými dvoma vrcholmi sa musíme vedieť dostať po hranách. Potom nám stačí využiť známy výsledok o tom, že súvislý graf na \(n\) vrcholoch má aspoň \(n - 1\) hrán.