3. príklad - Vzorové riešenie

Kategórie:
5
6
7

Zadanie

Archeológovia našli nálezisko neandertálca. Pri pozostatkoch našli aj korálkové náhrdelníky pre neandertálske fešandy. Tieto náhrdelníky boli vytvárané veľmi špecifickým spôsobom. Na kružnicovú šnúrku najprv v lubovoľnom poradí umiestnili dva typy ozdôb: 4 korálky a 5 perličiek. Potom pre každú po sebe idúcu dvojicu umiestnili nové ozdoby takto: ak je dvojica rovnakého typu ozdoby, tak medzi ne vložili korálku, a ak rôzneho, tak medzi ne vložili perličku. Potom odstránili pôvodné ozdoby, a tak im znova zostal náhrdelník s 9 ozdobami. Tento proces zopakovali niekoľkokrát.

Je možné, aby takto vytvorili aj náhrdelník, na ktorom sú ozdoby iba jedného typu? Ak áno, nájdite príklad takého náhrdelníku. Ak nie, vysvetlite, prečo to určite nejde.

Vzorové riešenie

Opravovali: Oliver, alytsa

Úloha po nás chce aby sme zistili, či sa dá vytvoriť náhrdelník pozostávajúci iba z perličiek (P​) alebo iba z korálok (K​). Chceme vlastne nájsť postupnosť náhrdelníkov takú, že prvý náhrdelník bude tvorený 4\,K a 5\,P, posledný bude mať iba K​ alebo iba P a vždy ten ďalší náhrdelník vznikne z posledného vyrobeného aplikáciou pravidiel zo zadania.

Máme dve možnosti ako môže výsledný náhrdelník vyzerať. Poďme sa pozrieť, z ktorých náhrdelníkov vieme tento finálny stav dosiahnuť:​

  • ​stav iba P​:​
    Aby sme dostali samé P, tak musí každá dvojica susedných ozdôb byť rôzna. Skúsme nejaký takýto náhrdelník zostrojiť. Začneme P, potom musíme dať KPKPKPK. Ale poslednú ozdobu už navliecť nemôžeme, ak by sme navliekli P, tak budú 2\,P vedľa seba (prvá a posledná ozdoba susedia), ak by sme navliekli K, tak budú zase 2\,K po sebe. Takže takúto pozíciu nevieme dosiahnuť hneď na začiatku. Čo sa stane ak využijeme pravidlá zo zadania? Majme náhrdelník PKPKPKPKP \rightarrow PPPPPPPPK \rightarrow KKKKKKKPP \rightarrow \dots \rightarrow PKKKKKKKP. Tu si môžeme všimnúť, že tretí a posledný náhrdelník sú ten istý, len inak zrotovaný, takže ak by sme pokračovali ďalej, tak by sme sa iba zacyklili a vyrábali stále tie isté náhrdelníky. To znamená, že náhrdelník, ktorý je tvorený iba P nevieme vytvoriť (inak by sme ho už našli pred dokončením cyklu)

  • ​stav iba K​:
    ​Aby sme dostali samé K, musí každá dvojica ozdôb v predchádzajúcom náhrdelníku byť rovnaká. To znamená, že predchádzajúci náhrdelník už mal iba samé K alebo samé P. Ak by mal iba K, tak sme zase "na konci", takže by už hneď na začiatku muselo byť 9\,K, čo nie je. Čiže by tam museli byť samé P. Ako sme ukázali vyššie, tak náhrdelník iba z P sa vytvoriť nedá, takže ani tento sa vytvoriť nedá.​

Odpoveď:

Neandrtálci nevedia vytvoriť náhrdelník, na ktorom budú iba ozdoby jedného druhu.