Matematyka dyskretna, zadanie nr 4443

Autor	Zadanie / Rozwiązanie
brightnesss postów: 113	2016-04-10 22:26:03 Zad1 Ile jest ciągów binarnych dlugości n, w ktorych wystepuje dokladnie k jedynek takich, że żadne dwie jedynki nie stoją obok siebie? Zad2 Mamy k róznych kart pocztowych. Chcemy je wysłac do n przyjaciól. Na ile sposobow mozemy to zrobic przy zalozeniu ze kazda osoba moze otrzymac dowolna ilosc kart? Jaka bedzie odpowiedz jesli zalozymy dodatkowo, ze kazdy przyjaciel ma otrzymac kartke? Bardzo prosze o wytlumaczenie tych zadan.

tumor postów: 8070	2016-04-11 07:33:03 1. Podejdź do zadania łącząc jedynki z zerami, bo wiemy, że po każdej jedynce (być może z wyjątkiem ostatniej) występuje zero. a) Po ostatniej jedynce też występuje zero Wówczas mamy k par (10) oraz n-2k zer, przed którymi nie ma jedynek. Ile jest sposobów ułożenia k par (traktujemy parę jak pojedynczy element) i n-2k zer? b) Po ostatniej jedynce nic już nie ma. Wówczas mamy ustalony ostatni element, k-1 par (10) oraz n-2(k-1)-1 zer. Ustalamy kolejność zer i par (10), a na końcu, na jeden możliwy sposób, wstawiamy jedynkę.

tumor postów: 8070	2016-04-11 08:07:26 2. Wyobraź sobie, że przyjaciele to numerki 1,2,...,n Masz karty rozłożone kolejno na stole. Na każdej z k kart piszesz dowolny numer przyjaciela, bo numery mogą się powtarzać albo wcale nie wystąpić. Dostaniesz zatem k-elementowy ciąg wyrazów pochodzących ze zbioru 1,2,...,n. Wariacje z powtórzeniami. Jeśli kart jest co najmniej tyle ilu przyjaciół, to możemy rozpatrywać tylko te opcje, w których każdy przyjaciel coś dostanie. Zatem od wyniku poprzedniego, który obejmuje wszystkie wariacje (takie, w których użyto wszystkich n numerów przyjaciół, ale i takie, gdzie użyto n-1 numerów albo n-5 numerów) odejmij wszelkie możliwe wariacje używające maksymalnie n-1 numerów. Zostaną tylko te, które używają dokładnie n numerów (być może z powtórzeniami). Przy tym rachunki w tym podpunkcie będą bardziej złożone, bo musisz się zastanowić, jak odjąć wszystkie wariacje nie spełniające naszych założeń, ale jednocześnie każdą odjąć raz, a nie więcej razy. ;) Możesz użyć od razu wzoru na liczbę podziałów zbioru (rozbić zbioru). Wszak zbiór kart rozbijasz na n niepustych podzbiorów. No i rozwiązałem to zadanie z założeniem, że każda karta będzie wysłana. Można się zastanowić, co się stanie, jeśli wcale tak nie będzie. Wówczas proponuję rozważać KOSZ NA ŚMIECI jako n+1 przyjaciela i zastosować techniki te co wcześniej (z wyjątkiem wymogu, by w drugim podpunkcie KOSZ dostał co najmniej jedną kartkę).

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj