Matematyka dyskretna, zadanie nr 4443
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
brightnesss post贸w: 113 |  2016-04-10 22:26:03Zad1 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