8. príklad - Vzorové riešenie

Tento príklad bolo ideálne počítať tak, že sme našli spôsob, ako rýchlo zistiť, či sa pre nejaký počet rozlomených článkov dá odvážiť každý počet gramov. Potom nám stačí vyskúšať rôzne počty rozlomení a nájsť najmenší, ktorý stačí.

Chceme zistiť, či sa to dá, keď rozlomíme 3 články:

Máme teda 3 rozlomené články a najviac 4 kusy reťaze. Dĺžky týchto kusov si určíme tak, aby sme vedeli odvážiť čo najviac rôznych hmotností, ako sa dá.
Pomocou tých troch rozlomených článkov vieme odvážiť hmotnosti 1-3 gramy. Aby sme vedeli odvážiť 4 gramy, potrebujeme kus reťaze s hmotnosťou najviac 4. Všimnime si, že keď vieme odvážiť všetky hmotnosti po nejaké číslo x a pridáme kus s hmotnosťou y, budeme navyše vedieť odvážiť hmotnosti od y do x+y. Tým pádom by bolo ideálne, aby sa tieto intervaly nikdy neprekrývali - teda aby platilo y>x. Takže najviac rôznych hmotností dosiahneme, ak to bude presne 4.
S reťazou hmotnosti 4 vieme odvážiť 1-7 gramov. To znamená, že ďalšia reťaz bude mať hmotnosť 8.
S reťazami hmotnosti 4 a 8 vieme odvážiť 1-15 gramov. Takže dalšia reťaz bude mať 16 gramov.
S reťazami hmotnosti 4, 8 a 16 vieme odvážiť 1-31 gramov. Posledný štvrtý kus bude mať všetky zvyšné články, teda 150-3\cdot1-4-8-16=119.
S reťazami hmotnosti 4, 8, 16 a 119 vieme odvážiť 1-63 gramov a 119-150 gramov.

To znamená, že pre 3 rozlomenia reťaze vieme navážiť najviac 63 rôznych hodnôt.

Skúsme teda 4:

Máme 4 rozlomené články a najviac 5 kusov reťaze. Znova sa snažíme, aby sme vedeli odvážiť, čo najviac rôznych hmotností.
Pomocou tých štyroch rozbitých článkov vieme odvážiť hmotnosti 1-4 gramy.
Aby sme vedeli odvážiť 5 gramov, jedna z reťazí bude musieť mať hmotnosť 5.
S reťazou hmotnosti 5 vieme odvážiť 1-9 gramov. To znamená, že ďalšia reťaz bude mať hmotnosť 10.
S reťazami hmotnosti 5 a 10 vieme odvážiť 1-19 gramov. Takže dalšia reťaz bude mať 20 gramov.
S reťazami hmotnosti 5, 10 a 20 vieme odvážiť 1-39 gramov. Takže dalšia reťaz bude mať 40 gramov.
S reťazami hmotnosti 5, 10, 20 a 40 vieme odvážiť 1-79 gramov. Posledný, piaty kus bude mať všetky zvyšné články, teda 150-4\cdot1-5-10-20-40=71.
Takto vieme odvážiť 1-79 gramov a s použitím posledého piateho kusu reťaze 71-150 gramov. Čiže pri 4 rozlomeniach vieme navážiť všetky hmotnosti od 1 do 150 gramov.

A keďže sme si ukázali, že pre 3 to nejde, vieme, že 4 je najmenší počet rozlomení, na ktorý sa to dá.

Iné riešenie:

Ešte by sme radi ukázali iný spôsob, ako sa dá dokázať, že 3 zlomenia nám nestačia. Keď rozlomíme 3 články, získame najviac 7 častí reťaze (3 zlomené a 4 súvislé časti medzi nimi). Pozrime sa, koľko možných kombinácií z nich môžeme vybrať. Každú časť môžeme buď vybrať alebo nevybrať a teda máme 2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2 alebo 2^7 možností. To nám ale dokopy dáva iba 128 možných kombinácií, teda nie je možné pomocou nich odvážiť 150 rôznych hotností. Takéto riešenie, sa viac podobá na poriadny matematický dôkaz, naopak to prvé riešenie skôr zodpovedá tomu, ako sme pri riešení rozmýšľali.

Komentár:

Veľa z vás si neuvedomilo, že pri zlomení článku získame okrem dvoch súvislích častí reťaze ešte jeden zlomený článok. Potom ste sa snažili použiť klasickú binárnu sústavu, čo ale neviedlo k optimálnemu riešeniu.