Seminár 3: Prístup k riešeniu matematických úloh, typy dôkazov

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 sme 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ť.

Slovíčko 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 nesmie 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ť 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.
Č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 sme 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 3 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šavanie týchto dvoch častí.

Komentár

V tejto časti seminára je možné so študentmi text vyššie spoločne prečítať a analyzovať. Zaujímavejšou a prínosnejšou sa však zdá byť možnosť, kedy študentom predostrieme vyššie spomenuté nesprávne pokusy o riešenie a spoločne budeme hľadať problematické miesta a diskutovať, ako ich vylepšiť.