3289.

110

TEKST ZADATKA

Od trga A do trga B vode dve jednosmerne ulice presečene sa 7 dvosmernih ulica. Na koliko načina vozač može stići sa trga A na trg B ako svakom dvosmernom ulicom prođe najviše jednom?


REŠENJE ZADATKA

Zamislimo dve jednosmerne ulice kao dve paralelne putanje koje vode od trga A A do trga B. B . Sedam dvosmernih ulica možemo posmatrati kao poprečne 'mostove' koji spajaju ove dve putanje na 7 mesta.

Na samom početku, vozač mora da izabere kojom od dve jednosmerne ulice će krenuti sa trga A. A . Za ovaj početni izbor on ima tačno 2 mogućnosti.

Kada vozač dođe do prve dvosmerne ulice, on donosi novu odluku: može da nastavi kretanje pravo istom jednosmernom ulicom, ili da skrene i pređe preko dvosmerne ulice na drugu jednosmernu ulicu. Dakle, na ovoj raskrsnici ima 2 mogućnosti.

Potpuno isti izbor vozač ima na svakoj od 7 dvosmernih ulica. Uslov da svakom dvosmernom ulicom prođe najviše jednom osigurava da se vozač ne može vraćati istom dvosmernom ulicom nazad, već nakon eventualnog prelaska mora nastaviti kretanje napred ka trgu B. B .

Pošto su svi ovi izbori nezavisni jedan od drugog, primenjujemo pravilo proizvoda. Ukupan broj načina dobijamo množenjem broja mogućnosti za svaki pojedinačni izbor.

Množimo 2 mogućnosti za izbor početne ulice sa po 2 mogućnosti na svakoj od 7 raskrsnica sa dvosmernim ulicama:

22227 puta=2272 \cdot \underbrace{2 \cdot 2 \cdot \dots \cdot 2}_{7 \text{ puta}} = 2 \cdot 2^7

Računamo konačan rezultat:

28=2562^8 = 256