1. Na każdym z pól szachownicy o wymiarach n × n położono lub nie jedno ziarenko. Jaka jest minimalna łączna liczba kolumn, wierszy i przekątnych na których znajduje się po tyle samo ziarenek?
2. Na ile różnych sposobów można spośród 20 rycerzy wybrać 13 i obsadzić nimi dokładnie 3 z 4 baszt zamku (nazwanych wg stron świata).
3. Ile jest różnych permutacji ciągó 1,2,...,n w których każda liczba i znajduje się na miejscu i lub sąsiednim z i (dla i = 1,2,...,n)? Znajdź zależność rekurencyjną.
4. Ile jest roznych wynikow meczow hokejowych w ktorych strzelono 13 bramek jesli wynik meczu podaje sie wraz z wynikami trzech tercji?
5. Ile jest ciągów binarnych o długości n, w których jest dokładnie k par 01?
Pomógłby ktoś z rozwiązaniami takich zadań?
1. Wydaje mi się, że zasady szufladkowej dirichleta, tylko nie wiem czy jeśli chodzi o przekątne to tylko te 2 o n miejscach czy wszystkie?
2/3. Z liczb Stirlinga, ale nie wiem jak zacząć.
4/5. W ogóle teog nie widzę.
Z góry dziękuje za pomoc. To nie tak, że oczekuję odrazu rozwiązań, tylko zbliża się kolokwium i chciałbym to zrozumieć.
Zadania kombinatoryczne
-
Everard
- Użytkownik
- Posty: 166
- Rejestracja: 11 lip 2007, o 22:59
- Płeć: Mężczyzna
- Lokalizacja: Bytom
- Pomógł: 49 razy
Zadania kombinatoryczne
1. Rozwiązanie szłoby mniej więcej tak samo niezależnie od tego, czy bierzesz jedynie te dwie przekątne czy wszystkie "przesunięte" \(\displaystyle{ 2n}\) (przesunięte w sensie że przechodzisz przez ścianę i kontynuujesz dopóki każda przekątna ma \(\displaystyle{ n}\) pól). Zrobiłoby się trudniej gdybyś musiał rozważać te przekątne jako "obcięte" (czyli niektóre miałyby mniej pól), ale nie wydaje mi się żeby to zadanie miało być aż tak skomplikowane.
W każdym razie masz \(\displaystyle{ n}\) kolumn, wierszy i \(\displaystyle{ 2n}\) przekątnych, natomiast ziarenek w każdym zbiorze jest od \(\displaystyle{ 0}\) do \(\displaystyle{ n}\). Mamy więc \(\displaystyle{ 4n}\) obiektów w \(\displaystyle{ n+1}\) szufladkach, więc z zasady szufladkowej musi istnieć szufladka z \(\displaystyle{ \ceil{\frac{4n}{n+1}}=3}\) (lub \(\displaystyle{ 2}\) dla \(\displaystyle{ n=1}\)) obiektami, zatem Twoja minimalna liczba to \(\displaystyle{ 2}\) lub \(\displaystyle{ 3}\) zależnie od \(\displaystyle{ n}\).
2. Liczbami Stirlinga? A czemu nie:
- wybieramy \(\displaystyle{ 13}\) spośród \(\displaystyle{ 20}\);
- wybieramy \(\displaystyle{ 3}\) spośród \(\displaystyle{ 4}\) wież;
- liczymy na ile sposobów możemy rozmieścić w tych trzech, odejmując sposoby które obsadzają mniej niż trzy wieże.
Finalnie:
\(\displaystyle{ {20 \choose 13}{4 \choose 3}(3^{13}-{3\choose 2}2^{13}-3).}\)
3. Oczywiście \(\displaystyle{ I_1=1, I_2=2}\). Dla \(\displaystyle{ n\ge 3}\) (zakładam że traktujemy \(\displaystyle{ 1}\) i \(\displaystyle{ n}\) jako nie sąsiadujące ze sobą) albo \(\displaystyle{ n}\) zostaje na swoim miejscu i resztę permutujemy zgodnie z warunkami zadania na \(\displaystyle{ I_{n-1}}\) sposobów, albo zamieniamy miejscami \(\displaystyle{ n}\) i \(\displaystyle{ n-1}\), resztę permutując na \(\displaystyle{ I_{n-2}}\) sposobów. Zatem
\(\displaystyle{ I_n=I_{n-1}+I_{n-2}.}\)
W każdym razie masz \(\displaystyle{ n}\) kolumn, wierszy i \(\displaystyle{ 2n}\) przekątnych, natomiast ziarenek w każdym zbiorze jest od \(\displaystyle{ 0}\) do \(\displaystyle{ n}\). Mamy więc \(\displaystyle{ 4n}\) obiektów w \(\displaystyle{ n+1}\) szufladkach, więc z zasady szufladkowej musi istnieć szufladka z \(\displaystyle{ \ceil{\frac{4n}{n+1}}=3}\) (lub \(\displaystyle{ 2}\) dla \(\displaystyle{ n=1}\)) obiektami, zatem Twoja minimalna liczba to \(\displaystyle{ 2}\) lub \(\displaystyle{ 3}\) zależnie od \(\displaystyle{ n}\).
2. Liczbami Stirlinga? A czemu nie:
- wybieramy \(\displaystyle{ 13}\) spośród \(\displaystyle{ 20}\);
- wybieramy \(\displaystyle{ 3}\) spośród \(\displaystyle{ 4}\) wież;
- liczymy na ile sposobów możemy rozmieścić w tych trzech, odejmując sposoby które obsadzają mniej niż trzy wieże.
Finalnie:
\(\displaystyle{ {20 \choose 13}{4 \choose 3}(3^{13}-{3\choose 2}2^{13}-3).}\)
3. Oczywiście \(\displaystyle{ I_1=1, I_2=2}\). Dla \(\displaystyle{ n\ge 3}\) (zakładam że traktujemy \(\displaystyle{ 1}\) i \(\displaystyle{ n}\) jako nie sąsiadujące ze sobą) albo \(\displaystyle{ n}\) zostaje na swoim miejscu i resztę permutujemy zgodnie z warunkami zadania na \(\displaystyle{ I_{n-1}}\) sposobów, albo zamieniamy miejscami \(\displaystyle{ n}\) i \(\displaystyle{ n-1}\), resztę permutując na \(\displaystyle{ I_{n-2}}\) sposobów. Zatem
\(\displaystyle{ I_n=I_{n-1}+I_{n-2}.}\)
-
Sarken
- Użytkownik
- Posty: 25
- Rejestracja: 19 wrz 2012, o 18:25
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 1 raz
Zadania kombinatoryczne
3. Chodziło mi, że pierwszą część zadania chyba z liczb Sterlinga.
1. Czemu n+1 szufladek?
1. Czemu n+1 szufladek?
-
arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Zadania kombinatoryczne
zad 4.
Nie znam się na hokeju ale z tego co pisze w zadaniu wyobrażam to sobie tak:
I tura: \(\displaystyle{ a:b}\)
II tura: \(\displaystyle{ c:d}\)
III tura: \(\displaystyle{ e:f}\)
Z warunków zadania:
\(\displaystyle{ a+b+c+d+e+f=13,0 \le a,b,c,d,e,f \le 13}\)
co daje:
\(\displaystyle{ {6+13-1 \choose 13} ={18 \choose 13}}\)
A pytanie powinno raczej brzmieć:
Ile jest możliwych wyników meczu hokejowego w którym strzelono - \(\displaystyle{ 13}\) bramek
...............................................................................................................
Co do 5 tego zadania pojęciem kluczowym są serie w ciągach zer i jedynek.
Może napiszę kilka przykładów:
\(\displaystyle{ I}\) . Np takie ciągi zaczynające i kończące się zerami:
\(\displaystyle{ 0001......0111000}\)
Zauważmy że w tego typu ciągach występuje:
\(\displaystyle{ k}\) - serii jedynek
\(\displaystyle{ k+1}\) - serii zer
\(\displaystyle{ k}\) - par \(\displaystyle{ 01}\)
\(\displaystyle{ R=k+k+1=2k+1}\) - wszystkich serii
\(\displaystyle{ II}\). Ciągi zaczynające się jedynkami i kończące się zerami:
\(\displaystyle{ 111 0001......0111000}\)
Zauważmy że w tego typu ciągach występuje:
\(\displaystyle{ k+1}\) - serii jedynek
\(\displaystyle{ k+1}\) - serii zer
\(\displaystyle{ k}\) - par \(\displaystyle{ 01}\)
\(\displaystyle{ R=k+1+k+1=2k+2}\) - wszystkich serii
\(\displaystyle{ III}\). Ciągi zaczynające się zerami i kończące się jedynkami:
\(\displaystyle{ 0001......0111000111}\)
Zauważmy że w tego typu ciągach występuje:
\(\displaystyle{ k}\) - serii jedynek
\(\displaystyle{ k}\) - serii zer
\(\displaystyle{ k}\) - par \(\displaystyle{ 01}\)
\(\displaystyle{ R=k+k=2k}\) - wszystkich serii
\(\displaystyle{ IV}\). Ciągi zaczynające się jedynkami i kończące się jedynkami:
\(\displaystyle{ 1110001......0111000111}\)
Zauważmy że w tego typu ciągach występuje:
\(\displaystyle{ k+1}\) - serii jedynek
\(\displaystyle{ k}\) - serii zer
\(\displaystyle{ k}\) - par \(\displaystyle{ 01}\)
\(\displaystyle{ R=k+1+k=2k+1}\) - wszystkich serii
Innych możliwości już niema.
Niech teraz:
\(\displaystyle{ n}\) - długość ciągu
\(\displaystyle{ x}\) - ilość występujących jedynek
\(\displaystyle{ y}\) - ilość występujących zer
\(\displaystyle{ n=x+y}\)
Teraz stosuję wzór do ilości serii \(\displaystyle{ R}\)
bo zauważmy tyle będzie par \(\displaystyle{ 01}\) - ile będzie wynosiło \(\displaystyle{ k}\)
w każdym z tych przypadków.
I teraz wracając do przypadków i korzystając ze wzoru na serie mamy:
ad. (I) - \(\displaystyle{ R=2k+1,}\)
\(\displaystyle{ a(n,k)= {x-1 \choose k} {y-1 \choose k-1}+ {x-1 \choose k-1} {y-1 \choose k}}\)
ad. (II) - \(\displaystyle{ R=2k+2,}\)
\(\displaystyle{ a(n,k)= {x-1 \choose k} {y-1 \choose k}}\)
ad. (III) - \(\displaystyle{ R=2k,}\)
\(\displaystyle{ a(n,k)= {x-1 \choose k-1} {y-1 \choose k-1}}\)
ad. (IV) - \(\displaystyle{ R=2k+1,}\)
\(\displaystyle{ a(n,k)= {x-1 \choose k} {y-1 \choose k-1}+ {x-1 \choose k-1} {y-1 \choose k}}\)
gdzie: \(\displaystyle{ a(n,k)}\) - to ilość ciągów w których występuje \(\displaystyle{ k}\) - par \(\displaystyle{ 01}\)
Wyszedłem tu z obserwacji, że ilość serii i ilość par \(\displaystyle{ 01}\) - jest związana ze sobą.
Potem zastosowałem wzór na ilość serii w ciągu zerojedynkowym!
Nie znam się na hokeju ale z tego co pisze w zadaniu wyobrażam to sobie tak:
I tura: \(\displaystyle{ a:b}\)
II tura: \(\displaystyle{ c:d}\)
III tura: \(\displaystyle{ e:f}\)
Z warunków zadania:
\(\displaystyle{ a+b+c+d+e+f=13,0 \le a,b,c,d,e,f \le 13}\)
co daje:
\(\displaystyle{ {6+13-1 \choose 13} ={18 \choose 13}}\)
A pytanie powinno raczej brzmieć:
Ile jest możliwych wyników meczu hokejowego w którym strzelono - \(\displaystyle{ 13}\) bramek
...............................................................................................................
Co do 5 tego zadania pojęciem kluczowym są serie w ciągach zer i jedynek.
Może napiszę kilka przykładów:
\(\displaystyle{ I}\) . Np takie ciągi zaczynające i kończące się zerami:
\(\displaystyle{ 0001......0111000}\)
Zauważmy że w tego typu ciągach występuje:
\(\displaystyle{ k}\) - serii jedynek
\(\displaystyle{ k+1}\) - serii zer
\(\displaystyle{ k}\) - par \(\displaystyle{ 01}\)
\(\displaystyle{ R=k+k+1=2k+1}\) - wszystkich serii
\(\displaystyle{ II}\). Ciągi zaczynające się jedynkami i kończące się zerami:
\(\displaystyle{ 111 0001......0111000}\)
Zauważmy że w tego typu ciągach występuje:
\(\displaystyle{ k+1}\) - serii jedynek
\(\displaystyle{ k+1}\) - serii zer
\(\displaystyle{ k}\) - par \(\displaystyle{ 01}\)
\(\displaystyle{ R=k+1+k+1=2k+2}\) - wszystkich serii
\(\displaystyle{ III}\). Ciągi zaczynające się zerami i kończące się jedynkami:
\(\displaystyle{ 0001......0111000111}\)
Zauważmy że w tego typu ciągach występuje:
\(\displaystyle{ k}\) - serii jedynek
\(\displaystyle{ k}\) - serii zer
\(\displaystyle{ k}\) - par \(\displaystyle{ 01}\)
\(\displaystyle{ R=k+k=2k}\) - wszystkich serii
\(\displaystyle{ IV}\). Ciągi zaczynające się jedynkami i kończące się jedynkami:
\(\displaystyle{ 1110001......0111000111}\)
Zauważmy że w tego typu ciągach występuje:
\(\displaystyle{ k+1}\) - serii jedynek
\(\displaystyle{ k}\) - serii zer
\(\displaystyle{ k}\) - par \(\displaystyle{ 01}\)
\(\displaystyle{ R=k+1+k=2k+1}\) - wszystkich serii
Innych możliwości już niema.
Niech teraz:
\(\displaystyle{ n}\) - długość ciągu
\(\displaystyle{ x}\) - ilość występujących jedynek
\(\displaystyle{ y}\) - ilość występujących zer
\(\displaystyle{ n=x+y}\)
Teraz stosuję wzór do ilości serii \(\displaystyle{ R}\)
bo zauważmy tyle będzie par \(\displaystyle{ 01}\) - ile będzie wynosiło \(\displaystyle{ k}\)
w każdym z tych przypadków.
I teraz wracając do przypadków i korzystając ze wzoru na serie mamy:
ad. (I) - \(\displaystyle{ R=2k+1,}\)
\(\displaystyle{ a(n,k)= {x-1 \choose k} {y-1 \choose k-1}+ {x-1 \choose k-1} {y-1 \choose k}}\)
ad. (II) - \(\displaystyle{ R=2k+2,}\)
\(\displaystyle{ a(n,k)= {x-1 \choose k} {y-1 \choose k}}\)
ad. (III) - \(\displaystyle{ R=2k,}\)
\(\displaystyle{ a(n,k)= {x-1 \choose k-1} {y-1 \choose k-1}}\)
ad. (IV) - \(\displaystyle{ R=2k+1,}\)
\(\displaystyle{ a(n,k)= {x-1 \choose k} {y-1 \choose k-1}+ {x-1 \choose k-1} {y-1 \choose k}}\)
gdzie: \(\displaystyle{ a(n,k)}\) - to ilość ciągów w których występuje \(\displaystyle{ k}\) - par \(\displaystyle{ 01}\)
Wyszedłem tu z obserwacji, że ilość serii i ilość par \(\displaystyle{ 01}\) - jest związana ze sobą.
Potem zastosowałem wzór na ilość serii w ciągu zerojedynkowym!
-
Everard
- Użytkownik
- Posty: 166
- Rejestracja: 11 lip 2007, o 22:59
- Płeć: Mężczyzna
- Lokalizacja: Bytom
- Pomógł: 49 razy
Zadania kombinatoryczne
Szufladki są ponumerowane od \(\displaystyle{ 0}\) do \(\displaystyle{ n}\), więc jest ich \(\displaystyle{ n+1}\).