Zapoznaj się z przedstawioną poniżej prezentacją multimedialną. Przeanalizuj zaprezentowane w niej rozwiązanie zadania dotyczącego rozmieszczeń liczb ze zbioru , w dwóch rzędach po cztery liczby. Pokazane jest w niej w jaki sposób można obliczyć, ile wśród tych rozmieszczeń jest takich, w których żadne dwie liczby parzyste nie sąsiadują ze sobą.
Rczlcm8NCvS5w
Prezentacja. Liczby z ośmioelementowego zbioru rozmieszczamy w dwóch rzędach po cztery liczby. Obliczymy w ilu spośród tych rozmieszczeń żadne dwie liczby parzyste nie sąsiadują ze sobą. Rozwiązanie. Załóżmy, że ciąg jest permutacją zbioru A. Jeżeli rozdzielimy tę permutacje na dwie permutacje czteroelementowe oraz to w ten sposób otrzymamy opisane rozmieszczenie wszystkich elementów zbioru math>A=1,2,3,4,5,6,7,9 w dwóch rzędach po cztery liczby. W ten sposób dowolnemu rozmieszczeniu elementów zbioru A przypisujemy wzajemnie jednoznacznie rozmieszczenie tych elementów z podziałem na dwa rzędy po cztery liczby, np. permutacji . Odpowiada podział. . . A podziałowi . . Odpowiada permutacja . Zauważmy, że w zbiorze A znajdują się trzy liczby parzyste 2,4 i sześć. Zatem rozmieszczenie spełnia warunki zadania w jednym z dwóch rozłącznych przypadków. Jeżeli w permutacji żadne dwie spośród tych trzech liczb nie sąsiadują ze sobą. Jeżeli w permutacji dwie spośród liczb parzystych znajdują się na miejscach a indeks dolny 4 koniec indeksu oraz a indeks dolny pięć koniec indeksu, a trzecia jest na miejscu, które nie sąsiaduje z żadnym z tych dwóch. Przykładem permutacji, która spełnia warunki zadania w przypadku 1 jest permutacja . Przykładem permutacji, która spełnia warunki zadania w przypadku 2 jest permutacja . Rozpatrujemy przypadek pierwszy. Pokażemy, że permutacji w której żadne dwie spośród liczb 2,4 oraz sześć nie sąsiadują ze sobą, można przyporządkować dokładnie jedną permutację jedenastoelementową utworzoną ze wszystkich elementów zbioru A oraz z trzech dopisanych do niej elementów równych zero, w której to permutacji żadne dwa elementy nieparzyste nie są zapisane obok siebie. W tym celu wystarczy postępować według poniższych reguł. Krok pierwszy. Najpierw do permutacji wstawiamy po jednym zerze między każde dwie sąsiednie elementy nieparzyste. Jeżeli w ten sposób wstawiliśmy trzy zera, to procedurę uzupełniania kończymy. Zauważmy, że w pierwszym kroku procedury wstawimy 3 zera wtedy i tylko wtedy, gdy w permutacji oba elementy skrajne, a1 oraz a8, są liczbami parzystymi. Popatrzmy dla przykładu na permutację . Uzupełniamy ją trzema zerami w następujący sposób: . Krok drugi. Jeżeli permutacja nie została uzupełniona trzema zerami, to sprawdzamy czy pierwszym elementem permutacji otrzymanej po wykonaniu pierwszego kroku jest liczba nieparzysta. Jeśli tak to wstawiamy przed nim element zero i gdy po wykonaniu tego kroku permutacja liczy jedenaście elementów to procedurę uzupełniania kończymy. Zauważmy, że w dwóch krokach procedury wstawimy trzy zera wtedy i tylko wtedy, gdy w permutacji pierwszy element jest liczbą nieparzystą, a ostatni liczbą parzystą. Przykładem takiej permutacji jest . Uzupełniamy ją trzema zerami w następujący sposób: . . Krok trzeci. Jeżeli permutacja nie została jeszcze uzupełniona trzema zerami, to do wstawienia pozostało zero jako ostatni jedenasty element permutacji. Zauważmy, że ostatnie zero wstawimy w jednym z dwóch możliwych przypadków gdy w permutacji pierwszy element jest liczbą parzystą, a ostatni liczbą nieparzystą. Dla ilustracji tego przypadku rozpatrzmy permutację . Uzupełniamy ją trzema zerami w następujący sposób: . . . gdy w permutacji pierwszy i ostatni element są liczbami nieparzystymi. Dla ilustracji tego przypadku rozpatrzmy permutację . Uzupełniamy ją trzema zerami w następujący sposób: . . . Każda z otrzymanych permutacji jedenastoelementowych ma następujące własności. Na pięciu miejscach o numerach parzystych rozmieszczone są w niej liczby ze zbioru. . Rozmieszczamy 5 elementów nieparzystych na przypisanych im miejscach co można zrobić na sposobów. Na wybranych trzech spośród sześciu miejsc o numerach nieparzystych rozmieszczone są elementy ze zbioru . Na każdym spośród pozostałych trzech miejsc wstawione jest zero. Wybieramy 3 miejsca z 6 dostępnych dla niezerowych liczb parzystych, a następnie rozmieszczamy je na wybranych miejscach można to zrobić na sposobów. Korzystając z reguły mnożenia stwierdzamy, że wszystkich takich permutacji jest . Pokazaliśmy w ten sposób, że każdej permutacji ośmioelementowej spełniającej warunki zadania odpowiada dokładnie jedna permutacja jedenastoelementowa w której na miejscach o numerach parzystych rozmieszczone są elementy ze zbioru a na pozostałych miejscach rozmieszczone są 2,4 i 6 oraz trzy zera. Wynika stąd, ze w pierwszym przypadku jest 14400 rozmieszczeń, które spełniają warunki zadania. Zauważmy, że jeżeli usuniemy wszystkie zera z permutacji 11-elementowej, w której na miejscach parzystych rozmieszczone są elementy ze zbioru , na miejscach nieparzystych rozmieszczone są liczby 2, 4, 6, oraz trzy zera, to dostaniemy ośmioelementową permutację, która spełnia warunki zadania. Rozpatrujemy przypadek drugi. Obliczamy, ile jest permutacji Zbioru A, w których dwie spośród liczb parzystych znajdują się na miejscach a indeks dolny 4 koniec indeksu oraz a indeks dolny 5 koniec indeksu, a trzecia jest na miejscu które nie sąsiaduje z żadnym z tych dwóch. Zauważmy, że ponieważ z żadnym spośród miejsc a indeks dolny 4 koniec indeksu oraz a indeks dolny 5 koniec indeksu nie sąsiaduje każde z czterech miejsc a indeks dolny 1 koniec indeksu, a indeks dolny 2 koniec indeksu, a indeks dolny 7 koniec indeksu, a indeks dolny 8 koniec indeksu, więc są 4 możliwości przydzielenia trzech miejsc w permutacji dla liczb ze zbioru . W tym przypadku warunki zadania spełniają permutacje, w których elementy parzyste zapisane są na miejscach: . Wobec tego po wyborze tych miejsc wystarczy rozmieścić liczby parzyste na przydzielonych im miejscach, a następnie rozmieścić 5 liczb nieparzystych na pozostałych 5 miejscach. Oznacza to, że w drugim przypadki liczba możliwych rozmieszczeń, które spełniają warunki zadania jest równa. . Za każdym razem 3 elementy parzyste rozmieścimy na trzech przydzielonych im miejscach na sposobów, 5 elementów nieparzystych rozmieścimy na 5 przydzielonych im miejscach na sposobów. Ostatecznie stwierdzamy, że jest 17280 wszystkich rozmieszczeń, które spełniają warunki zadania. Pokazaliśmy, że warunki zadania spełnione są jedynie w dwóch rozłącznych przypadkach. Obliczyliśmy liczby możliwych rozmieszczeń w każdym z nich: w przypadku 1 jest ich 14400, w przypadku 2 jest ich 2880. Stąd na podstawie reguły dodawania otrzymujemy, że wszystkich szukanych rozmieszczeń jest 17280.
Prezentacja. Liczby z ośmioelementowego zbioru rozmieszczamy w dwóch rzędach po cztery liczby. Obliczymy w ilu spośród tych rozmieszczeń żadne dwie liczby parzyste nie sąsiadują ze sobą. Rozwiązanie. Załóżmy, że ciąg jest permutacją zbioru A. Jeżeli rozdzielimy tę permutacje na dwie permutacje czteroelementowe oraz to w ten sposób otrzymamy opisane rozmieszczenie wszystkich elementów zbioru math>A=1,2,3,4,5,6,7,9 w dwóch rzędach po cztery liczby. W ten sposób dowolnemu rozmieszczeniu elementów zbioru A przypisujemy wzajemnie jednoznacznie rozmieszczenie tych elementów z podziałem na dwa rzędy po cztery liczby, np. permutacji . Odpowiada podział. . . A podziałowi . . Odpowiada permutacja . Zauważmy, że w zbiorze A znajdują się trzy liczby parzyste 2,4 i sześć. Zatem rozmieszczenie spełnia warunki zadania w jednym z dwóch rozłącznych przypadków. Jeżeli w permutacji żadne dwie spośród tych trzech liczb nie sąsiadują ze sobą. Jeżeli w permutacji dwie spośród liczb parzystych znajdują się na miejscach a indeks dolny 4 koniec indeksu oraz a indeks dolny pięć koniec indeksu, a trzecia jest na miejscu, które nie sąsiaduje z żadnym z tych dwóch. Przykładem permutacji, która spełnia warunki zadania w przypadku 1 jest permutacja . Przykładem permutacji, która spełnia warunki zadania w przypadku 2 jest permutacja . Rozpatrujemy przypadek pierwszy. Pokażemy, że permutacji w której żadne dwie spośród liczb 2,4 oraz sześć nie sąsiadują ze sobą, można przyporządkować dokładnie jedną permutację jedenastoelementową utworzoną ze wszystkich elementów zbioru A oraz z trzech dopisanych do niej elementów równych zero, w której to permutacji żadne dwa elementy nieparzyste nie są zapisane obok siebie. W tym celu wystarczy postępować według poniższych reguł. Krok pierwszy. Najpierw do permutacji wstawiamy po jednym zerze między każde dwie sąsiednie elementy nieparzyste. Jeżeli w ten sposób wstawiliśmy trzy zera, to procedurę uzupełniania kończymy. Zauważmy, że w pierwszym kroku procedury wstawimy 3 zera wtedy i tylko wtedy, gdy w permutacji oba elementy skrajne, a1 oraz a8, są liczbami parzystymi. Popatrzmy dla przykładu na permutację . Uzupełniamy ją trzema zerami w następujący sposób: . Krok drugi. Jeżeli permutacja nie została uzupełniona trzema zerami, to sprawdzamy czy pierwszym elementem permutacji otrzymanej po wykonaniu pierwszego kroku jest liczba nieparzysta. Jeśli tak to wstawiamy przed nim element zero i gdy po wykonaniu tego kroku permutacja liczy jedenaście elementów to procedurę uzupełniania kończymy. Zauważmy, że w dwóch krokach procedury wstawimy trzy zera wtedy i tylko wtedy, gdy w permutacji pierwszy element jest liczbą nieparzystą, a ostatni liczbą parzystą. Przykładem takiej permutacji jest . Uzupełniamy ją trzema zerami w następujący sposób: . . Krok trzeci. Jeżeli permutacja nie została jeszcze uzupełniona trzema zerami, to do wstawienia pozostało zero jako ostatni jedenasty element permutacji. Zauważmy, że ostatnie zero wstawimy w jednym z dwóch możliwych przypadków gdy w permutacji pierwszy element jest liczbą parzystą, a ostatni liczbą nieparzystą. Dla ilustracji tego przypadku rozpatrzmy permutację . Uzupełniamy ją trzema zerami w następujący sposób: . . . gdy w permutacji pierwszy i ostatni element są liczbami nieparzystymi. Dla ilustracji tego przypadku rozpatrzmy permutację . Uzupełniamy ją trzema zerami w następujący sposób: . . . Każda z otrzymanych permutacji jedenastoelementowych ma następujące własności. Na pięciu miejscach o numerach parzystych rozmieszczone są w niej liczby ze zbioru. . Rozmieszczamy 5 elementów nieparzystych na przypisanych im miejscach co można zrobić na sposobów. Na wybranych trzech spośród sześciu miejsc o numerach nieparzystych rozmieszczone są elementy ze zbioru . Na każdym spośród pozostałych trzech miejsc wstawione jest zero. Wybieramy 3 miejsca z 6 dostępnych dla niezerowych liczb parzystych, a następnie rozmieszczamy je na wybranych miejscach można to zrobić na sposobów. Korzystając z reguły mnożenia stwierdzamy, że wszystkich takich permutacji jest . Pokazaliśmy w ten sposób, że każdej permutacji ośmioelementowej spełniającej warunki zadania odpowiada dokładnie jedna permutacja jedenastoelementowa w której na miejscach o numerach parzystych rozmieszczone są elementy ze zbioru a na pozostałych miejscach rozmieszczone są 2,4 i 6 oraz trzy zera. Wynika stąd, ze w pierwszym przypadku jest 14400 rozmieszczeń, które spełniają warunki zadania. Zauważmy, że jeżeli usuniemy wszystkie zera z permutacji 11-elementowej, w której na miejscach parzystych rozmieszczone są elementy ze zbioru , na miejscach nieparzystych rozmieszczone są liczby 2, 4, 6, oraz trzy zera, to dostaniemy ośmioelementową permutację, która spełnia warunki zadania. Rozpatrujemy przypadek drugi. Obliczamy, ile jest permutacji Zbioru A, w których dwie spośród liczb parzystych znajdują się na miejscach a indeks dolny 4 koniec indeksu oraz a indeks dolny 5 koniec indeksu, a trzecia jest na miejscu które nie sąsiaduje z żadnym z tych dwóch. Zauważmy, że ponieważ z żadnym spośród miejsc a indeks dolny 4 koniec indeksu oraz a indeks dolny 5 koniec indeksu nie sąsiaduje każde z czterech miejsc a indeks dolny 1 koniec indeksu, a indeks dolny 2 koniec indeksu, a indeks dolny 7 koniec indeksu, a indeks dolny 8 koniec indeksu, więc są 4 możliwości przydzielenia trzech miejsc w permutacji dla liczb ze zbioru . W tym przypadku warunki zadania spełniają permutacje, w których elementy parzyste zapisane są na miejscach: . Wobec tego po wyborze tych miejsc wystarczy rozmieścić liczby parzyste na przydzielonych im miejscach, a następnie rozmieścić 5 liczb nieparzystych na pozostałych 5 miejscach. Oznacza to, że w drugim przypadki liczba możliwych rozmieszczeń, które spełniają warunki zadania jest równa. . Za każdym razem 3 elementy parzyste rozmieścimy na trzech przydzielonych im miejscach na sposobów, 5 elementów nieparzystych rozmieścimy na 5 przydzielonych im miejscach na sposobów. Ostatecznie stwierdzamy, że jest 17280 wszystkich rozmieszczeń, które spełniają warunki zadania. Pokazaliśmy, że warunki zadania spełnione są jedynie w dwóch rozłącznych przypadkach. Obliczyliśmy liczby możliwych rozmieszczeń w każdym z nich: w przypadku 1 jest ich 14400, w przypadku 2 jest ich 2880. Stąd na podstawie reguły dodawania otrzymujemy, że wszystkich szukanych rozmieszczeń jest 17280.
W grupie osób jest dorosłych oraz dwoje dzieci: Jaś i Małgosia. Całą tę -osobową grupę ustawiamy na trzy różne sposoby: (1) w dwóch szeregach po osób, (2) w trzech szeregach po osoby, (3) w czterech szeregach po osoby. Ile jest w każdym z tych trzech przypadków wszystkich możliwych ustawień takich, że Jaś i Małgosia nie stoją obok siebie?
Załóżmy, że ciąg opisuje rozmieszczenie wszystkich osób podanej grupy -osobowej w jednym szeregu, w których Jaś i Małgosia nie stoją obok siebie. Obliczymy, w ilu spośród tych rozmieszczeń Jaś i Małgosia nie sąsiadują ze sobą. Korzystamy z pomysłu omówionego w grafice. Aby rozdzielić Jasia i Małgosię rozpatrujemy -elementową permutację, w której:
na miejscach o numerach parzystych rozmieszczamy osób dorosłych (można to zrobić na sposobów),
na dwóch miejscach wybranych spośród miejsc o numerach nieparzystych rozmieszczamy Jasia oraz Małgosię (można to zrobić na sposobów),
pozostałe miejsc uzupełniamy zerami (można je też pozostawić puste).
Obliczamy, że wszystkich takich permutacji jest .
Następnie zauważamy, że każdej takiej permutacji -elementowej wzajemnie jednoznacznie odpowiada rozmieszczenie rozpatrywanej grupy osób, w którym Jaś i Małgosia nie sąsiadują ze sobą. Oznacza to, że wszystkich ciągów opisujących rozmieszczenie wszystkich osób podanej grupy -osobowej w jednym szeregu, w których Jaś i Małgosia nie stoją obok siebie jest .
Zauważmy ostatecznie, że:
w przypadku (1), kiedy ustawiamy daną grupę w dwóch szeregach po osób, rozbijamy permutację na dwie: oraz . Wtedy, oprócz rozpatrzonych powyżej przypadków ustawień, w których Jaś i Małgosia nie sąsiadują ze sobą, mamy jeszcze jeden przypadek spełniający warunki zadania. To przypadek, w którym Jaś i Małgosia zajmą miejsca oraz . Ponieważ Jasia i Małgosię na tych dwóch miejscach można rozmieścić na sposoby, a dorosłych na pozostałych miejscach - na sposobów, więc w przypadku (1) liczba wszystkich szukanych rozmieszczeń jest równa .
w przypadku (2), kiedy ustawiamy daną grupę w trzech szeregach po osoby, rozbijamy permutację na trzy: , oraz . Wtedy, oprócz rozpatrzonych na wstępie przypadków ustawień, w których Jaś i Małgosia nie sąsiadują ze sobą, mamy jeszcze dwa przypadki spełniające warunki zadania. To przypadki, kiedy Jaś i Małgosia zajmą sąsiednie miejsca: oraz , a także oraz . Ponieważ w każdym z tych dwóch przypadków Jasia i Małgosię na ustalonych dwóch miejscach można rozmieścić na sposoby, a dorosłych na pozostałych miejscach - na sposobów, więc w przypadku (2) liczba wszystkich szukanych rozmieszczeń jest równa .
w przypadku (3), kiedy ustawiamy daną grupę w czterech szeregach po osoby, rozbijamy permutację na cztery: , , oraz . Wtedy, oprócz rozpatrzonych na wstępie przypadków ustawień, w których Jaś i Małgosia nie sąsiadują ze sobą, mamy jeszcze trzy przypadki spełniające warunki zadania. To przypadki, kiedy Jaś i Małgosia zajmą sąsiednie miejsca: oraz , oraz , a także oraz . Ponieważ w każdym z tych trzech przypadków Jasia i Małgosię na ustalonych dwóch miejscach można rozmieścić na sposoby, a dorosłych na pozostałych miejscach - na sposobów, więc w przypadku (3) liczba wszystkich szukanych rozmieszczeń jest równa .
