5. Klenoty Moje Spoznaj vzorové riešenie

V tejto úlohe máme nájsť najmenší počet krokov, na ktorý môže Čeky presvedčiť Ivku. Čo to znamená? Keď nájdeme, že Čeky stačí \(n\) krokov a myslíme si, že je to najmenej, musíme dokázať, že na menej krokov to nie je možné. Ak sa nám to nebude dariť, je možné, že naše riešenie nie je dostatočné a budeme musieť nájsť presvedčenie na menej krokov.

Jedným zo spôsobov, ako môže Čeky dokázať o náramčeku, že má váhu \(1\, \text{kg}\), je pridať ho do vreca, o ktorého obsahu vie presvedčiť Ivku, že má Váhu \(10\, \text{kg}\). (Vrece sa následne neroztrhne, takže pridaný náramček musí vážiť \(1\, \text{kg}\).)

Najprv sa pozrieme, koľko najviac náramčekov môže Čeky do takých \(11\, \text{kg}\) zmestiť. Ak vždy vyberá najmenší náramček, tak po štyroch \(1+2+3+4=10\) tam už ďalší nedá (najmenší, ktorý jej ostal, má váhu \(5\, \text{kg}\), a do vreca už vieme dať len \(1\, \text{kg}\), aby sa neroztrhlo).

Vieme naplniť vrece štyrmi náramčekmi aj inak? Na to musíme aspoň jeden vymeniť. Jediné, čo sa nám do vreca ešte zmestí, je vymeniť niektorý náramček za ten s váhou \(5\, \text{kg}\), a vymieňaný náramček musí byť ten s váhou \(4\, \text{kg}\). Máme teda dva spôsoby ako zmestiť štyri náramčeky do vreca tak, aby sa neroztrhlo: \(1,\,2,\,3,\,4\, \text{kg}\) a \(1,\,2,\,3,\,5\, \text{kg}\).

Keď teda Ivke ukážeme vrece so štyrmi náramčekmi, určite platí, že niektorý z nich je ten s váhou \(1\, \text{kg}\). Ostáva nám ju presvedčiť o tom, ktorý z nich to je. Na to použijeme jednoduchý trik – ukážeme Ivke jeden zo štyroch náramčekov, ktoré boli vo vreci pri prvom pokuse, spolu s ďalšími dvomi, ktoré tam predtým neboli.

Ak sme prvýkrát vo vreci ukazovali \(1,2,3,4 \, \text{kg}\), tak tie dva odlišné by museli vážiť aspoň \(5\, \text{kg} + 6\, \text{kg} = 11\, \text{kg}\), ku ktorým sa jednotka už nezmestí. Ak sme ale začali so štvoricou \(1,\,2,\,3,\,5\, \text{kg}\), tak jediná (nepoužitá) dvojica náramkov, ku ktorej sa do vreca bez roztrhnutia zmestí ešte tretí, je \(4\, \text{kg}\) a \(6\, \text{kg}\) (všetky väčšie dvojice by vážili aspoň \(11\, \text{kg}\)).

Tým sme dostali naše riešenie na dva ťahy: Čeky najprv dá do vreca náramčeky s hmotnosťami \(1,\,2,\,3,\,5\, \text{kg}\) a potom \(1,\,4,\,6\, \text{kg}\), z čoho si Ivka musí byť istá, že náramok, ktorý bol v oboch týchto meraniach, musí vážiť \(1\, \text{kg}\).

To je pre nás super výsledok, lebo dokázať, že Čeky na menej ťahov Ivku nepresvedčí, je jednoduché. Ak dá Čeky do vreca len jeden náramček, tak to nemusí byť ten jednokilový a ak ich tam dá viac, tak sú navzájom nerozlíšiteľné. Čeky preto potrebuje najmenej dva kroky.