7. Kradnutie Mincí Strieborných vzorové riešenie

Úvod

Na začiatku riešenia nám môžu napadnúť nejaké spôsoby, ako môže Robber-ta nájsť vrece so striebornými mincami (ďalej len srieborné vrece). Napríklad môže dať v každom kroku na váhu jedno vrece. Niektorých riešiteľov môže napadnúť postup často používaný v informatike: Robberta rozdelí vrecia na polovice a z jednej polovice vriec dá na váhu po jednej minci. Pokiaľ váha ukáže násobok desiatich, strieborné vrece je v nevybranej polovici, v opačnom prípade vo váženej polovici. Takto po prvom kroku dostaneme \(60\) vriec, z ktorých jedno bude strieborné. Opakovaním budeme dostávať postupne najviac \(30,\, 15,\, 8,\, 4,\, 2,\, 1\) vreco. Teda už po \(7\) krokoch nájdeme strieborné vrece. V informatike sa postup takéhoto typu nazýva binárne vyhľadávanie.

Musíme však pamätať na to, že pri takomto type úloh musíme dokázať, že sme skutočne našli najmenší počet krokov. Nie len preto, aby sme sa vyhli strhnutému počtu bodov za chýbajúce zdôvodnenie, ale aj preto, aby sme sa vyhli zlému výsledku. Hoci binárne vyhľadávanie sa zdá byť dosť efektívne, po bližšom zamyslení až tak nevyzerá. Totiž nijako nevyužíva to, že v každom vreci je až \(100\) mincí. Nevieme to nejako využiť na to, aby sme z váženia získali viac informácie?

Úlohu si najprv trochu pozmeníme. Pokúsime sa zistiť, koľko najviac vriec môže byť v banke, aby Robber-ta vedela nájsť strieborné na jedno váženie. Potom budeme uvažovať dve váženia a takto budeme pridávať váženia, kým budeme potrebovať. Takýto prístup nám umožní nájsť správne riešenie. Navyše, takto aj zdôvodníme, prečo Robber-te nemôže stačiť menší počet vážení.

Pripomíname, že do vašich riešení stačí napísať veci, ktoré sú potrebné pre správnosť riešenia. Nie je potrebné písať, čo ste skúšali a ako ste na riešenie prišli. Konkrétne, z tohoto vzorového riešenia by na úplné riešenie stačili nasledovné dve alebo posledné dve sekcie.

Riešenie – dolný odhad

Čo ak má Robber-ta iba jedno váženie? To, že vo vreciach je viac mincí, vie Robber-ta využiť tak, že vyberie z nich na váhu rôzne počty mincí. Ak má Robber-ta \(14\) vriec, tak vie z nich vybrať postupne po \(0,\, 1,\, 2,\, \dots,\ 12,\, 13\) mincí a dať ich na váhu. Váha sa nepreťaží lebo na nej je najviac \((0 + 1 + 2 + \dots + 13) \cdot 10 = 910\) gramov. Ak váha ukáže \(910 - s\) gramov, tak vieme, že na váhe muselo byť \(s\) strieborných mincí. Podľa toho Robber-ta nájde strieborné vrece. Teda na jedno váženie vie Robber-ta nájsť strieborné vrece spomedzi \(14\) vriec.

Ak by vriec bolo viac, tak Robber-ta nevie z každého vybrať na váhu iný počet – položila by tam aspoň \(((0 + 1 + 2 + \dots + 13) \cdot 10 + 14 \cdot 9 = 1036\) gramov, čím by prehrala.¹ Preto by sme mali dve vrecia, označme si ich \(R\) a \(J\), z ktorých Robber-ta vážila rovnaký počet mincí. Robber-ta teda nevie rozlíšiť situácie, kedy sú strieborné mince vo vreci \(R\) a kedy sú vo vreci \(J\). V oboch prípadoch jej váha dáva rovnaké informácie. Preto na jeden krok vie Robber-ta rozlíšiť najviac \(14\) vriec.

Čo ak má Robber-ta dva kroky váženia? Aby vedela strieborné vrece nájsť v druhom vážení, nesmie jej po prvom kroku ostať skupina aspoň \(15\) vriec, z ktorých v prvom vážení vybrala rovnaký počet mincí. Teda do prvého váženia môže Robber-ta vybrať najviac zo \(14\) vriec po žiadnej minci, najviac zo \(14\) vriec po jednej minci a rovnako po dvoch a troch minciach. Teraz môže mať Robber-ta na váhe najviac \((0\cdot14 + 1 \cdot 14 + 2 \cdot 14 + 3 \cdot 14) \cdot 10 = 840\) gramov. Aby nepreťažila váhu, môže ešte na ňu pridať po \(4\) mince z najviac \(4\) ďalších vriec. Teraz je na váhe \((0\cdot14 + 1 \cdot 14 + 2 \cdot 14 + 3 \cdot 14 + 4 \cdot 4) \cdot 10 - s = 1000 - s\) gramov, kde \(s\) je počet strieborných mincí. Teda opäť z ukázanej hmotnosti vieme zistiť, v ktorej skupine vriec sa nachádza strieborné. Ak by Robber-ta pridala na váhu čo i len jednu ďalšiu mincu, už by sa preťažila. Teda na dva kroky vie Robber-ta rozlíšiť najviac \(60\) vriec.

Týmto sme dokázali, že Robber-ta potrebuje aspoň tri kroky váženia. Teraz už nepotrebujeme zisťovať, koľko vriec je schopná rozlíšiť (môžete si to však premyslieť). Stačí nám opísať, ako rozlíši \(120\) vriec, čo ide celkom jednoducho – stačí nám v provom kroku rozdeliť váženie na polovicu.

Postup váženia

V prvkom kroku si Robber-ta vyberie \(60\) vriec a vyberie z nich po jednej minci na váhu. Ak váha neukáže násobok \(10\), Robber-ta pokračuje s vybranými vrecami, inak s nevybranými. V druhom kroku si Robber-ta rozdelí \(60\) vriec na skupiny po \(14\), \(14\), \(14\), \(14\) a \(4\) vrecia. Skupiny si očísluje \(0\), \(1\), \(2\), \(3\), \(4\). Z každého vreca zo skupiny číslo \(i\) (\(i \in \{0, 1, 2, 3, 4\}\)) vyberie na váhu po \(i\) mincí. Váha ukáže hmotnosť \(1000 - s\), kde \(s\) je číslo skupiny vriec so strieborným vrecom. Ďalej pokračuje s touto skupinou, ktorá má teda najviac \(14\) vriec. Vyberie z vriec postupne po \(0,\, 1,\, \dots,\, 13\) minciach na váhu. Z toho zistí počet strieborných mincí na váhe, z čoho jednoznačne vie, z ktorého vreca boli vybrané. V každom vážení sme na váhu vybrali najviac \(100\) mincí, čím sme ju isto nikdy nepreťažili.

Najmenší počet krokov, ktorý Robber-ta potrebuje na nájdenie strieborného vreca, je teda \(3\).

Iný spôsob dolného odhadu

Ukážeme ešte iný spôsob, ako môžeme zdôvodniť, prečo \(2\) kroky váženia Robber-te nestačia. V tomto prípade nám stačí okrem neho dopísať do riešenia postup váženia ako je v predchádzajúcej sekcii.

Predpokladajme, že by Robber-ta vedela nájsť strieborné mince len na dva kroky. V prvom vážení môže Robber-ta položiť na váhu najviac \(100\) mincí. Preto existuje aspoň \(20\) vriec, ktorých mince ešte neboli vážené. Ak by Robber-ta z každého z nich vybrala rôzny počet mincí, položila by na váhu aspoň \(0 \cdot 9 + 1 \cdot 9 + 2 \cdot 9 + 3 \dots 9 + \dots + 19 \cdot 9 = 1710\) gramov, čo sa nemohlo stať. Preto existujú aspoň dve vrecia, označme si ich \(R\) a \(J\), z ktorých Robber-ta v oboch krokoch dala na váhu rovnaký počet mincí. Robber-ta teda nevie rozlíšiť situácie, kedy sú strieborné mince vo vreci \(R\) a kedy sú vo vreci \(J\). V oboch prípadoch jej váha dáva rovnaké informácie.