Polacy, Niemcy i Rosjanie [kombinatoryka]
-
- Użytkownik
- Posty: 9
- Rejestracja: 9 paź 2013, o 19:44
- Płeć: Mężczyzna
- Lokalizacja: Lublin
- Podziękował: 1 raz
Polacy, Niemcy i Rosjanie [kombinatoryka]
Witajcie! Zadanie brzmi:
W poczekalni siedzi 3 Polaków, 3 Niemców oraz 3 Rosjan. Na ile sposobów można ich posadzić na 9 krzesłach tak, żeby żadne dwie pary jednej narodowości nie siedziały obok siebie?
Uznałem, że wszystkich możliwych kombinacji usadzeń jest:
\(\displaystyle{ \frac{9!}{3!3!3!}}\)
Natomiast sytuacji, których musimy odrzucić, jest:
\(\displaystyle{ {3 \choose 2} \cdot {9 \choose 4} \cdot \frac{5!}{3!}}\)
Ponieważ z trzech nacji wybieramy dwie, z których bierzemy pary siedzące obok siebie, wybieramy im 4 z 9 miejsc, a resztę ustawiamy na 5! sposobów, co dzielimy przez 3! ponieważ nie odróżniamy członków jednej, pozostałej w pełni nacji.
Wynik ostateczny jest różnicą przytoczonych powyżej wyrażeń.
Czy ktoś mógłby sprawdzić poprawność rozwiązania?
W poczekalni siedzi 3 Polaków, 3 Niemców oraz 3 Rosjan. Na ile sposobów można ich posadzić na 9 krzesłach tak, żeby żadne dwie pary jednej narodowości nie siedziały obok siebie?
Uznałem, że wszystkich możliwych kombinacji usadzeń jest:
\(\displaystyle{ \frac{9!}{3!3!3!}}\)
Natomiast sytuacji, których musimy odrzucić, jest:
\(\displaystyle{ {3 \choose 2} \cdot {9 \choose 4} \cdot \frac{5!}{3!}}\)
Ponieważ z trzech nacji wybieramy dwie, z których bierzemy pary siedzące obok siebie, wybieramy im 4 z 9 miejsc, a resztę ustawiamy na 5! sposobów, co dzielimy przez 3! ponieważ nie odróżniamy członków jednej, pozostałej w pełni nacji.
Wynik ostateczny jest różnicą przytoczonych powyżej wyrażeń.
Czy ktoś mógłby sprawdzić poprawność rozwiązania?
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Polacy, Niemcy i Rosjanie [kombinatoryka]
A te krzesła jak są ustawione. W jednym rządku czy w trzech rządkach po trzy krzesła, czy w kółeczku, czy po prostu trzeba uwzględnić wszystkie sposoby?Robert2k9 pisze: W poczekalni siedzi 3 Polaków, 3 Niemców oraz 3 Rosjan. Na ile sposobów można ich posadzić na 9 krzesłach tak, żeby żadne dwie pary jednej narodowości nie siedziały obok siebie?
-
- Użytkownik
- Posty: 9
- Rejestracja: 9 paź 2013, o 19:44
- Płeć: Mężczyzna
- Lokalizacja: Lublin
- Podziękował: 1 raz
Polacy, Niemcy i Rosjanie [kombinatoryka]
Mamy jeden rządek krzeseł żadnych kółek, dwurzędów ani innych komplikacji.
- Mathix
- Użytkownik
- Posty: 357
- Rejestracja: 18 mar 2012, o 13:00
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 9 razy
- Pomógł: 73 razy
Polacy, Niemcy i Rosjanie [kombinatoryka]
Jak wybierasz 4 spośród 9 miejsc to te miejsca nie muszą być koniecznie obok siebie, mogą to być na przykład miejsca pierwsze, trzecie, szóste i ósme.
-
- Użytkownik
- Posty: 9
- Rejestracja: 9 paź 2013, o 19:44
- Płeć: Mężczyzna
- Lokalizacja: Lublin
- Podziękował: 1 raz
Polacy, Niemcy i Rosjanie [kombinatoryka]
A czy ktoś może zasugerować poprawne rozwiązanie tego zadania?
- Mathix
- Użytkownik
- Posty: 357
- Rejestracja: 18 mar 2012, o 13:00
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 9 razy
- Pomógł: 73 razy
Polacy, Niemcy i Rosjanie [kombinatoryka]
Nie jestem pewien czy to jest dobrze:
Związujemy ze sobą czterech ludzi. Mamy ciąg postaci \(\displaystyle{ (aabb)acbc}\). Litery to narodowości, to jest ciąg przykładowy. Dla ciągu \(\displaystyle{ (aabb)}\) możemy wybrać \(\displaystyle{ 6}\) miejsc, natomiast \(\displaystyle{ bb}\) i \(\displaystyle{ aa}\) można wybrać spośród \(\displaystyle{ bbb}\) i \(\displaystyle{ aaa}\) i mogą się oni zamieniać miejscami, \(\displaystyle{ a}\) z \(\displaystyle{ a}\) oraz \(\displaystyle{ b}\) z \(\displaystyle{ b}\).
Dodatkowo mamy trzy narodowości. Zatem od wszystkich możliwych ustawień, jest ich \(\displaystyle{ 9!}\) (przecież nawet ludzie tej samej narodowości są inni) należy odjąć:
\(\displaystyle{ 6\cdot(2!)^{2}\cdot{3\choose2}^{3}\cdot4!}\)
Byłbym wdzięczny jakby ktoś skomentował to rozwiązanie.
Związujemy ze sobą czterech ludzi. Mamy ciąg postaci \(\displaystyle{ (aabb)acbc}\). Litery to narodowości, to jest ciąg przykładowy. Dla ciągu \(\displaystyle{ (aabb)}\) możemy wybrać \(\displaystyle{ 6}\) miejsc, natomiast \(\displaystyle{ bb}\) i \(\displaystyle{ aa}\) można wybrać spośród \(\displaystyle{ bbb}\) i \(\displaystyle{ aaa}\) i mogą się oni zamieniać miejscami, \(\displaystyle{ a}\) z \(\displaystyle{ a}\) oraz \(\displaystyle{ b}\) z \(\displaystyle{ b}\).
Dodatkowo mamy trzy narodowości. Zatem od wszystkich możliwych ustawień, jest ich \(\displaystyle{ 9!}\) (przecież nawet ludzie tej samej narodowości są inni) należy odjąć:
\(\displaystyle{ 6\cdot(2!)^{2}\cdot{3\choose2}^{3}\cdot4!}\)
Byłbym wdzięczny jakby ktoś skomentował to rozwiązanie.
Ostatnio zmieniony 24 kwie 2014, o 22:11 przez Mathix, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Polacy, Niemcy i Rosjanie [kombinatoryka]
Chciałeś chyba napisać \(\displaystyle{ {3\choose2}^{2}}\) zamiast \(\displaystyle{ {3\choose2}^{3}}\).
Nie widzę, gdzie literom przyporządkowujesz narodowości. Można to zrobić na \(\displaystyle{ 3!}\) sposobów.
Wyniki \(\displaystyle{ (aabb)ccabc}\) oraz \(\displaystyle{ cc(aabb)cab}\) są takie same, a liczysz je jako różne.
Nie widzę, gdzie literom przyporządkowujesz narodowości. Można to zrobić na \(\displaystyle{ 3!}\) sposobów.
Wyniki \(\displaystyle{ (aabb)ccabc}\) oraz \(\displaystyle{ cc(aabb)cab}\) są takie same, a liczysz je jako różne.
- Mathix
- Użytkownik
- Posty: 357
- Rejestracja: 18 mar 2012, o 13:00
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 9 razy
- Pomógł: 73 razy
Polacy, Niemcy i Rosjanie [kombinatoryka]
a - RosjanieWyniki (aabb)ccabc oraz cc(aabb)cab są takie same, a liczysz je jako różne.
b - Polacy
c - Niemcy
Czemu takie same? Przecież jak posadzimy na ostatnim krzesełku Niemca to nie to samo jak posadzimy Polaka.
A z tym:
się zgadzam dopiero teraz zauważyłem. Czyli wg ciebie w moim wyniku trzeba zmienić tylko \(\displaystyle{ {3\choose2}}\) na \(\displaystyle{ 3!}\)?Chciałeś chyba napisać \(\displaystyle{ {3\choose2}^{2}}\) zamiast \(\displaystyle{ {3\choose2}^{3}}\).
Nie widzę, gdzie literom przyporządkowujesz narodowości. Można to zrobić na 3! sposobów.
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Polacy, Niemcy i Rosjanie [kombinatoryka]
Czyli jeśli dobrze rozumiem, to rozwiązanie wygląda teraz następująco: litery są na stałe przyporządkowane poszczególnym narodowościom, na \(\displaystyle{ 3}\) sposoby wybieramy narodowość pierwszej pary (na przykład \(\displaystyle{ a}\)), na \(\displaystyle{ 2}\) sposoby wybieramy narodowość drugiej pary (na przykład \(\displaystyle{ b}\)), wybieramy osoby do pierwszej i drugiej pary na \(\displaystyle{ \binom32^2}\) sposobów, ustalamy kolejność osób w parach na \(\displaystyle{ (2!)^2}\) sposobów, ustalamy miejsce dla wybranych par na \(\displaystyle{ 6}\) sposobów, ustawiamy osoby spoza par na \(\displaystyle{ 5!}\) sposobów (bo jest ich \(\displaystyle{ 5}\), a nie \(\displaystyle{ 4}\)). Razem \(\displaystyle{ 3\cdot2\cdot\binom32^2\cdot(2!)^2\cdot6\cdot5!=(3!)^3\cdot6!}\).
Ale problemem jest to, że wyniki \(\displaystyle{ (aabb)ccabc}\) i \(\displaystyle{ aa(bbcc)abc}\) są takie same, a tym sposobem liczymy je jako różne.
Ale problemem jest to, że wyniki \(\displaystyle{ (aabb)ccabc}\) i \(\displaystyle{ aa(bbcc)abc}\) są takie same, a tym sposobem liczymy je jako różne.
- Mathix
- Użytkownik
- Posty: 357
- Rejestracja: 18 mar 2012, o 13:00
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 9 razy
- Pomógł: 73 razy
Polacy, Niemcy i Rosjanie [kombinatoryka]
O to mi chodziło . W taki razie podwójnie będziemy liczyć ciągi, w których występują trzy pary po kolei ludzi tych samych narodowości. Więc od tego co policzyliśmy trzeba odjąć ciągi typu \(\displaystyle{ (aabbcc)abc}\), będzie ich:
\(\displaystyle{ {3\choose2}^{3}\cdot(2!)^{3}\cdot(3!)^{2}}\)
Bo do ciągu \(\displaystyle{ (aabbcc)}\) wybieramy trzy razy po dwie liczby z trzech, możemy je zamienić miejscami, narodowości możemy zmieniać miejscami i te liczby co są poza ciągiem trzeba spermutować.
Teraz będzie w porządku
\(\displaystyle{ {3\choose2}^{3}\cdot(2!)^{3}\cdot(3!)^{2}}\)
Bo do ciągu \(\displaystyle{ (aabbcc)}\) wybieramy trzy razy po dwie liczby z trzech, możemy je zamienić miejscami, narodowości możemy zmieniać miejscami i te liczby co są poza ciągiem trzeba spermutować.
Teraz będzie w porządku
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Polacy, Niemcy i Rosjanie [kombinatoryka]
Jeszcze trzeba pomnożyć przez \(\displaystyle{ 4}\), bo grupa trzech par nie musi być na początku.
Ale to jeszcze nie koniec. Również dwukrotnie zostały policzone ustawienia typu \(\displaystyle{ (aabb)bccac=aab(bbcc)ac}\).
Ale to jeszcze nie koniec. Również dwukrotnie zostały policzone ustawienia typu \(\displaystyle{ (aabb)bccac=aab(bbcc)ac}\).
- Mathix
- Użytkownik
- Posty: 357
- Rejestracja: 18 mar 2012, o 13:00
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 9 razy
- Pomógł: 73 razy
Polacy, Niemcy i Rosjanie [kombinatoryka]
Nie da się tego zadania rozwiązać bardziej trywialnie? Czy trzeba robić wszystko tak jak tu wyżej pisaliśmy? Może ma ktoś pomysł na jakieś prostsze rozwiązanie, bo ten sposób wymaga dużo liczenia i łatwo w nim o pomyłkę ze względu na dużą liczbę obliczeń, a także i błąd logiczny.