3 zadania z zagadnienia kombinatoryki i zliczania

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
MMRTMX
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 13 sty 2021, o 13:32
Płeć: Mężczyzna
wiek: 21
Podziękował: 3 razy

3 zadania z zagadnienia kombinatoryki i zliczania

Post autor: MMRTMX » 13 sty 2021, o 14:06

Cześć, rozwiązuję zadania z kombinatoryki i zliczania przed kolokwium, do tych nie posiadam odpowiedzi, byłbym bardzo wdzięczny gdyby ktoś mógł rzucić okiem na moje rozwiązania i ewentualnie przedstawić poprawne jeśli ja coś przekręcę.
Zadanie 1: Ile jest różnych uporządkowanych czwórek \(\displaystyle{ (a, b, c, d)}\) liczb naturalnych
a. dodatnich,
b. z których dokładnie jedna jest równa 0,
takich, że \(\displaystyle{ a+b+c+d = 12}\)
Uważam, że do zrobienia zadania potrzebny będzie wzór na n wyrazową wariację z powtórzeniami.
Odp. a) \(\displaystyle{ (\frac{n}{2})^{4} }\), ponieważ liczb naturalnych jest \(\displaystyle{ n}\), liczb dodatnich będzie \(\displaystyle{ \frac{n}{2} }\), a że losujemy 4 liczby(myślę, że liczby mogą się powtarzać) robimy \(\displaystyle{ \frac{n}{2} \cdot \frac{n}{2} \cdot \frac{n}{2} \cdot \frac{n}{2} = (\frac{n}{2})^{4}}\)
b) tego nie wiem, bo opcji jest bardzo dużo i nie mam pomysłu jak to policzyć

Zadanie 2: Ile jest różnych 10-elementowych ciągów
a. o wyrazach tworzących zbiór 3-elementowy
b. ternarnych, w których występuje: 5 liter a, 3 litery b i 2 litery c.

a) Korzystając ze wzoru na wariację z powtórzeniami zliczam ile będzie zbiorów spełniających warunek, będzie ich \(\displaystyle{ n ^{3} }\), jeśli każdy z elementów tego 10 elementowego ciągu ma \(\displaystyle{ n ^{3} }\) możliwości, to będzie \(\displaystyle{ (n ^{3}) ^{10} }\).
b) Nie jestem pewien tego podpunktu, ale wydaje mi się, że możliwości ułożenia liter a, b, c będzie \(\displaystyle{ 10!}\)(mam też wątpliwość, czy nie powinienem tego podnieść do dziesiątej potęgi)

Zadanie 3: W każdą kratkę szachownicy 3x3 wpisano jedną z liczb: \(\displaystyle{ -1, 0, 1}\), a następnie zsumowano liczby
w każdym wierszu, w każdej kolumnie i na każdej z dwóch przekątnych.
Wykaż, że wśród tych wszystkich sum pewne 2 są równe.

To zadanie wydaje mi się najprostrze, będzie tu trzeba wykorzystać zasadę szufladkową Dirichleta. Mamy szachownicę 3x3, czyli pól do zapełnienia liczbami będzie 9, każde z 9 pól ma 3 możliwe wartości\(\displaystyle{ (-1,0,1)}\), więc możliwości zapełnienia szachownicy jest \(\displaystyle{ 3 ^{9} }\). Teraz należy policzyć ile będzie różnych sum zgodnych z zadaniem. Najmniejszą sumą będzie \(\displaystyle{ -3}\)(ponieważ: \(\displaystyle{ -1+(-1)+(-1)=-3}\)), a największą \(\displaystyle{ 3}\)(ponieważ: \(\displaystyle{ 1+1+1 = 3}\)). Różnych sum jest \(\displaystyle{ 3-(-3)=6}\), z góry widać, że \(\displaystyle{ \frac{3 ^{9}}{6} > 1}\), oznacza to, że na pewno w przynajmniej jednej 'przegródce' znajdzie się więcej niż jeden element, co oznacza, że założenie zadania jest prawdziwe.

Dobrze to rozumiem? Będę bardzo wdzięczny za wszelkie wskazówki.

Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 7854
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 243 razy
Pomógł: 3086 razy

Re: 3 zadania z zagadnienia kombinatoryki i zliczania

Post autor: kerajs » 13 sty 2021, o 15:47

1)
a) \(\displaystyle{ {12-1 \choose 4-1} }\)
b) \(\displaystyle{ 4{12-1 \choose 4-1} }\)

2)
a) \(\displaystyle{ 3^{10}-{3 \choose 2} 2^{10}+{3 \choose 1} 1^{10}}\)
b) \(\displaystyle{ \frac{10!}{5!2!3!} }\)

3) Różnych sum jest 7, a w szachownicy występuje 8 sum.

MMRTMX
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 13 sty 2021, o 13:32
Płeć: Mężczyzna
wiek: 21
Podziękował: 3 razy

Re: 3 zadania z zagadnienia kombinatoryki i zliczania

Post autor: MMRTMX » 13 sty 2021, o 16:08

kerajs pisze:
13 sty 2021, o 15:47
...
Czyli muszę wrócić porządnie do nauki, jakaś podpowiedź kiedy użyć jakiej metody?

Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 7854
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 243 razy
Pomógł: 3086 razy

Re: 3 zadania z zagadnienia kombinatoryki i zliczania

Post autor: kerajs » 15 sty 2021, o 08:10

MMRTMX pisze:
13 sty 2021, o 16:08
jakaś podpowiedź kiedy użyć jakiej metody?
Obawiam się, że tu nie ma schematów. Czytaj uważnie treść zadań aby być pewnym o co nas pytają, i zastanów się co, z poznanych metod, można zastosować . Wraz z praktyką przyjdzie i rutyna, i automatyzm, i pewność odpowiedzi.

Awatar użytkownika
pesel
Użytkownik
Użytkownik
Posty: 1621
Rejestracja: 8 cze 2010, o 13:09
Płeć: Mężczyzna
Podziękował: 1 raz
Pomógł: 393 razy

Re: 3 zadania z zagadnienia kombinatoryki i zliczania

Post autor: pesel » 15 sty 2021, o 09:29

MMRTMX pisze:
13 sty 2021, o 14:06
Zadanie 3: W każdą kratkę szachownicy 3x3 wpisano jedną z liczb: −1,0,1, a następnie zsumowano liczby
w każdym wierszu, w każdej kolumnie i na każdej z dwóch przekątnych.
Wykaż, że wśród tych wszystkich sum pewne 2 są równe.
Tutaj chyba ciekawszy byłoby przypadek, w którym nie uwzględnia się sumowań po jednej, albo obu przekątnych.

MMRTMX
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 13 sty 2021, o 13:32
Płeć: Mężczyzna
wiek: 21
Podziękował: 3 razy

Re: 3 zadania z zagadnienia kombinatoryki i zliczania

Post autor: MMRTMX » 15 sty 2021, o 15:21

kerajs pisze:
15 sty 2021, o 08:10
MMRTMX pisze:
13 sty 2021, o 16:08
jakaś podpowiedź kiedy użyć jakiej metody?
Obawiam się, że tu nie ma schematów. Czytaj uważnie treść zadań aby być pewnym o co nas pytają, i zastanów się co, z poznanych metod, można zastosować . Wraz z praktyką przyjdzie i rutyna, i automatyzm, i pewność odpowiedzi.
A mógłbyś powiedzieć jak doszedłeś do rozwiązania zadania 1szego i 2 podpunkt a? Drugie już podpunkt b oraz zadanie 3 już rozpracowałem, a na te dwa nie ma pomysłu

Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 7854
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 243 razy
Pomógł: 3086 razy

Re: 3 zadania z zagadnienia kombinatoryki i zliczania

Post autor: kerajs » 15 sty 2021, o 19:08

Co do zadania pierwszego to wyjaśnienie znajdziesz tu :
KLIK:    
(przekopiowałem to z kombinatoryka pytanie ).

Wynik 2a to zastosowanie zasady włączeń i wyłączeń.
Od wszystkich 10 wyrazowych ciągów w których mogą występować pewne trzy elementy odejmuję 10 wyrazowe ciągi w których mogą występować dwa z tych trzech elementów, i dodaję nadmiarowo odjęte ciągi 10 wyrazowe ciągi w których występuje jeden element.


pesel pisze:
15 sty 2021, o 09:29
Tutaj chyba ciekawszy byłoby przypadek, w którym nie uwzględnia się sumowań po jednej, albo obu przekątnych.
Tezę łatwo wykazać przez brak kontrprzykładu.
1) Zakładam że istnieje układ 7 różnych sum (od -3 do 3), w tym jedna na przekątnej.
Niewątpliwie suma 3 ( 1,1,1) nie może się przecinać z sumą -3 (-1,-1,-1) , więc układy te { ( 1,1,1) i (-1,-1,-1) } muszą być równoległe. Trzecim równoległym musi być suma 0 z elementami (-1,0,1) , lecz wtedy prostopadłe do nich sumy to -1 , 0 oraz 1 co daje powtarzającą się sumę 0 . Teza jest prawdziwa bo układ 7 różnych sum (od -3 do 3), w tym jednej na przekątnej nie istnieje.
2) Zakładam że istnieje układ 6 różnych sum na wierszach i kolumnach szachownicy. Z 1) wynika, że taki układ nie może jednocześnie zawierać sumy 3 ( 1,1,1) i sumy -3 (-1,-1,-1). Zawiera więc sześć sum :
a) -3,-2,-1,0,1,2
b) -2,-1,0,1,2,3
jednak żadna suma z tych sum nie jest podzielna przez 2 , co sprawia że taki układ nie istnieje.

a4karo
Użytkownik
Użytkownik
Posty: 19033
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 6 razy
Pomógł: 3219 razy

Re: 3 zadania z zagadnienia kombinatoryki i zliczania

Post autor: a4karo » 15 sty 2021, o 20:36

kerajs pisze:
15 sty 2021, o 19:08

2) Zakładam że istnieje układ 6 różnych sum na wierszach i kolumnach szachownicy. Z 1) wynika, że taki układ nie może jednocześnie zawierać sumy 3 ( 1,1,1) i sumy -3 (-1,-1,-1). Zawiera więc sześć sum :
a) -3,-2,-1,0,1,2
b) -2,-1,0,1,2,3
jednak żadna suma z tych sum nie jest podzielna przez 2 , co sprawia że taki układ nie istnieje.
???

Awatar użytkownika
pesel
Użytkownik
Użytkownik
Posty: 1621
Rejestracja: 8 cze 2010, o 13:09
Płeć: Mężczyzna
Podziękował: 1 raz
Pomógł: 393 razy

Re: 3 zadania z zagadnienia kombinatoryki i zliczania

Post autor: pesel » 15 sty 2021, o 21:56

Kerajsowi chodzi zapewne o to, że każda liczba jest liczona dwukrotnie (raz jako element kolumny, a drugi raz jako element wiersza), dlatego też suma sum wszystkich wierszy i kolumn będzie parzysta. Jednak zarówno suma liczb w podpunkcie a) oraz b) (czyli suma sum) parzysta nie jest.

ODPOWIEDZ