/Konkursy/Zadania testowe/Kombinatoryka

Zadanie nr 2167331

Ile dróg prowadzi od górnego do dolnego końca przeciwprostokątnej dużego trójkąta, jeśli wolno poruszać się po bokach małych trójkątów w sposób przedstawiony na rysunku


PIC


A) 16 B) 27 C) 64 D) 90 E) 111

Wersja PDF

Rozwiązanie

Najprościej jest zastosować metodę, podobną jak przy wypisywaniu trójkąta Pascala. Tzn. będziemy się poruszać w dół po krawędziach grafu, zapamiętując w każdym wierzchołku liczbę prowadzących do niego dróg. W danym wierzchołku P wpisujemy sumę wszystkich liczb, które są w wierzchołkach, z których wychodzą krawędzie do P .


PIC


 
Odpowiedź: D

Wersja PDF
spinner