Odpowiedź:

W poniższym rozwiązaniu przez n(K, L) rozumieć będziemy liczbę wszystkich najkrótszych dróg z punktu K do punktu L. Symbol C(n, k) oznacza symbol Newtona („n po k”).

Zaznaczmy na schemacie ulic punkty C, D, E, F, G (zobacz rysunek 1.).

Zauważmy, że każda najkrótsza droga z A do B musi przechodzić przez któryś z punktów C, D, E, F lub G. Ponadto, liczba wszystkich najkrótszych dróg z A do B przechodzących przez C jest równa n(A, C) · n(C, B). Analogicznie, liczba wszystkich najkrótszych dróg z A do B przechodzących przez D jest równa n(A, D) · n(D, B) itd.

Obliczymy n(A, C), czyli liczbę wszystkich najkrótszych dróg z A do C. Kierunek wyznaczony na rysunku 1. przez prostą AG nazwiemy poziomym, a kierunek prostopadły do poziomego – pionowym. Każda najkrótsza droga z A do C składa się z dokładnie 11 odcinków: 2 poziomych i 9 pionowych. Wskazanie 2 odcinków (spośród 11), które mają być poziome, określa nam jednoznacznie najkrótszą drogę z A do C. Stąd najkrótszych dróg z A do C jest C(11, 2). (Przykładowo: jedna z takich dróg ma poziome odcinki trzeci i ósmy, a pozostałe pionowe; inna – odcinki szósty i jedenasty.)

Podobnie rozumując, otrzymujemy

n(A, C) · n(C, B) = C(11, 2) · C(13, 0) = 55 · 1 = 55
n(A, D) · n(D, B) = C(11, 3) · C(13, 1) = 165 · 13 = 2145
n(A, E) · n(E, B) = C(11, 4) · C(13, 2) = 330 · 78 = 25740
n(A, F) · n(F, B) = C(13, 1) · C(11, 3) = 13 · 165 = 2145
n(A, G) · n(G, B) = C(13, 0) · C(11, 2) = 1 · 55 = 55

więc n(A, B) = 55 + 2145 + 25740 + 2145 + 55 = 30140.

Rysunek 1. Schemat ulic z zaznaczonymi punktami C, D, E, F, G przy parku
schemat punktacji

4 pkt – zastosowanie poprawnej metody i poprawny wynik.
3 pkt – obliczenie liczby wszystkich najkrótszych dróg z A do K (gdzie K ∈ {C, D, E, F, G}).
2 pkt – zapisanie, że liczba wszystkich najkrótszych dróg z A do B przechodzących przez punkt K (gdzie K ∈ {C, D, E, F, G}) jest iloczynem liczby wszystkich najkrótszych dróg z A do K i liczby wszystkich najkrótszych dróg z K do B.
1 pkt – zapisanie, że każda najkrótsza droga z A do B musi przechodzić przez jeden z punktów C–G.
0 pkt – rozwiązanie, w którym zastosowano niepoprawną metodę, albo brak rozwiązania.