Sposoby przebycia drogi

Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
crybe
Dopiero zaczynam
Dopiero zaczynam
Posty: 15
Rejestracja: 27 lut 2023, 18:44
Podziękowania: 7 razy
Płeć:

Sposoby przebycia drogi

Post autor: 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
Fachowiec
Fachowiec
Posty: 2954
Rejestracja: 14 lis 2016, 15:38
Podziękowania: 33 razy
Otrzymane podziękowania: 1297 razy
Płeć:

Re: Sposoby przebycia drogi

Post autor: 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ł.
Awatar użytkownika
Jerry
Expert
Expert
Posty: 3423
Rejestracja: 18 maja 2009, 09:23
Podziękowania: 50 razy
Otrzymane podziękowania: 1867 razy

Re: Sposoby przebycia drogi

Post autor: 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
Fachowiec
Fachowiec
Posty: 2954
Rejestracja: 14 lis 2016, 15:38
Podziękowania: 33 razy
Otrzymane podziękowania: 1297 razy
Płeć:

Re: Sposoby przebycia drogi

Post autor: kerajs »

Jerry pisze: 07 lut 2024, 22:27 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.
Awatar użytkownika
Jerry
Expert
Expert
Posty: 3423
Rejestracja: 18 maja 2009, 09:23
Podziękowania: 50 razy
Otrzymane podziękowania: 1867 razy

Re: Sposoby przebycia drogi

Post autor: Jerry »

kerajs pisze: 08 lut 2024, 09:43 Wybór (18,12),(19,11),(20,10) daje rozłączne trasy dla każdego z tych punktów.
Masz rację!

Pozdrawiam
anilewe_MM
Czasem tu bywam
Czasem tu bywam
Posty: 121
Rejestracja: 12 paź 2021, 17:26
Podziękowania: 532 razy
Płeć:

Re: Sposoby przebycia drogi

Post autor: anilewe_MM »

Jerry pisze: 07 lut 2024, 22:27 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?
Awatar użytkownika
Jerry
Expert
Expert
Posty: 3423
Rejestracja: 18 maja 2009, 09:23
Podziękowania: 50 razy
Otrzymane podziękowania: 1867 razy

Re: Sposoby przebycia drogi

Post autor: 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