Przejście z (0,0) do (4,4); przecięcia przekątnych ośmiokąta

[Rav_DuCe]

1) Po płaszczyźnie z układem współrzędnych można wędrować w następujący sposób: z punktu (n,k) można przejść tylko do punktu (n+1,k) albo do punktu (n,k+1). Oblicz liczbę dróg prowadzących z punktu (0,0) do punktu (4,4).


2) Przekątne ośmiokąta mają tę własność że żadne trzy nie przecinają się w jednym punkcie. W ilu punktach przecinają się przekątne tego wielokąta.

[tarnoś]

Ad.1

Moim zdaniem to bedzie wygladać tak:

Aby dojść z punktu (0,0) do punktu (4,4) trzeba wykonać 4 ruchy "n+1" (oznaczmy przez n) i 4 ruchy "k+1" (oznaczmy przez k).

Otrzymujemy zbiór {n,n,n,n,k,k,k,k}, a możliwe drogi to permutacje tego z zbioru.

W naszym przypadku oczywiście permutacje z powtórzeniami (element "n" powtarza sie 4 razy i "k" tez 4 razy).

\(\displaystyle{ P_{8}^{4,4}=\frac{8!}{4! 4!}=70}\)

[Kaidorn]

moim zdaniem takie małe sprostowanie. jest to kombinacja czterech elementów z ośmiu, bo mamy jak kolega podał 8 ruchów z czego 4 poziome i 4 pionowe. zatem sprowadza się to jedynie do policzenia kombinacji 4 ruchów (obojętnie poziomych czy pionowych, te drugie są automatycznie wliczane bo):
\(\displaystyle{ C ^{4} _{8} = C ^{4} _{8} *C _{4} ^{4}}\)
liczymy więc:
\(\displaystyle{ C ^{4} _{8} = \frac{8!}{4!*4!} = 70}\)

[Piotrek172]

Sory ze odkopuje, ale zastanawiam się dlaczego tutaj jest kombinacja. Przecież jak wybierzemy drogę nnkn i druga czwórka sama się dobierze to przecież pierwsza częśc drogi jak wylosujemy nknn jest całkiem inna czyli kolejność ma znaczenie, więc nie powinna być wariancja z powtórzeniami? Jak nie to dlaczego?

[Valiors]

1) Założenie, że możemy się przemieścić z punktu (n,k) do punktu (n, k+1) lub (n+1, k), oznacza generalnie to, że z pola (n,k) możemy iść albo do sąsiedniego pola do góry, albo do sąsiedniego pola w prawo. Mamy rozstrzygnąć na ile sposobów można dojść od punktu (0,0) do punktu (4,4). Do punktu (0,0) możemy dostać się tylko na 1 sposób. Do każdego pola od (0,1) do (0,4) możemy dostać się na 1 sposób. Wynika to z tego, że możemy do nich się dostać tylko idąc w prawo. Do każdego pola od (1, 0) do (4, 0) również możemy dostać się na 1 sposób. Wynika to z tego, że możemy do nich się dostać tylko idąc w górę. Teraz korzystając z tego co już wiemy, spróbujmy wywnioskować na ile sposobów można się dostać do pola (1,1). Otóż do tego pola możemy wejść tylko z pola (0,1) lub (1,0). Zarówno do pola (1,0) jak i do pola (0,1) mogliśmy się dostać tylko na 1 sposób. Skoro do pola (1,1) możemy wejść tylko z pola (0,1) lub (1,0), a do nich mogliśmy wejść tylko na 1 sposób, to do pola (1,1) wejdziemy na 1+1 = 2 sposobów. Spójrzmy teraz na pole (1, 2). Do niego możemy wejść z pól (0,2) oraz (1, 1). Do pola (0,2) możemy wejść tylko na 1 sposób. Do pola (1, 1) możemy wejść na 2 sposoby. Zatem do pola (1, 2) możemy wejść na 1 + 2 = 3 sposoby. Analogicznie wchodzimy do pola (1,3). Możemy tam wejść tylko z pól (0, 3) oraz (1, 2) do których możemy wejść odpowiednio na 1 sposób i na 3 sposoby. Zatem do (1,3) wchodzimy na 1+3 = 4 sposoby. Widzisz już pewną własność? Oznaczmy jako P(x,y) liczbę sposobów na wejście do pola (x,y). Wtedy P(x,y) = P(x-1, y) + P(x, y - 1). Dla każdego pola licząc zgodnie z tym spostrzeżeniem, otrzymujemy, że z pola (0,0) do pola (4,4) możemy dostać się na 70 sposobów.

Rozumowanie tutaj przedstawione jest tak naprawdę bardzo podobne do programowania dynamicznego. Polega to na tym, że znajdujemy pewien wzór, spostrzeżenie i korzystamy z wyliczonych już szukanych wartości dla wcześniejszych pól by znaleźć odpowiedź dla pola w którym aktualnie się znajdujemy.

PS: Jeżeli wiesz co to jest trójkąt Pascala to pewnie zauważyłeś, że jeżeli będziemy do każdego pola wpisywać liczbę sposobów na które do tego pola możemy się dostać to otrzymamy "przewrócony" trójkąt Pascala.