Witam, mam problem z jednym typem zadań związanych z kratą ulic. Poniżej treść:
Ile jest najkrótszych dróg na podanym planie miasta , które prowadzą z punktu A do B
i omijają rozkopane odcinki ulic (zaznaczone pogrubieniem)?
Posłuż się współczynnikami dwumianowymi.
Próbowałem to ugryźć posługując się zasadą włączania i wyłączania suma - część wspólna, ale nie wychodzi mi prawidłowy wynik (484). Ma ktoś jakieś pomysły?
Z góry dzięki za pomoc.
Pozdrawiam.
Krata ulic
-
mat_61
- Użytkownik
- Posty: 4618
- Rejestracja: 8 lis 2009, o 10:22
- Płeć: Mężczyzna
- Lokalizacja: Racibórz
- Pomógł: 866 razy
Krata ulic
Zasada włączania i wyłączania jest jak najbardziej OK.
Oznacz sobie rozkopane odcinki: poziomy jako CD (C po lewej) oraz pionowy jako EF (E na dole)
Wszystkie możliwe drogi, czyli 7 odcinków poziomych (P) i 5 pionowych (G) to permutacje z powtórzeniami, czyli:
\(\displaystyle{ \frac{12!}{7! \cdot 5!}=...}\)
Teraz odejmujesz drogi zawierające odcinek CD, czyli trzeba przejść drogę AC (3 odcinki P i 2 odcinki G) + odcinek CD + drogę DB (3 odcinki P i 3 odcinki G). Będzie to więc iloczyn permutacji z powtórzeniami, czyli:
\(\displaystyle{ \frac{5!}{2! \cdot 3!} \cdot \frac{6!}{3! \cdot 3!}=...}\)
Pozostaje (analogicznie) odjęcie dróg zawierających odcinek EF (czyli dróg AE + EF + FB) oraz dodanie dróg zawierających jednocześnie odcinki CD i EF (czyli dróg AC + CD + DE + EF + FB).
Oznacz sobie rozkopane odcinki: poziomy jako CD (C po lewej) oraz pionowy jako EF (E na dole)
Wszystkie możliwe drogi, czyli 7 odcinków poziomych (P) i 5 pionowych (G) to permutacje z powtórzeniami, czyli:
\(\displaystyle{ \frac{12!}{7! \cdot 5!}=...}\)
Teraz odejmujesz drogi zawierające odcinek CD, czyli trzeba przejść drogę AC (3 odcinki P i 2 odcinki G) + odcinek CD + drogę DB (3 odcinki P i 3 odcinki G). Będzie to więc iloczyn permutacji z powtórzeniami, czyli:
\(\displaystyle{ \frac{5!}{2! \cdot 3!} \cdot \frac{6!}{3! \cdot 3!}=...}\)
Pozostaje (analogicznie) odjęcie dróg zawierających odcinek EF (czyli dróg AE + EF + FB) oraz dodanie dróg zawierających jednocześnie odcinki CD i EF (czyli dróg AC + CD + DE + EF + FB).
-
abc123bb
- Użytkownik
- Posty: 9
- Rejestracja: 6 sty 2012, o 14:33
- Płeć: Mężczyzna
- Lokalizacja: mazowieckie
Krata ulic
Witam,
nie mogę sobie poradzić z bardzo podobnym zadaniem:
... ys123.jpg/
Czy ktoś może mi to wyjaśnić tak jak Kolega powyżej? Jakbym nie liczył wychodzi mi wynik 130
nie mogę sobie poradzić z bardzo podobnym zadaniem:
... ys123.jpg/
Czy ktoś może mi to wyjaśnić tak jak Kolega powyżej? Jakbym nie liczył wychodzi mi wynik 130
-
mat_61
- Użytkownik
- Posty: 4618
- Rejestracja: 8 lis 2009, o 10:22
- Płeć: Mężczyzna
- Lokalizacja: Racibórz
- Pomógł: 866 razy
Krata ulic
Wszystkie możliwe drogi AB (gdyby cały duży prostokąt był "pokreskowany"), czyli 6 odcinków poziomych (P) i 4 pionowe (G) to permutacje z powtórzeniami, czyli:
\(\displaystyle{ \frac{10!}{6! \cdot 4!}=...}\)
Teraz oznacz sobie środki boków "pustego" kwadratu kolejno zgodnie z ruchem wskazówek zegara przez C, D, E, F (C na dole). Możliwe przejścia wewnątrz tego kwadratu to drogi CF, CE, DF, DE.
Pozostaje odjęcie od wszystkich możliwych dróg AB tych zawierających drogi CF, CE, DF, DE. Ich ilość wyznacz sobie wg tej samej zasady, np. dla drogi AD(3P+2G)+DF+FB(1P+2G) mamy
\(\displaystyle{ \frac{5!}{3! \cdot 2!} \cdot \frac{3!}{1! \cdot 2!} =...}\)
Analogicznie zrób dla dróg AD+DE+EB, AC+CF+FB, AC+CE+EB
-------------------------
Same obliczenia można uprościć zauważając, że ilość możliwych przejść dla dróg EB oraz FB jest taka sama.
-- 6 sty 2012, o 16:13 --
Oczywiście zgodnie z treścią zadania można posłużyć się współczynnikami dwumianowymi Newtona. Nawet zapis rachunkowy jest taki sam, tylko inne "uzasadnienie" zastosowanego wzoru.
Np. dla wszystkich dróg mamy do pokonania 10 odcinków (6P+4G).
Można więc powiedzieć, że mamy do ułożenia w kolejności 10 elementów (6 elementów P oraz 4 elementy G) - jest to więc permutacja z powtórzeniami.
Można także powiedzieć, że wybieramy 6 "miejsc" z 10 w których umieścimy elementy P (na pozostałych będą elementy G) lub wybieramy 4 "miejsca" z 10 w których umieścimy elementy G (na pozostałych będą elementy P). W tym przypadku posłużymy się współczynnikami dwumianowymi Newtona (kombinacje).
Jest to związane z tym, że jeżeli mamy n-elementową permutację z powtórzeniami ze zbioru 2-elementowego \(\displaystyle{ \left\{ a_{1}; a_{2}\right\}}\) w której element \(\displaystyle{ a_{1}}\) powtarza się \(\displaystyle{ k}\) razy \(\displaystyle{ (k<n)}\) , to:
\(\displaystyle{ P_{n}^{k,n-k}=C_{n}^{k}}\)
\(\displaystyle{ \frac{10!}{6! \cdot 4!}=...}\)
Teraz oznacz sobie środki boków "pustego" kwadratu kolejno zgodnie z ruchem wskazówek zegara przez C, D, E, F (C na dole). Możliwe przejścia wewnątrz tego kwadratu to drogi CF, CE, DF, DE.
Pozostaje odjęcie od wszystkich możliwych dróg AB tych zawierających drogi CF, CE, DF, DE. Ich ilość wyznacz sobie wg tej samej zasady, np. dla drogi AD(3P+2G)+DF+FB(1P+2G) mamy
\(\displaystyle{ \frac{5!}{3! \cdot 2!} \cdot \frac{3!}{1! \cdot 2!} =...}\)
Analogicznie zrób dla dróg AD+DE+EB, AC+CF+FB, AC+CE+EB
-------------------------
Same obliczenia można uprościć zauważając, że ilość możliwych przejść dla dróg EB oraz FB jest taka sama.
-- 6 sty 2012, o 16:13 --
Oczywiście zgodnie z treścią zadania można posłużyć się współczynnikami dwumianowymi Newtona. Nawet zapis rachunkowy jest taki sam, tylko inne "uzasadnienie" zastosowanego wzoru.
Np. dla wszystkich dróg mamy do pokonania 10 odcinków (6P+4G).
Można więc powiedzieć, że mamy do ułożenia w kolejności 10 elementów (6 elementów P oraz 4 elementy G) - jest to więc permutacja z powtórzeniami.
Można także powiedzieć, że wybieramy 6 "miejsc" z 10 w których umieścimy elementy P (na pozostałych będą elementy G) lub wybieramy 4 "miejsca" z 10 w których umieścimy elementy G (na pozostałych będą elementy P). W tym przypadku posłużymy się współczynnikami dwumianowymi Newtona (kombinacje).
Jest to związane z tym, że jeżeli mamy n-elementową permutację z powtórzeniami ze zbioru 2-elementowego \(\displaystyle{ \left\{ a_{1}; a_{2}\right\}}\) w której element \(\displaystyle{ a_{1}}\) powtarza się \(\displaystyle{ k}\) razy \(\displaystyle{ (k<n)}\) , to:
\(\displaystyle{ P_{n}^{k,n-k}=C_{n}^{k}}\)
-
abc123bb
- Użytkownik
- Posty: 9
- Rejestracja: 6 sty 2012, o 14:33
- Płeć: Mężczyzna
- Lokalizacja: mazowieckie
Krata ulic
Dziękuję Ci serdecznie za pomoc w rozwiązaniu!
Nie rozumiem czy dobrze to zakreślam [te punkty]:
Tak to ma być zaznaczone? Chyba coś źle zrobiłem bo wtedy nie mogę wyznaczyć tych dróg co powiedziałeś [np. nie mogę wyznaczyć DE].
Help...
Pozdrawiam,
Bartek.
Nie rozumiem czy dobrze to zakreślam [te punkty]:
Tak to ma być zaznaczone? Chyba coś źle zrobiłem bo wtedy nie mogę wyznaczyć tych dróg co powiedziałeś [np. nie mogę wyznaczyć DE].
Help...
Pozdrawiam,
Bartek.
-
mat_61
- Użytkownik
- Posty: 4618
- Rejestracja: 8 lis 2009, o 10:22
- Płeć: Mężczyzna
- Lokalizacja: Racibórz
- Pomógł: 866 razy
Krata ulic
Tak.abc123bb pisze:Tak to ma być zaznaczone?
Określenie droga DE nie oznacza, że jest to odcinek łączący punkty D i E, tylko drogę między tymi punktami. Ponieważ każda z tych dróg przebiegająca po "zakazanym" terenie, jest jednoznacznie wyznaczalna (np. droga DE to "jeden krok" w prawo i "jeden krok" do góry) to takie określenie jest poprawne.abc123bb pisze:Chyba coś źle zrobiłem bo wtedy nie mogę wyznaczyć tych dróg co powiedziałeś [np. nie mogę wyznaczyć DE].
Dla ułatwienia możesz dorysować przerywaną linią odcinki DF i CE oznaczające cztery "odcinki jednostkowe" po których nie wolno chodzić.
-- 6 sty 2012, o 18:25 --
Dla napisania odnośnika dostępnego bezpośrednio (bez konieczności kopiowania adresu) umieść adres w znacznikach
Kod: Zaznacz cały
[url]...[/url]