Zoznam úloh

5. Klenoty Moje Spoznaj

Zadanie



Čeky  $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.

Pre odovzdávanie sa musíš prihlásiť.
Trojsten

Korešpondenčný matematický seminár zastrešuje občianske združenie Trojsten.

Kontakt
Ďalšie projekty