Lode

Táto úloha je príkladom úlohy, kde hľadáme najmenší alebo najväčší počet niečoho. Je na nej ilustrovaných niekoľko neúplných riešení.

Zadanie úlohy.

Na pláne $7 \times 7$ hráme hru lode. Nachádza sa na ňom jedna loď $2 \times 3$. Môžeme vystreliť na ľubovoľné políčko plánu, a ak loď zasiahneme, hra končí. Ak nie, strieľame znova. Určte najmenší počet výstrelov, ktoré potrebujeme, aby sme s istotou loď zasiahli.

Pokus o riešenie 1.

Naším cieľom je strieľať čo najoptimálnejšie, aby sme použili čo najmenej výstrelov. Neoplatí sa nám preto strieľať na políčka pri sebe, lebo výstrely pri sebe pokryjú menej políčok ako výstrely ďalej od seba. Nesmieme však strieľať moc ďaleko od seba. Ak medzi dvoma výstrelmi sú aspoň dve políčka už sa tam môže zmestiť loď. Najlepšie teda bude, keď medzi susednými výstrelmi bude jedno voľné políčko. To vieme dosiahnuť vystrelením na políčka ako je znázornené na obrázku.

Na to, aby s istotou zasiahli loď, potrebujeme najmenej $9$ výstrelov. Na menej výstrelov to nie je možné, pretože sme strieľali najoptimálnejšie.

Rozbor riešenia

Na prvý pohľad toto riešenie môže vyzerať výborne, avšak riešenie má vážny nedostatok – chýba mu zdôvodnenie, prečo nestačí menej ako 9 výstrelov. Ale prečo? Veď sa v riešení spomína, že menej výstrelov nestačí. Objavuje sa tu aj ďalší problém. Uvedené zdôvodnenia sú len veľmi vágne a len na intuitívnej úrovni. Poďme si to postupne rozobrať.

„Neoplatí sa nám preto strieľať na políčka pri seba...“ Slovíčko „neoplatí“ je znamením intuitívnych dôkazov. Aby malo v dôkaze význam, musí byť matematicky podložené. Ako je podložené tu? Riešiteľ síce opisuje, že výstrely pri sebe pokryjú menej políčok ako výstrely ďalej od seba, ale tu už matematické podklady končia. Riešiteľ nepíše, čo to znamená pokryť políčko. Znamená to, že doňho nesme zasahovať loď, nesmie byť v ňom ľavý horný roh lode alebo niečo iné? Taktiež nezdôvodňuje, prečo počet pokrytých políčok bude menší. Patrilo by sa sem uviesť nejaký výpočet, že naozaj ten počet (tak ako ho máme definovaný) vyjde menší.

Ďalším problémom je, že riešiteľ sa pozerá na polohu iba dvoch políčok. Vo všeobecnosti neplatí, že lokálne najoptimálnejšie riešenie je najoptimálnejšie aj globálne. Môže sa nám stať (zatiaľ teoreticky), že dva výstrely nebudú umiestnené optimálne, ale to, čo pri nich stratíme, môžeme získať pri iných dvojiciach a môže nás to doviesť k ostro lepšiemu rozloženiu výstrelov ako keby sme sa snažili všetko spraviť „najoptimálnejšie“ na úrovni susedných výstrelov.

Uvedené riešenie teda iba intuitívne vysvetľuje, prečo je 9 najmenší počet výstrelov. Použitý postup je pre nás dobrý, keď sa snažíme nájsť políčka kam strieľať. Avšak z formálnej stránky to hodnote riešenia nepridáva a riešenie má rovnakú hodnotu, ako keby sme len v ňom uviedli obrázok s vetou, že $9$ výstrelov stačí.

Z hľadiska formulácie riešenia je problém, že riešenie v sebe mieša dve časti: konštrukciu, že $9$ výstrelov stačí a dôkaz, že menej nestačí. Síce toto nie je chyba, ktorá by sama o sebe zapríčinila stratu bodov. Ale rozčlenenie riešenia na dve časti vám pomôže si ujasniť, že každá z týchto častí je vyriešená úplne a nie len intuitívne. Taktiež aj opravovateľ bude mať väčšiu radosť z pekne uprataného riešenia :).

Čo v tejto fáze riešenia? Rozhodne nie sme spokojní s tým, že úlohu máme. Keď máme pocit, že lepšie to už nejde, pustíme sa do dokazovania, že je to naozaj tak. Častokrát si táto fáza vyžaduje pozerať sa na úlohu z inej strany. To bude zrejme potrebné aj v našom prípade. Jednou našou možnosťou síce je matematicky podložiť naše úvahy, ale čaká nás niekoľko problémov. Ide hlavne o to, že sa chceme pozerať na to, ako musia byť umiestnené dva výstrely, čo nemusí stačiť, ako sme spomenuli vyššie.

Pokus o riešenie 2.

Na nasledujúcom obrázku vidíme $8$ obdĺžnikov $2 \times 3$ rozmiestnených na plániku, ktoré sa neprekrývajú.

Ak by mali menej ako $8$ výstrelov, tak jeden z ôsmich obdĺžnikov nezasiahneme a zrovna tam sa môže nachádzať loďka. Potrebujeme teda do každého obdĺžnika vystreliť jeden výstrel. Musíme ich umiestniť zároveň tak, aby sa medzi ne nezmestila žiadna iná loď. Na to, aby sme s istotou zasiahli loď, potrebujeme najmenej $8$ výstrelov.

Rozbor riešenia

Toto riešenie taktiež nie je úplné. Riešiteľ v ňom ukázal len, že potrebuje aspoň $8$ výstrelov. Neukázal, že $8$ výstrelov stačí. Hovorí iba v teoretickej rovine, že ak sa mu podarí tých 8 výstrelov vhodne umiestniť, tak budú stačiť. Ale je to naozaj možné? Čo ak z nejakého iného dôvodu $8$ výstrelov stačiť nebude.

Spoločný rozbor

Vidíme, že riešenia 1 a 2 majú rôzne výsledky, jedno tvrdí, že najmenej výstrelov je $9$ a druhé $8$. Jedno riešenie je teda nesprávne, ale ktoré? Ak sme pri riešení tejto úlohy v stave, že máme všetko, čo tieto dve riešenia spolu, tak vieme, že správnym riešením úlohy je $8$ alebo $9$ výstrelov. Pre dokončenie úlohy potrebujeme buď nájsť $8$ políčok, na ktoré nám stačí vystreliť, alebo dokázať, že $8$ výstrelov nestačí.

Na prekvapenie (možno nie pre všetkých je to prekvapenie) naozaj stačí $8$ výstrelov. Všetky intuitívne argumenty v riešení 1 sú teda nesprávne. Na riešení uvedenom nižšie si môžete všimnúť, že nie je pravda, že sa neoplatí strieľať blízko seba. Stalo sa tu, pred čím sme varovali. Tým, že sme na niektorých miestach strieľali „neoptimálne“ zlepšilo situáciu inde a v konečnom dôsledku sme dosiahli lepšie riešenie.

Vzorové riešenie

Ukážeme, že $8$ je najmenší počet výstrelov, ktorý potrebujeme, aby sme s istotou zasiahli loď.

Na obrázku vľavo vidíme, že môžeme na plán umiestniť 8 neprekrývajúcich sa obdĺžnikov $2 \times 3$ (stredné políčko ostane prázdne). Aby sme s istotou zasiahli loď, musíme zasiahnuť aspoň jedno políčko v každom z ôsmich vyznačených obdĺžnikov, preto potrebujeme aspoň 8 výstrelov.

Na obrázku vpravo je uvedený príklad výberu ôsmych políčok, na ktoré stačí vystreliť, aby sa už mimo nich nedala na plán umiestniť žiadne loď $2 \times 3$. Preto týchto $8$ výstrelov k zasiahnutiu lode vždy stačí.

Rozbor vzorového riešenia

Táto úloha je pekným príkladom toho, ako sa to, čo je napísané v riešení, líši od toho, čím sme prechádzali pri riešení úlohy. Hoci je samotné riešenie úlohy krátke, úlohu sme veru krátko neriešili. Väčšina riešiteľov začne s deviatimi výstrelmi ako v pokuse 1 a potom sa postupne cez rôzne vylepšenia strieľania, rôzne pokusy o 8 výstrelov a ďalšie iné úvahy dostane k riešeniu s ôsmimi výstrelmi.

Všimnime si ďalej členenie riešenia. Najprv uvedieme, čo chceme ukázať (táto časť môže byť aj na konci) a vo zvyšku riešenia dokážeme, že naše riešenie je správne. Riešenie je pekne rozčlenené na dve časti podľa dvoch bodov, čo potrebujeme pri takejto úlohe ukázať (môžu byť aj vymenené). V prvej časti ukážeme, že potrebujeme aspoň 8 výstrelov. V druhej ukážeme, že 8 výstrelov nám naozaj stačí. Nie je tu žiadne premiešavenie týchto dvoch častí.

Takto napísané riešenie je prehľadné, je v ňom práve to, čo treba a nič navyše a opravovateľ zaň udelí 9 bodov s radosťou, lebo sa mu bez problémov čítalo. Ak by riešenie bolo dlhšie, kedy by sme potrebovali obe časti rozčleniť na viac odsekov, môžeme ich pre lepšiu prehľadnosť vyčleniť nadpismi alebo značkami.