Táto úloha je teoretická. Ako svoje riešenie odovzdaj pdf súbor, v ktorom bude tvoje riešenie aj so zdôvodnením, prečo je správne. Po konci kola ti riešenie opraví vedúci, a napíše ti komentár – povie ti kde si spravil(a) chyby, prípadne ti poradí ako vieš svoje riešenia zlepšiť.

Ak máš hocijaké otázky k tejto úlohe, napíš Štepimu na [email protected] alebo Soni na [email protected] .

Konečne sa Štepi, Hanka a Miška naozaj vydali domov. Naložili si všetky veci do loďky a vytiahli mapy, ktoré im daroval Strížožírts. Tie mapy však boli iné ako poznali! Bola to iba zmes kratších a dlhších čiar, z ktorých vôbec nebolo jasné ako vyzerá rieka, po ktorej sa majú plaviť. Zmätene sa na seba pozreli a s prosbou o pomoc sa obrátili na Teba.

Amazonka je rozvetvený riečny systém, pričom rieka sa môže v nejakom mieste rozdeľovať na dve alebo sa dve môžu spojiť do jednej. Roky si domorodci kreslia mapy riek a to takým spôsobom, že vždy keď idú po nejakej trase, tak si zaznamenajú aké prítoky po ceste vidia. Ak loď odbočuje na rozdvojke doľava, potom posádka vidí rameno na pravej strane, čo zakreslia do mapy takto:

Ak sa spájajú dva prítoky a loď prichádza tým z prava, potom druhý prítok vidia po svojej ľavej ruke, čo zakreslia takto:

a. (10 bodov) Ako by vyzerala mapa, ktorú zakreslí posádka, ak prechádza po vyznačenej trase v riečnej sieti?

Na cestu späť dostali moreplavci pod vedením Štepiho pre istotu týchto máp viacej. No na to, aby sa bezpečne dostal domov, by potreboval vedieť ako vyzerá celý riečny systém.

b. (20 bodov) Podľa nasledujúcich 3 máp zisti ako vyzerá celý riečny systém, ktorý popisujú tieto mapy. Všetky mapy začínajú v jednom bode a aj končia v jednom bode. V mapách je dokopy zakreslená celá sieť, nemôže sa stať, že by tam bola ešte nejaká vetva, ktorá nie je na žiadnej mape.

Moreplavci však došli na koniec mapy. Preto vystúpili v najbližšej dedine a kúpili si nové mapy. Najbližší úsek trasy čo ich čakal bol však zložitejší.

c. (20 bodov) Zisti ako vyzeral ďalší úsek riečneho systému, ak Štepi dostal tieto 4 mapy:

Keď už mal Štepi zakreslený celý riečny systém, zistil, že ho vie prejsť viacerými spôsobmi. Teraz by ho zaujímalo koľko rôznych ciest existuje.

d. (20 bodov) Zisti koľkými spôsobmi vie Štepi preplávať cez tento riečny systém, teda koľko je rôznych ciest, ktorými sa dá preplaviť z ľavého konca na pravý.

e. (30 bodov) Vymysli nejaký postup, ktorým sa dá vyriešiť úloha ako b) aj c) pre ľubovoľné zadané mapy. Stále môžeš predpokladať, že každý úsek rieky sa nachádza aspoň na jednej mape.