Sposoby przebycia drogi

[crybe]

Zbadać na ile sposobów można dojść poruszając się tylko w prawo i w górę po punktach z punktu (10,10) do punktu (20,25), przy czym nie można przejść przez wnętrze kwadratu o przekątnej mającej końce w punktach (12,18) i (18,12) (ale można przejść po jego krawędzi)

[kerajs]

Liczyłbym trasy przechodzące przez punkt
1) (10, 20)
2) (11,19)
3) (12,18)
4) (18,12)
5) (19,11)
6) (20,10)
i je dodał.

[Jerry]

Zgadzam się z kerajsem, ale wg mnie przez punkty:
\[(18,10),(18,11),(18,12),(12,18),(12,19)(12,20),(12,21),(12,22),(12,23),(12,24),(12,22)\]
Pozdrawiam
PS.

Liczbę tras z punktu \((a,b)\) przez punkt \((c,d)\) do punktu \((e,f)\), gdzie \(\begin{cases}a\le c\le e\\ b\le d\le f\end{cases}\), określa wzór:
\[{(c-a)+(d-b)\choose c-a}\cdot{(e-c)+(f-d)\choose e-c}\]

[kerajs]

ale wg mnie przez punkty:
\[(18,10),(18,11),(18,12), ....... \]

Ponieważ z (18,10) można przejść do (18,11) oraz do (18,12), a z (18,11) można przejść do (18,12) to istnieją trasy zliczane dwu i trzykrotnie.
Wybór (18,12),(19,11),(20,10) daje rozłączne trasy dla każdego z tych punktów.

[Jerry]

Wybór (18,12),(19,11),(20,10) daje rozłączne trasy dla każdego z tych punktów.

Masz rację!

Pozdrawiam

[anilewe_MM]

Liczbę tras z punktu \((a,b)\) przez punkt \((c,d)\) do punktu \((e,f)\), gdzie \(\begin{cases}a\le c\le e\\ b\le d\le f\end{cases}\), określa wzór:
\[{(c-a)+(d-b)\choose c-a}\cdot{(e-c)+(f-d)\choose e-c}\]

Wyjaśnisz skąd to?

[Jerry]

Na przykładzie...
Poruszając się krokiem jeden w prawo albo jeden w górę z punktu \((0,0)\) do punktu \((6,6)\) musimy wykonać \(12\) kroków, z czego \(6\) w prawo i \(6\) w górę, ale w dowolnej kolejności. Wybierzmy z dwunastu pozycji sześć i na tych pozycjach poruszamy się w prawo - automatycznie na pozostałych pozycjach jest ruch do góry. Zatem wszystkich tras jest: \({12\choose6}\).

Jeśli trasa miałaby przechodzić np. przez punkt \((2,3)\), to pierwszy etap trasy możemy ustalić na \({5\choose2}\) sposobów, a drugi na \({(6-2)+(6-3)\choose 6-2}={7\choose 4}\) sposobów. Z reguły mnożenia wszystkich takich tras jest \({5\choose2}\cdot{7\choose 4}\).

Pozdrawiam