szukanie zaawansowane
 [ Posty: 8 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 16 paź 2014, o 11:53 
Użytkownik

Posty: 1
Lokalizacja: Kraków
Od dłuższego czasu próbuję rozwiązać to zadanie.

Pustynię przemierza karawana pięciu wielbłądów. Na ile sposobów można zmienić ich kolejność tak, by przed żadnym z wielbłądów nie szedł ten co przed chwilą?

Podejrzewam tutaj zastosowanie zasady włączeń i wyłączeń ale nie wiem w jaki sposób się za nią zabrać.
Góra
Kobieta Offline
PostNapisane: 17 paź 2014, o 16:11 
Użytkownik

Posty: 12
Lokalizacja: kraków
Nie jestem pewna ale wydaje mi sie,z e to bedzie Permutacja
Wielbłądy 1,2,3,4,5
{1,2,3,4,5} aby nie szedł ten co przed chwila czyli nie moze isc wielblad nr.1
{2,3,4,5,1}, {3,4,5,1,2}, i tak dalej oczywiscie zalezy w jakiej kolejnosci zapiszemy aby nie szedl ten co przed chwila wiec i tak wychodzi na to samo
wzór
Pn=n!
gdzie n= ilość elementów wyrazu, n!=ciąg wyrazowy utworzony z elementów danego zbioru,
P5= 1x2x3x4x5 P5=120
Opd:Na 120 sposobow.


Nie chce cie wprowadzac w blad ale mysle ze raczej tak bedzie.
Góra
Mężczyzna Offline
PostNapisane: 17 paź 2014, o 16:29 
Użytkownik
Avatar użytkownika

Posty: 6645
Ja stawiam na 55 sposobów.
Góra
Kobieta Offline
PostNapisane: 17 paź 2014, o 17:20 
Użytkownik

Posty: 12
Lokalizacja: kraków
jak to obliczyles?
Góra
Mężczyzna Offline
PostNapisane: 17 paź 2014, o 18:40 
Użytkownik
Avatar użytkownika

Posty: 246
Lokalizacja: Warszawa
lolkloop napisał(a):
Od dłuższego czasu próbuję rozwiązać to zadanie.

Pustynię przemierza karawana pięciu wielbłądów. Na ile sposobów można zmienić ich kolejność tak, by przed żadnym z wielbłądów nie szedł ten co przed chwilą?

Podejrzewam tutaj zastosowanie zasady włączeń i wyłączeń ale nie wiem w jaki sposób się za nią zabrać.


Mamy karawanę: \begin{array}{c} W_1 \\ W_2 \\ W_3 \\ W_4 \\ W_5 \end{array}

Niech zdarzenia
A_1 oznacza - w naszej permutacji W_1 będzie przed W_2 , tzn. mamy gdzieś w karawanie \begin{array}{c} W_1 \\ W_2 \end{array},
A_2 oznacza - mamy \begin{array}{c} W_2 \\ W_3 \end{array},

A_3 oznacza - mamy \begin{array}{c} W_3 \\ W_4 \end{array},

A_4 oznacza - mamy \begin{array}{c} W_4 \\ W_5 \end{array}

Chcemy znaleźć ilość permutacji sprzyjających zdarzeniu przeciwnemu do A_1 \cup A_2 \cup A_3 \cup A_4
Teraz możemy skorzystać z wzoru włączeń i wyłączeń, ale ostrożnie, bo być może np. |A_1 \cap A_2| \neq |A_1 \cap A_3| , ponieważ

A_1 \cap A_2 oznacza że gdzieś jest \begin{array}{c} W_1 \\ W_2 \\ W_3 \end{array},

a A_1 \cap A_3 oznacza że gdzieś jest \begin{array}{c} W_1 \\ W_2 \end{array} i \begin{array}{c} W_3 \\ W_4 \end{array}, a to trochę inaczej się liczy.

Edit - akurat tutaj nie, bo |A_1 \cap A_2| =|A_1 \cap A_3|=3!
Z potrójnymi iloczynami też trzeba się zastanowić, ale |A_i \cap A_j \cap A_k|=2 zawsze

wyszło mi 53, ale mogłem się pomylić
Góra
Mężczyzna Offline
PostNapisane: 18 paź 2014, o 00:49 
Użytkownik
Avatar użytkownika

Posty: 6645
dezire napisał(a):
jak to obliczyles?


Na paluszkach :oops:
Góra
Mężczyzna Offline
PostNapisane: 18 paź 2014, o 10:28 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
kerajs napisał(a):
Ja stawiam na 55 sposobów.

Brakuje mi dwóch sposobów do Twojego wyniku, a liczyłem w ghci tak:
Kod:
1
2
3
4
5
$> import Data.List
$> let {pred [] = True ; pred [_] = True ; pred (x:y:l) = x+1 /= y && pred (y:l)}
$> length $ filter pred $ permutations [1..5]
53


-- 18 paź 2014, o 10:46 --

mm34639 napisał(a):
Edit - akurat tutaj nie, bo |A_1 \cap A_2| =|A_1 \cap A_3|=3!
Z potrójnymi iloczynami też trzeba się zastanowić, ale |A_i \cap A_j \cap A_k|=2 zawsze

To i dla mnie było zaskoczenie, że wynik nie zależy od tego, jakie zbiory A_i,A_j,\ldots wybierzemy, ale tak musi być. Jak liczymy |A_1 \cap A_2| to łączymy wielbłądy W_1,W_2 w grubasa, a następnie otrzymanego grubasa łączymy z W_3, otrzymując jeszcze większego grubasa. W przypadku |A_1\cap A_3| łączymy W_1 i W_2 w grubasa, a następnie W_3 i W_4 w drugiego grubasa. Tak czy siak, każde połączenie zmniejsza liczbę wielbłądów o 1, więc wynik zależy tylko od liczby takich połączeń, a nie na przykład od liczby otrzymanych grubasów, czy też wielkości najgrubszego z nich. To samo dotyczy iloczynu trzech zbiorów.

mm34639 napisał(a):
wyszło mi 53, ale mogłem się pomylić

Sprawdziłem i też mi tak wyszło.
Góra
Mężczyzna Offline
PostNapisane: 18 paź 2014, o 15:56 
Użytkownik
Avatar użytkownika

Posty: 6645
Ja też sprawdziłem. Ze smutkiem muszę przyznac że maszyna liczy lepiej niz ja na paluszkach. :oops:
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 8 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Karawana wielbłądów  Wisienkaaa  0
 Okrągły stół, listy w kopertach, karawana.  Finezik  2
 Handlarze wielbłądów  skullbox  3
 Handlarze wielbłądów- dane  szpila95  2
 Przez pustynię idzie karawana...  JarTSW  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl