3288.

109

TEKST ZADATKA

Da bi se stiglo iz mesta A A do mesta D D može se proći kroz mesto B B ili kroz mesto C. C . Od mesta A A do B B vode tri direktna puta, od A A do C C - četiri, od B B do C C - tri, od B B do D D - dva i od C C do D D - tri direktna puta. Koliko ima mogućih puteva od A A do D D ako se kroz svako mesto prolazi najviše jednom?

REŠENJE ZADATKA

Da bismo odredili ukupan broj puteva od A A do D, D , moramo analizirati sve moguće rute koje ne prolaze kroz isto mesto više puta. Moguće rute su:

1)A→B→D2)A→C→D3)A→B→C→D4)A→C→B→D\begin{aligned} &1) A \to B \to D \\ &2) A \to C \to D \\ &3) A \to B \to C \to D \\ &4) A \to C \to B \to D \end{aligned}

Primenjujemo pravilo proizvoda za svaku pojedinačnu rutu. Broj puteva za prve dve direktne rute je:

n(A→B→D)=3⋅2=6n(A→C→D)=4⋅3=12\begin{aligned} &n(A \to B \to D) = 3 \cdot 2 = 6 \\ &n(A \to C \to D) = 4 \cdot 3 = 12 \end{aligned}

Sada računamo broj puteva za rute koje uključuju i prelaz između B B i C: C :

n(A→B→C→D)=3⋅3⋅3=27n(A→C→B→D)=4⋅3⋅2=24\begin{aligned} &n(A \to B \to C \to D) = 3 \cdot 3 \cdot 3 = 27 \\ &n(A \to C \to B \to D) = 4 \cdot 3 \cdot 2 = 24 \end{aligned}

Pošto su ove rute međusobno isključivi skupovi puteva, ukupan broj puteva dobijamo primenom pravila zbira:

N=6+12+27+24N = 6 + 12 + 27 + 24

Računamo konačan zbir:

N=69N = 69