Čeky má $11$ náramčekov, každý inej farby.
Odkladá si ich do vreca, ktoré by sa roztrhlo, ak by v ňom bolo viac ako $11\, \textrm{kg}$.
Ivka vie, že náramčeky majú v nejakom poradí hmotnosti $1,\,2,\,3,\,...,\,11\, \textrm{kg}$, ale nevie v akom. Čeky pozná hmotnosti všetkých náramčekov a chce dokázať Ivke, že ružový náramček váži $1\, \textrm{kg}$. V jednom kroku môže Čeky dať do vreca nejaké náramčeky a ukázať Ivke, že sa <u>neroztrhlo</u>. Koľko najmenej krokov potrebuje Čeky na to, aby Ivku presvedčila?
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.
Korešpondenčný matematický seminár zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Intenzívny matematický zážitok v lete
Tímová matematická súťaž pre stredoškolákov
Knižnica všemožných matematických múdrostí