3288. Elementi kombinatorike

TEKST ZADATKA

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

REŠENJE ZADATKA

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

\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:

\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$ i $C :$

\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 + 24

Računamo konačan zbir:

N = 69

109