Odporúčaný článok

Anketa - Ahoj Rieškar, stalo sa ti niekedy, že si nerozumel zadaniam? Chcel by si v lete prísť na denný tábor? Sú nejaké akcie, ktoré by si chcel, aby sme robili častejšie? … Prejsť na článok

×

2. príklad - Vzorové riešenie

Kategórie:
5
6

Zadanie

Paulus má v jednej časti svojho mozgu osem mozgových buniek. Tieto bunky sú pospájané tak, ako vidno na obrázku. Každá bunka si pamätá jedno písmenko alebo pomlčku. Táto časť mozgu si pamätá názvy tropického ovocia, preto existuje spôsob, akým po spojeniach týchto buniek prejsť tak, aby znaky buniek, ktorými prejdeme, tvorili reťazec ANANAS–KOKOS–MANGO. Nájdite všetky možnosti, ako priradiť jednotlivým bunkám zodpovedajúce znaky.

Vzorové riešenie

Opravovali: Teri

V reťazci ANANAS-KOKOS-MANGO sa nachádza osem znakov - sedem písmen A, N, S, K, O, M, G a pomlčka. Keďže aj mozgových buniek je osem, tak vieme, že v každej bunke musí byť práve jeden z týchto znakov a každý znak sa bude nachádzať v práve jednej mozgovej bunke, aby sme vedeli vytvoriť daný reťazec.

Na to, aby sme vedeli vytvoriť reťazec ANANAS-KOKOS-MANGO prechádzaním po mozgových bunkách, tak znaky, ktoré spolu susedia v reťazci, sa musia nachádzať v susediacich bunkách, čiže takých, ktoré sú spolu spojené a medzi nimi sa nenachádza žiadna iná bunka. Teraz sa teda pozrieme na každý znak v reťazci a zistíme, aké znaky s ním susedia, čiže aké sú v reťazci tesne pred ním a tesne za ním.

Susediace s tromi znakmi Susediace s dvomi znakmi
A N, S, M N A, G
S A, -, O K -, O
- S, K, M M A, -
O K, S, G G N, O

V tabuľke vyššie máme znaky rozdelené do dvoch skupín podľa toho či susedia s tromi inými znakmi v reťazci alebo len s dvomi. V prvom stĺpci každej sekcie je potom konkrétny znak a v druhom stĺpci sú vypísané znaky, s ktorými susedí.

Teraz sa pozrieme na to, aké spojenia majú medzi sebou mozgové bunky. Pre jednoduchosť si ich očíslujeme, tak ako je to na obrázku 1:

Môžeme si všimnúť, že bunky 1, 3, 7 a 8 sa spájajú priamo len s dvomi inými bunkami a bunky 2, 4, 5 a 6 sa spájajú priamo s tromi inými bunkami. Keďže máme len štyri bunky, ktoré sa spájajú s tromi bunkami, tak v týchto bunkách budú musieť byť tie znaky, ktoré majú susediť s tromi inými znakmi. A potom znaky, ktoré susedia s dvomi inými znakmi budú v bunkách, ktoré sa spájajú s dvomi inými bunkami.

Teraz sa pozrieme bližšie na to, kde sa môžu jednotlivé znaky nachádzať:

Znak S má susediť s tromi znakmi, z ktorých každý susedí s ďalšími tromi znakmi. Jediná bunka, ktorá susedí s tromi inými bunkami a zároveň aj všetci jej susedia susedia s tromi bunkami, je bunka 5. Z toho vyplýva, že znak S musí byť v bunke 5.

Pozrime sa na bunky 7 a 8. Obidve z nich susedia s dvomi bunkami, sú si navzájom susedmi a ešte každá z nich susedí s jednou bunkou, ktorá susedí s tromi bunkami. Jediná dvojica znakov, z ktorých každý znak susedí s dvomi inými znakmi a jeden z týchto susedov je ten druhý znak z tejto dvojice, je dvojica N a G. To znamená, že máme dve možnosti. Buď bude v bunke 7 znak N a v bunke 8 znak G (možnosť A) alebo bude v bunke 7 znak G a v bunke 8 znak N (možnosť B). Ďalej budeme rozoberať tieto dve možnosti:

Možnosť A:

So znakom N susedí okrem znaku G ešte znak A, takže ten bude musieť byť v bunke 4. Podobne so znakom G okrem znaku N susedí ešte znak O, takže ten bude musieť byť v bunke 6. V bunke 5, ktorá susedí aj s bunkou 4 aj s bunkou 6, už máme písmeno S a to aj naozaj susedí so znakmi A a O. Jeho tretím susedom je pomlčka a tú musíme doplniť na posledného nezaplneného suseda bunky 5, čiže pomlčka bude v bunke 2. Zostáva nám už iba doplniť písmená M a K. Obidve susedia s pomlčkou. Túto podmienku spĺňajú obidve voľné bunky (bunka 1 a bunka 3). Znak M susedí ešte so znakom A, ktorý je v bunke 4, čiže znak M musíme doplniť do bunky 1. Znak K susedí okrem pomlčky aj so znakom O, ktorý je v bunke 6 a teda znak K musíme doplniť do bunky 3.

Doplnili sme všetky znaky do mozgových buniek. Teraz si overíme, či naozaj naše doplnenie spĺňa všetky podmienky zo zadania. Reťazec ANANAS-KOKOS-MANGO vieme spraviť nasledovným presunom medzi bunkami (čísla buniek sú oddelené čiarkami): 4,7,4,7,4,5,2,3,6,3,6,5,2,1,4,7,8,6.

Možnosť B:

So znakom N susedí okrem znaku G ešte znak A, takže ten bude musieť byť v bunke 6. Podobne so znakom G okrem znaku N susedí ešte znak O, takže ten bude musieť byť v bunke 4. V bunke 5, ktorá susedí aj s bunkou 4 aj s bunkou 6, už máme písmeno S a to aj naozaj susedí so znakmi A a O. Jeho tretím susedom je pomlčka a tú musíme doplniť na posledného nezaplneného suseda bunky 5, čiže pomlčka bude v bunke 2. Zostáva nám už iba doplniť písmená M a K. Obidve susedia s pomlčkou. Túto podmienku spĺňajú obidve voľné bunky (bunka 1 a bunka 3). Znak M susedí ešte so znakom A, ktorý je v bunke 6, čiže znak M musíme doplniť do bunky 3. Znak K susedí okrem pomlčky aj so znakom O, ktorý je v bunke 4 a teda znak K musíme doplniť do bunky 1.

Doplnili sme všetky znaky do mozgových buniek. Teraz si overíme, či naozaj naše doplnenie spĺňa všetky podmienky zo zadania. Reťazec ANANAS-KOKOS-MANGO vieme spraviť nasledovným presunom medzi bunkami (čísla buniek sú oddelené čiarkami): 6,8,6,8,6,5,2,1,4,1,4,5,2,3,6,8,7,4.

Záver:

Aj v možnosti A aj v možnosti B sme nemali žiadnu možnosť výberu pri doplňovaní znakov do buniek a teda sme našli všetky možnosti ako vieme doplniť znaky do mozgových buniek, aby sme vedeli vytvoriť reťazec ANANAS-KOKOS-MANGO.

Odpoveď: Sú dve možnosti ako vieme doplniť znaky do mozgových buniek tak, aby sme vedeli vytvoriť reťazec ANANAS-KOKOS-MANGO. Sú vyobrazené na obrázkoch pod možnosťou A a možnosťou B.