3 zadania z zagadnienia kombinatoryki i zliczania

[MMRTMX]

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.

[kerajs]

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]

...

Czyli muszę wrócić porządnie do nauki, jakaś podpowiedź kiedy użyć jakiej metody?

[kerajs]

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.

[pesel]

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]

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

[kerajs]

Co do zadania pierwszego to wyjaśnienie znajdziesz tu :

KLIK:    

Załóżmy, że mam znaleźć liczbę rozwiązań równania: \(\displaystyle{ x_1+x_2+x_3=6}\) w liczbach naturalnych dodatnich (np: podzielić 6 cukierków między trójkę dzieci tak, aby każde dostało przynajmniej jednego cukierka, albo rozdzielić 6 zadań między trzech studentów tak, aby każdy dostał przynajmniej jedno zadanie).
Mogę wypisać rozwiązania podając trójki \(\displaystyle{ x_1,x_2,x_3}\):
\(\displaystyle{ 4,1,1\\
3,2,1\\
3,1,2\\
2,3,1\\
2,2,2\\
2,1,3\\
1,4,1\\
1,3,2\\
1,2,3\\
1,1,4}\)
i je zliczyć (jest ich 10)
Inne podejście to liczbę \(\displaystyle{ 6}\) przedstawić jako sumę jedynek \(\displaystyle{ 1+1+1+1+1+1}\). Aby dostać dowolne rozwiązanie wystarczy dwa plusy zamienić na przecinki (np: \(\displaystyle{ 1,1+1,1+1+1}\) albo \(\displaystyle{ 1+1+1+1,1,1}\))
Czyli ilość rozwiązań to ilość wyborów dwóch plusów (o jeden mniej niż niewiadomych) z pięciu (o jeden mniej niż znana suma). \(\displaystyle{ {5 \choose 2}=10}\) albo \(\displaystyle{ {6-1 \choose 3-1}={5 \choose 2}=10}\)
Ogólnie:
Liczba rozwiązań równania: \(\displaystyle{ x_1+x_2+...+x_n=S \ \ \wedge S \ge n}\) w liczbach naturalnych dodatnich to: \(\displaystyle{ {S-1 \choose n-1}}\)

A co jeśli mam znaleźć liczbę rozwiązań równania: \(\displaystyle{ x_1+x_2+x_3=6}\) w liczbach naturalnych (zero uznaję za naturalne) ?
Wtedy robiąc podstawienie:
\(\displaystyle{ t_1=x_1+1\\
t_2=x_2+1\\
t_3=x_3+1}\)
mam znaleźć liczbę rozwiązań równania: \(\displaystyle{ t_1-1+t_2-1+t_3-1=6}\) w liczbach naturalnych dodatnich. To jest już proste i z tekstu powyżej wiem że ilość ta to: \(\displaystyle{ {6+3-1 \choose 3-1}=28}\).

(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.

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]

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.

???

[pesel]

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.