9. Koláče Maťko Spapá vzorové riešenie

Úvodné pozorovania

Prvá vec, ktorú si môžeme všimnúť, je, že pri prvom vážení Betka nevie o perníkoch nič, takže si nevšimne, ak Vodka zje najväčší perník, vážiaci \(200\) gramov. Takže tento perník sa nám s istou nájsť nepodarí.

Ďalej si môžeme všimnúť, že vážení máme k dispozícii \(17\). Totiž po \(17\). vážení nám ostanú tri perníky. Ak dva z nich porovnáme, tak ich už musíme aj poslať Kike a dopadlo by to rovnako, ako keby sme ich poslali bez toho posledného váženia.

Podúloha a)

Pozrime sa najprv na časť a). Vie Betka zaručene nájsť dva perníky, ktoré spolu vážia aspoň \(280\) gramov? Vie Betka nájsť \(190\)-gramový perník? Na začiatok porovnáme dva ľubovoľné perníky a tretí dáme Vodkovi zjesť. Potom v každom ďalšom vážení dáme Vodkovi zjesť perník, ktorý bol v predchádzajúcom vážení ľahší, a porovnáme aktuálne najťažší perník s jedným ešte neváženým. To opakujeme, kým nám neostanú dva perníky. Ten ťažší z nich je ťažší od \(18\)-tich perníkov, preto musí vážiť aspoň \(190\) gramov.

Uvedený postup vieme vlastne zovšeobecniť. Keď máme nejakú skupinu perníkov a jeden perník bokom, tak vieme nájsť najťažší perník z tejto skupiny. V prvom vážení dávame Vodkovi perník, čo máme bokom a pokračujeme ako vyššie. Dokonca nám potom zostane z tejto skupiny jeden perník, ktorý z posledného váženia vyšiel ako ľahší. Zišiel by sa však nájsť aj druhý perník, ktorý bude dostatočne ťažký.

To môžeme spraviť tak, že našich \(19\) perníkov rozdelíme do dvoch skupín. Do jednej dáme \(9\), do druhej \(10\) perníkov a jeden zvyšný perník odložíme na prvé váženie. Vyššie uvedeným postupom nájdeme najťažší perník z prvej skupiny a najťažší perník z druhej skupiny. Vieme o nich, že víťaz prvej skupiny má aspoň \(90\) gramov a víťaz druhej aspoň \(100\). Z nich je ale jeden ťažší a ten je dokonca z našich \(19\) perníkov najťažší, a teda má aspoň \(190\) gramov. Spolu teda majú aspoň \(280\) gramov. Takto sme ukázali, že odpoveď na otázku a) je kladná.

Podúloha b)

Teraz sa ale pozrieme na tú ťažšiu časť. Vie Betka týmto spôsobom zaručene nájsť dva perníky, ktoré spolu vážia aspoň \(300\) gramov? Aj keď sa to možno na prvý pohľad nezdá, aj to dokáže. V predchádzajúcej časti sme vždy kŕmili Vodku perníkmi, ktoré prehrali posledné váženie. Tento výsledok ale môžeme zlepšiť, ak nebudeme lakomí a pre Vodku odložíme ďalší perník. Tým nám ostane len \(18\) perníkov vážiacich \(10,\, 20,\, \dots,\, 180\) gramov, ale dostaneme tým k dobru o jedno váženie viac.

Samozrejme, stále potrebujeme nejako nájsť perníky, ktoré budú ťažšie od dostatočného množstva perníkov. Najťažšie perníky z nejakej skupiny sa nám osvedčili v podúlohe a). Skúsime teda tento nápad potiahnuť ďalej tým, že skúsime namiesto dvoch skupín mať tri.

Rozdelíme si teda \(18\) perníkov do troch skupín, v každej po \(6\) perníkov. Zvyšné dva si necháme bokom. V týchto troch skupinách vyberieme predtým popísaným spôsobom najťažší perník, pričom v prvej skupine dáva Vodkovi zjesť perník, čo má bokom a v ďalších dvoch ľahší perník z posledného váženia v predošlej skupine. Potom nám ostanú tri víťazné perníky, jeden porazený z posledného váženia a jeden odložený na boku. Medzi víťaznými perníkmi váži najľahší perník aspoň \(60\) gramov, druhý najľahší aspoň \(120\) gramov a najťažší aspoň \(180\) gramov. Ak Betka vyberie dva najťažšie perníky, zaručene pošle Kike aspoň \(300\) gramov. To vie však spraviť tak, že nájde najľahší z nich. Ten dokáže nájsť pomocou dvoch vážení jednoducho tak, že ľubovoľné dva z nich odváži, a ten ľahší odváži s tým tretím. Vodkovi dáva pritom dva zvyšné perníky, ktoré ešte má k dispozícii.

Komentár

Mnoho z vás si myslelo, že Betka nedokáže nájsť dva perníky vážiace spolu \(300\) gramov a snažili ste sa zdôvodňovať, prečo to nie je možné. Keďže opak je pravdou, tak všetky takéto dôkazy sú nesprávne. Objavili sa v nich časté chyby, ktoré sa vyskytujú pri úlohách podobného typu, kde zdôvodňujeme, že niečo nemôže byť väčšie. Častým problémom bolo, že sa tento dôkaz moc opieral o konštrukciu nájdenú v časti a) a neuvažoval iné spôsoby váženia. Napr. situáciu, keď dva perníky dáme Vodkovi bez toho, aby sme ich niekedy porovnali; alebo keď dávame vážiť perník, ktorý z niektorého váženia vyšiel ako ľahký. Pokiaľ ste vo svojom riešení mali „dôkaz“, že b) nejde, skúste sa nad ním zamyslieť a nájsť v ňom chybu. Veríme, že vám to pomôže podobným chybám predísť.