szukanie zaawansowane
 [ Posty: 26 ]  Przejdź na stronę 1, 2  Następna strona
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 7 lut 2015, o 16:21 
Użytkownik

Posty: 1439
Lokalizacja: Warszawa
Dana jest grupa złożona z 3 Chińczyków, 3 Polaków i 3 Rosjan. Na ile sposobów można ustawić te osoby tak, żeby nikt nie miał za sąsiada swojego rodaka?

Próbowałem "od tyłu", licząc wszystkie ustawienia, w których trafią się obok siebie krajanie, ale wyszło dużo skomplikowanych przypadków i kilkakrotne użycie zasady włączeń i wyłączeń. Zresztą nie wiem, jak sobie poradzić ze zliczaniem cząstkowym w niektórych miejscach. Można jakoś prościej?
Góra
Mężczyzna Offline
PostNapisane: 7 lut 2015, o 17:59 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
Można ustawiać w szeregu, w kółeczku, albo w jakiś bardziej wymyślny sposób. Czy chcesz zliczać to wszystko?
Góra
Mężczyzna Offline
PostNapisane: 7 lut 2015, o 18:08 
Użytkownik

Posty: 1439
Lokalizacja: Warszawa
Nie napisałem czegoś, co było w poleceniu, a wydawało mi się oczywiste: ustawiamy w rzędzie.
Góra
Mężczyzna Offline
PostNapisane: 7 lut 2015, o 18:17 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
Tak przypuszczałem, ale wolałem się upewnić.

Jeśli chcesz to zliczać ręcznie, to można się ograniczyć do ustawień z ustalonymi pierwszymi dwiema osobami, a na końcu wynik pomnożyć przez 6. Możliwości nie jest bardzo dużo, ale i tak ręczna metoda nie jest szczególnie zachęcająca. Jeszcze pomyślę nad tym.
Góra
Mężczyzna Offline
PostNapisane: 10 lut 2015, o 03:31 
Użytkownik

Posty: 1439
Lokalizacja: Warszawa
Nie wiem, co masz na myśli, pisząc: "jeśli chcesz to zliczać ręcznie". Chcę to po prostu zliczyć. Oczywiście im szybszą metodą, tym lepiej. Nie mam innego pomysłu na rozwiązanie niż taki:

Niech S oznacza zbiór wszystkich możliwych ustawień tych ludzi, P to te ustawienia, w których znajdzie się koło siebie dwóch Polaków, R - Rosjan, C - Chińczyków.
Wówczas |S|=9! i szukamy |S\setminus(P\cup R\cup C)|=|S|-|P\cup R\cup C|. Do znalezienia |P\cup R\cup C| zastosujemy zasadę włączeń i wyłączeń.

Zacznijmy od znalezienia |P|. Ustawienia, w których znajdzie się obok siebie dwóch Polaków, możemy rozdzielić na takie, w których stoją obok siebie wszyscy trzej, i takie, w których stoi obok siebie dokładnie dwóch. W pierwszym przypadku wybieramy 1 z 7 miejsc dla tej trójki, następnie permutujemy ją oraz permutujemy pozostałą szóstkę. W drugim wypadku ustalmy najpierw ustawienie nie-Polaków. Między nimi i na skrajach mamy 7 miejsc, które możemy zaproponować dwójce Polaków. Po usadzeniu tej dwójki mamy 6 miejsc dla pojedynczego Polaka. Pozostaje spermutować Polaków na wybranych dla nich miejscach i spermutować pozostałych. Stąd

|P|=7\cdot3!\cdot6!+7\cdot6\cdot3!\cdot6!=7!\cdot42

Obliczamy |P\cap R|. Możemy tutaj rozróżnić następujące przypadki:
1) obie nacje wystąpią trójkami;
2) jedna nacja wystąpi trójką, druga dwójką i pojedynczo;
3) obie nacje wystąpią w dwójce i pojedynczo.

W każdym z tych przypadków ważny jest odpowiedni wybór miejsc dla poszczególnych narodowości, natomiast niezależnie od konfiguracji trzeba będzie spermutować każdą z tych trójek ludzi. Dlatego dla wygody wystarczy liczyć jedynie sposoby wyboru miejsc, a sumę pomnożyć na końcu przez (3!)^3.
1) Wybieramy 1 z 5 miejsc dla trójki Polaków, następnie 1 z 4 dla trójki Rosjan.
2) Wybieramy na 2 sposoby, która nacja ma wystąpić w trójce. Mamy 4 możliwości ustawienia tej trójki z trzema Chińczykami. W tym momencie w rzędzie znajduje się 6 miejsc dla dwójki Polaków, a w kolejnym kroku 5 miejsc dla pojedynczego.
3) Niech X oznacza dwójkę lub pojedynczą osobę z jednej nacji, Y z drugiej. Mamy trzy podprzypadki rozmieszczenia iksów i igreków, zanim dołożymy do rzędu Chińczyków.
a) XXYY
b) XYYX
c) XYXY

W każdym z podprzypadków możemy wybrać na 2 sposoby, która nacja jest iksem, na 2 sposoby, który iks oznacza dwójkę ludzi, na 2, który igrek oznacza dwójkę.
a) Należy rozdzielić stojące obok siebie iksy i igreki. Zatem wstawiamy po jednym Chińczyku między iksy i między igreki. Trzeci ma do dyspozycji 5 miejsc.
b) Iksy są rozdzielone, więc jeden Chińczyk musi rozdzielić igreki, a pozostali dwaj mają do wyboru dowolne 2 miejsca z 6.
c) Wszyscy są rozdzieleni, więc wybieramy dla Chińczyków dowolne 3 miejsca z 7.

|P\cap R|=(3!)^3\left(5\cdot4+2\cdot4\cdot6\cdot5+2^3\left( 5+ {6 \choose 2}+{7\choose3} \right)\right)=6^3\cdot676

Obliczamy |P\cap R\cap C|. Przypadki:
1) wszystkie trzy nacje w trójkach;
2) dwie nacje w trójce, trzecia w dwójce i pojedynczo
3) jedna nacja w trójce, pozostałe w dwójkach i pojedynczo
4) wszystkie nacje w dwójce i pojedynczo

1) Ustalamy na 3! sposobów kolejność trójek.
2) Wybieramy na 3 sposoby, która nacja ma być rozdzielona. Wybieramy 1 z 3 miejsc dla dwójki, 1 z 2 dla pojedynczej osoby. Wybieramy 1 z 2 kolejności dla trójek.
3) Niech Z oznacza trójkę. Na podstawie wcześniejszych rozważań wiemy, że taki układ może być albo postaci XYZYX albo XYXY z trójką Z dołączoną w dowolne z 5 miejsc. Mamy zatem 3! sposobów przypisania literom nacji, 2 na zdecydowanie, który iks jest dwójką, 2 na to, który igrek jest dwójką, i łącznie 6 możliwości dołączenia trójki Z.
4) Przyjmijmy oznaczenia: p - dwójka Polaków lub jeden Polak, r - dwójka Rosjan lub jeden Rosjanin, c - dwójka Chińczyków lub jeden Chińczyk. Wówczas szukane przypadki można sprowadzić do pytania o to, ile jest słów powstałych z liter p,p,r,r,c,c, w których żadne dwie litery nie stoją obok siebie. Odejmę od wszystkich możliwych słów te, w których jakiekolwiek dwie litery się powtarzają. Skorzystam w tym celu z gotowego wzoru na liczbę permutacji z powtórzeniami i zasady włączeń wyłączeń. Szczegóły pominę, prezentując same rachunki.

\frac{6!}{2^3}-3\cdot5\cdot\frac{4!}{2^2}+3\cdot4\cdot3-3!=30

Pozostaje teraz zdecydować na 2^3 sposobów, która litera oznacza w danym ustawieniu dwójkę Polaków, dwójkę Rosjan i dwójkę Chińczyków.

|P\cap R\cap C|=(3!)^3\left(3!+3^2\cdot2^2+3!\cdot2^2\cdot6+2^3\cdot30\right)=6^3\cdot426

Ostatecznie
|S|-|P\cup R\cup C|=9!-3\cdot7!\cdot42+3\cdot6^3\cdot676-6^3\cdot426=73872




Rozwiązanie jest długie i niezachęcające. Nie potrafię wymyślić krótszego, ponieważ nie umiem obejść jednego problemu, który odpowiada za to zamieszanie i który było widać już przy obliczaniu |P|, a złożoność obliczeń w kolejnych krokach była właśnie jego następstwem.
Kiedy np. liczymy sytuacje, w których trafi się obok siebie dwóch Polaków, to musimy wziąć pod uwagę zarówno dwóch, jak i trzech. Gdybyśmy zaczęli liczyć to w taki sposób, że ustawiamy dwóch, bo tyle nam do szczęścia wystarczy, a resztą się nie przejmujemy, wtedy ustawienia z trójką Polaków policzylibyśmy kilkakrotnie. I o ile w tym wypadku dałoby się to jakoś skontrolować, tzn. stwierdzić, ile razy za dużo wystąpiła każda z trójek i odjąć to od liczby wszystkich możliwych dwójek, to kiedy rozważamy już wystąpienia choćby dwóch nacji, sytuacja staje się dla mnie zbyt skomplikowana, żeby można ją było w ten sposób skontrolować. Dlatego nie widzę innej możliwości niż takie babranie się w przypadkach i bardzo jestem ciekaw, czy da się to zrobić mądrzej.
Góra
Mężczyzna Offline
PostNapisane: 11 lut 2015, o 20:11 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
Chodziło mi o coś takiego:

PRPRCPCRC\\
PRPRCRCPC\\
PRPCPRCRC\\
PRPCPCRCR\\
PRPCRPCRC\\
PRPCRCPRC\\
PRPCRCPCR\\
PRPCRCRPC\\
PRPCRCRCP\\
PRCPRPCRC\\
PRCPRCPRC\\
PRCPRCPCR\\
PRCPRCRPC\\
PRCPRCRCP\\
PRCPCPRCR\\
PRCPCRPRC\\
PRCPCRPCR\\
PRCPCRCPR\\
PRCPCRCRP\\
PRCRPRCPC\\
PRCRPCPRC\\
PRCRPCPCR\\
PRCRPCRPC\\
PRCRPCRCP\\
PRCRCPRPC\\
PRCRCPRCP\\
PRCRCPCPR\\
PRCRCPCRP\\
PRCRCRPCP.

Następnie mnożymy wynik (29) przez 6 (o czym wcześniej pisałem) i przez (3!)^3 (o czym poprzednio zapomniałem).
Góra
Mężczyzna Offline
PostNapisane: 12 lut 2015, o 17:20 
Użytkownik
Avatar użytkownika

Posty: 3469
Lokalizacja: blisko
A czy wy rozróżniacie np dwóch rosjan między sobą?
Góra
Mężczyzna Offline
PostNapisane: 12 lut 2015, o 17:30 
Użytkownik

Posty: 1439
Lokalizacja: Warszawa
Majeskas napisał(a):
wybieramy 1 z 7 miejsc dla tej trójki, następnie permutujemy ją oraz permutujemy pozostałą szóstkę. W drugim wypadku ustalmy najpierw ustawienie nie-Polaków. Między nimi i na skrajach mamy 7 miejsc, które możemy zaproponować dwójce Polaków. Po usadzeniu tej dwójki mamy 6 miejsc dla pojedynczego Polaka. Pozostaje spermutować Polaków na wybranych dla nich miejscach i spermutować pozostałych



Cytuj:
W każdym z tych przypadków ważny jest odpowiedni wybór miejsc dla poszczególnych narodowości, natomiast niezależnie od konfiguracji trzeba będzie spermutować każdą z tych trójek ludzi. Dlatego dla wygody wystarczy liczyć jedynie sposoby wyboru miejsc, a sumę pomnożyć na końcu przez (3!)^3.



norwimaj napisał(a):
Następnie mnożymy wynik (29) przez 6 (o czym wcześniej pisałem) i przez (3!)^3 (o czym poprzednio zapomniałem).
Góra
Mężczyzna Offline
PostNapisane: 12 lut 2015, o 17:38 
Użytkownik
Avatar użytkownika

Posty: 3469
Lokalizacja: blisko
Ja to tak widzę:

3 \cdot  {3 \choose 2} \cdot (2!)^1 \cdot 8!-3 \cdot  {3 \choose 2} \cdot {3 \choose 2}(2!)^2 \cdot 7!+{3 \choose 2} \cdot {3 \choose 2}\cdot {3 \choose 2} \cdot (2!)^3 \cdot 6!

Najpierw wybieramy tylko jedną parę z trzech narodowości możliwości jest trzy po dwa, w każdej grupe narodowości, mnożymy przez trzy bo jedną parę można wybrać z trzech narodowości!

potem wybieramy już dwie pary na trzy możliwości(zawsze z dwcóh narodowości) i permutujemy,

na końcu wybieramy aż trzy pary z trzech narodowości i też permutujemy!

W rozpisce Norwimaja przestawienie np dwóch Chińczyków nie zmienia sytuacji a ja uważam, że powinno być:

p1,p2,p3,r1,r2,r3,c1,c2,c3

a nie:

p,p,p,r,r,r,c,c,c

w tym ostatnim pomyśle różnice by były między:

p,p,r,p,r,r,c,c,c

a:

p,r,p,p,r,r,c,c,c

Sytuacja by się bardziej skomplikowała bo np para polaków i jeden polak to np dla rosjan dwa różne obiektu a dla polaków między sobą takie same!

-- 15 lutego 2015, 15:54 --

Jeżeli nie rozróżniamy ludzi jednej narodowości to wtedy wynik wychodzi:

107
Góra
Mężczyzna Offline
PostNapisane: 19 lut 2015, o 22:28 
Użytkownik

Posty: 1439
Lokalizacja: Warszawa
arek1357 napisał(a):
Ja to tak widzę:

3 \cdot  {3 \choose 2} \cdot (2!)^1 \cdot 8!-3 \cdot  {3 \choose 2} \cdot {3 \choose 2}(2!)^2 \cdot 7!+{3 \choose 2} \cdot {3 \choose 2}\cdot {3 \choose 2} \cdot (2!)^3 \cdot 6!

Najpierw wybieramy tylko jedną parę z trzech narodowości możliwości jest trzy po dwa, w każdej grupe narodowości, mnożymy przez trzy bo jedną parę można wybrać z trzech narodowości!

potem wybieramy już dwie pary na trzy możliwości(zawsze z dwcóh narodowości) i permutujemy,

na końcu wybieramy aż trzy pary z trzech narodowości i też permutujemy!



Zrozumiałem z tego tylko tyle (czego też nie jestem pewien), że podobnie jak ja, zliczasz wszystkie te ustawienia, w których pewna para tej samej narodowości wystąpi koło siebie. Ale nie wiem, co te skrótowe opisy mają wspólnego z problemem.

arek1357 napisał(a):

W rozpisce Norwimaja przestawienie np dwóch Chińczyków nie zmienia sytuacji a ja uważam, że powinno być:

p1,p2,p3,r1,r2,r3,c1,c2,c3

a nie:

p,p,p,r,r,r,c,c,c



norwimaj napisał(a):

Następnie mnożymy wynik (29) przez 6 (o czym wcześniej pisałem) i przez (3!)^3 (o czym poprzednio zapomniałem).


Owszem, Norwimaj wypisał po prostu wszystkie możliwe ustawienia trzech grup trzyosobowych bez przypisywania im narodowości i osób, a następnie uwzględnił te różnice. Mnożenie przez (3!)^3 odpowiada właśnie za to, na co zwróciłeś uwagę, tj. przypisanie konkretnych osób w grupach.

Cytuj:
w tym ostatnim pomyśle różnice by były między:

p,p,r,p,r,r,c,c,c

a:

p,r,p,p,r,r,c,c,c

Sytuacja by się bardziej skomplikowała bo np para polaków i jeden polak to np dla rosjan dwa różne obiektu a dla polaków między sobą takie same!


Nie rozumiem.


Cytuj:
Jeżeli nie rozróżniamy ludzi jednej narodowości to wtedy wynik wychodzi:

107


Moim zdaniem przy takiej treści powinniśmy wszystkich rozróżniać. Gdybyśmy mieli nie rozróżniać ludzi, pytanie powinno raczej brzmieć: "Na ile sposobów możemy wybrać miejsca w rzędzie dla Polaków, Rosjan i Chińczyków, tak aby…?".
Nawiasem mówiąc, nie ma to jakiegoś szczególnego znaczenia dla trudności zadania, bo ona leży właśnie w zliczeniu wyborów tych miejsc, a rozróżnialność czy nierozróżnialność ludzi to tylko kwestia pomnożenia albo niepomnożenia tej liczby przez 6^3. Tak jak to było u Norwimaja.

Co do wyniku 107, to nie wiem, skąd się wziął i co może mieć wspólnego z tym, który podałeś na początku posta. Jeśli chodzi o wyniki moje i Norwimaja, to ciężka sprawa. Wyszło mi niemal dwukrotnie więcej. Metoda Norwimaja jest na pewno poprawna, tylko niełatwo sprawdzić, czy faktycznie wypisał wszystkie możliwości. Chyba jeszcze gorzej znaleźć błąd w moim długim, zawiłym rozumowaniu, choć jeśli ktoś go widzi, to będę wdzięczny.
Najlepszy byłby komputer, który wypisałby wszystko i policzył.
Góra
Mężczyzna Offline
PostNapisane: 20 lut 2015, o 13:14 
Użytkownik
Avatar użytkownika

Posty: 3469
Lokalizacja: blisko
107 liczyłem przypadek gdy nie rozróżniamy ludzi tej samej narodowości!
A pierwszy wzór dla przypadków gdy rozróżniamy ludzi jednakowej narodowości.
Góra
Mężczyzna Offline
PostNapisane: 20 lut 2015, o 14:41 
Użytkownik

Posty: 1439
Lokalizacja: Warszawa
W takim razie 107\cdot6^3 powinno dać ten pierwszy wzór, a nie daje.
Góra
Mężczyzna Offline
PostNapisane: 20 lut 2015, o 15:05 
Użytkownik
Avatar użytkownika

Posty: 3469
Lokalizacja: blisko
A czy na pewno jest wzór zły?
Góra
Mężczyzna Offline
PostNapisane: 20 lut 2015, o 15:26 
Użytkownik

Posty: 1439
Lokalizacja: Warszawa
Nie wiem. Zupełnie nie rozumiem, skąd się wziął, i o to spytałem wyżej.
Góra
Mężczyzna Offline
PostNapisane: 20 lut 2015, o 15:30 
Użytkownik
Avatar użytkownika

Posty: 3469
Lokalizacja: blisko
Zastosuj ten mój wzór poprzez analogię na przypadek dwóch Polaków i dwóch Rosjan , mamy:

p_{1},p_{2},r_{1},r_{2}

łatwo zauważyć ustawiając ich na piechotę, że możliwości , że nie stoją obok siebie dwóch z jednej narodowości jest osiem , a teraz zastosujmy moje rozumowanie poprzez analogię do mojego wzoru i otrzymamy (na to że stoją koło siebie):

2 \cdot  {2 \choose 2} \cdot 2! \cdot 3!- {2 \choose 2} \cdot  {2 \choose 2} \cdot (2!)^2 \cdot 2!=16

Czyli wychodzi osiem!


Pierwsza kombinacja to wybór dwóch Polaków z grupy dwóch Polaków lub dwóch Rosjan z grupy dwóch Rosjan(na dwa sposoby) i masz jedną parę i dwóch ludzi do permutowania między sobą razem trzy!

Potem wybierasz już dwóch Polaków z grupy dwóch Polaków i dwóch Rosjan z grupy Dwóch Rosjan (już tylko jeden sposób)
co daje dwie pary , które permutujesz również.

A na koniec stosujesz zasadą włączeń i wyłączeń czyli odejmujesz!


Sprawdza się to też przy dwóch Polakach, dwóch Rosjanach i dwóch Chińczykach!

To zadanie i to drugie z liczbami stojącymi koło siebie to bardzo podobne zadania do obu zastosowałem ten sam tok postępowania!

A teraz jak nie rozróżniasz ludzi tej samej narodowości otrzymujesz:

p,r,p,r

lub:

r,p,r,p

czyli dwie możliwości odpowiednik tego 107 możliwości dla dziewięciu ludzi o trzech narodowościach (przy nierozróżnianiu tej samej narodowości)!
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 26 ]  Przejdź na stronę 1, 2  Następna strona


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Podział 24-o osobowej grupy  kasieńka3  1
 Podział 38 osobowej klasy na 2 grupy  Krys  4
 Kombinatoryka, wektor charakterystyczny i zliczanie funkcji  wrozansk  0
 rozmiar grupy multiplikatywnej, rząd podgrupy generowanej  Dec  0
 Zliczanie rozmieszczenia kul w komórkach  szymod  6
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl