Odporúčaný článok

Riešky výlet - Ahojte Rieškari, zoberte batohy, úsmevy, dobré nálady, lopty, hry, frisbee, kamarátov… a poďte s nami na výlet! Poprechádzame sa po Malých Karpatoch, kde pre vás máme pripravený skvelý program a … Prejsť na článok

×

5. príklad - Vzorové riešenie

Kategórie:
5
6
7
8
9

Zadanie

Zvláštny prístroj, v ktorom sa Michard ocitol, sa nachádza na útese. Ak spraví 2 kroky dopredu alebo dozadu oproti svojej terajšej pozícii, spadne do priepasti. Aby sa mohol Michard s prístrojom hýbať, musí zadať postupnosť pokynov. Pokyn môže byť jedine krok dopredu alebo krok dozadu. Prístroj si potom zvolí nejaké prirodzené číslo n, ktoré dopredu nepoznáme, a splní len tie pokyny zadanej postupnosti, ktorých poradové číslo je násobok n. Akú najdlhšiu postupnosť pokynov vie Michard zadať prístroju, aby určite nespadol s prístrojom do priepasti?

Vzorové riešenie

Opravovali: Danko, alica, uršuľa

Tento príklad sa dal riešiť postupným skúšaním všetkých možností, ako sa môžeme pohnúť po jednotlivých krokoch. Ak vždy skontrolujeme a vyškrtneme možnosti, ktoré pre nejaké n nesedia, postupne sa dostaneme do bodu, kedy už nevieme žiadnu postupnosť predĺžiť, a teda sme našli najdlhšiu postupnosť pokynov. Existuje ale niekoľko spôsobov, ako si riešenie zjednodušiť.

Dobrou myšlienkou na začiatok je uvedomiť si, že vždy keď urobíme zo stredu krok určitým smerom, nasledujúci krok musíme urobiť opačným smerom, inak spadneme z útesu. Tým sa znova ocitneme v strede, a znova musíme uplatniť to isté pravidlo. Vždy po párnom počte vykonaných krokov (pre ľubovoľné n) teda budeme nutne v strede útesu.

Z toho vieme, že pre možnosť, že si prístroj vyberie n=1, musia byť dvojice pokynov 1. a 2., 3. a 4., 5. a 6., a tak ďalej, vzájomne opačné. Podobne vieme postupovať aj pri iných zvolených n, ako možno vidieť v nasledujúcej tabuľke:

pre n = musia byť navzájom opačné
1 1. a 2. 3. a 4. 5. a 6. 7. a 8. 9. a 10. 11. a 12.
2 2. a 4. 6. a 8. 10. a 12.
3 3. a 6. 9. a 12.
4 4. a 8. 12. a 16.
5 5. a 10.
6 6. a 12.

Označme si pokyn “krok dopredu” P a pokyn “krok dozadu” Z. Nemusíme ale rozoberať aj možnosti, keď je prvý pokyn P aj keď je Z. Keď si vyberieme hociktorú z týchto možností a podľa toho napíšeme postupnosť, analogickú postupnosť vieme napísať aj s opačným začiatočným pokynom, a to tak, že iba všetky pokyny otočíme. Tiež budú platiť všetky argumenty, ktorými sme iné postupnosti vylúčili, keď v nich vymeníme smery. Bez toho aby to ovplyvnilo riešenie, si teda zvoľme, že začneme pokynom P.

Aký môže byť vtedy druhý pokyn? Ako už vieme, keby sme zadali ako ďalší pokyn P, spadne prístroj z útesu. Musíme preto zadať pokyn Z .

PZ

Teraz sa pozrieme na štvrtý pokyn. Ak n=2, tak prvý vykonaný pokyn je Z. Z toho vyplýva, že druhý vykonaný pokyn, štvrtý celkovo, musí byť P.

PZ?P.

Z tabuľky vidíme, že kvôli možnosti n=1 musia byť 3. a 4. pokyn navzájom opačné. Teda tretí pokyn musí byť Z.

PZZP

Vieme, že kvôli n=3 musia byť aj 3. a 6. pokyn opačné, teda 6. pokyn bude P.

PZZP?P

Aký môže byť piaty pokyn? Kvôli n=1 musí byť opačný ako 6. pokyn, teda Z.

PZZPZP

Ôsmy pokyn musí byť kvôli n=4 opačný ako štvrtý, teda v našom prípade Z.

PZZPZP?Z

Siedmy pokyn potom musí byť kvôli n=1 opačný ako ôsmy, teda P.

PZZPZPPZ

Desiaty pokyn musí byť kvôli n=5 opačný ako piaty, teda P.

PZZPZPPZ?P

Deviaty pokyn vtedy musí byť kvôli n=1 opačný ako desiaty, teda Z

PZZPZPPZZP

Dvanásty pokyn kvôli n=6 musí byť opačný ako šiesty, teda Z. Aby ale prístroj nespadol ani ak si vyberie číslo n=3, musí byť dvanásty pokyn opačný ako deviaty, teda P. Určite nemôže byť pokyn P aj Z naraz, vidíme teda, že pri 12. pokyne môže prístroj spadnúť tak či tak.

Zostal ešte jedenásty pokyn. Ten vieme zadať aj ako P aj ako Z s tým, že prístroj určite nespadne nech si vyberie akékoľvek n.

Teraz je dôležité nakoniec overiť, že naša postupnosť je naozaj taká, že prístroj nespadne nech si zvolí ľubovoľné n.

  • Ak n=1, tak sa vykonajú pokyny PZZPZPPZZP a nakoniec Z alebo P, prístroj ani v jednom prípade nespadol.
  • Ak n=2, vykonajú sa pokyny ZPPZP, vidíme, že ani teraz stroj nespadne.
  • Ak n=3, vykonajú sa pokyny ZPZ, teda ani tu prístroj nespadne.
  • Ak n=4, vykonajú sa pokyny PZ, prístroj nespadne.
  • Ak n=5, vykonajú sa pokyny ZP, prístroj nespadne
  • Ak je n viac ako 6, vykoná sa vždy najviac jeden pokyn, tieto čísla majú totiž všetky okrem prvého násobku väčšie ako 11, čiže nie sú v našej postupnosti. Keďže urobíme iba jeden alebo žiaden krok, prístroj z útesu určite nespadne.

Dokázali sme teda, že neexistuje vyhovujúca postupnosť dlhšia ako 11 pokynov, a našli sme niekoľko správnych postupností práve tejto dĺžky, napríklad: PZZPZPPZZPP

Kľúčové v celom postupe je ukázať, že pri 12. pokyne sa už naša postupnosť určite pokazí, a že existuje nejaká funkčná dĺžky 11. Týmto máme zaručené, že odpoveď na úlohu je 11. Preto ako dôkaz úplne stačilo nasledovné:

Druhé riešenie

Vytvoríme podobnú tabuľku ako sa nachádza v prvom riešení, alebo slovne popíšeme, prečo párne pokyny v postupnostiach pre všetky n musia byť opakmi predošlých pokynov.

Vidíme, že ak je v postupnosti 12. pokyn, tak 9. pokyn, musí byť opačný ako 12. pokyn (kvôli n=3), a 12. pokyn musí byť opačný ako 10 (kvôli n=2). Z toho vyplýva, že 9. pokyn musí byť rovnaký ako 10. Avšak vieme, že pri takejto postupnosti by Michard spadol z útesu, pretože 9. a 10. pokyn nemôže byť rovnaký kvôli n=1.

Tým pádom sme dokázali, že správna postupnosť 12 a viac pokynov určite nemôže existovať. Teraz ak nájdeme postupnosť pre 11 ktorá platí pre všetky n, tak sme dokázali, že najdlhšia možná postupnosť má 11 pokynov. Takáto postupnosť je napríklad: PZZPZPPZZPP

Komentár

V príklade sa vyskytli dva kroky, ktoré mnohí riešitelia zabudli spomenúť, aj keď došli k správnemu výsledku. Prvým bol postreh, že to či začneme pokynom dopredu alebo dozadu maximálny počet pokynov v postupnosti neovplyvní. Druhým dôležitým krokom bola skúška správnosti, teda či postupnosť pokynov ktorú sme našli bola naozaj taká, že prístroj určite nespadne. Dala sa robiť po každom kroku, stačilo ju ale spomenúť aj na konci riešenia. Tieto dva princípy, symetrickosť a skúška správnosti, sú dôležitou časťou mnohých riešení, treba na ne v podobných príkladoch vždy myslieť.