Matematyka dyskretna, zadanie nr 4444
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
brightnesss post贸w: 113 |  2016-04-11 13:26:42Zad1 Na p贸艂ce stoi 12 ksi膮偶ek. Na ile sposob贸w mo偶na wybra膰 spo艣r贸d nich 5 ksi膮zek, aby nie by艂o w艣r贸d nich 偶adnych dw贸ch stoj膮cych obok siebie? Zad2 Przy okr膮g艂ym stole zasiada 12 osob, Na ile sposob贸w mo偶na wybra膰 sposr贸d nich 5 os贸b tak, aby nie zosta艂a wybrana 偶adna para os贸b siedz膮cych obok siebie? Wiem, 偶e to s膮 zadania na kombinacj臋 z powt贸rzeniami. Jednak nie potrafie ich zrozumie膰. Szuka艂am na r贸偶nych forach rozwi膮za艅 i tam by艂a metoda np ustawienia w ci膮g binarny 100101, jednak nie rozumiem na czym ona polega i jak nam pomaga. Z g贸ry dzi臋kuj臋 za pomoc. |
tumor post贸w: 8070 | 2016-04-11 13:44:51 Mo偶e proponuj jakie艣 rozwi膮zania, jakie艣 idee? 1. Mo偶esz spojrze膰 rekurencyjnie. Zadanie ma rozwi膮zanie, gdy chcemy wybra膰 k ksi膮偶ek, a wszystkich ksi膮偶ek jest co najmniej 2k-1. Je艣li wszystkich jest wi臋cej, to mamy jeszcze wi臋cej rozwi膮za艅. Je艣li S(12,5) oznacza, 偶e z 12 wybieramy 5 ksi膮偶ek zgodnie z regu艂ami, to $S(12,5)=S(10,4)+S(9,4)+S(8,4)+S(7,4)$ Mamy tu cztery przypadki, je艣li wybieramy pierwsz膮 ksi膮偶k臋, to zostaje 10 z kt贸rych musimy wybra膰 4. Je艣li omijamy pierwsz膮 a wybieramy drug膮, to zostaje 9 z kt贸rych wybieramy 4 etc. Za ka偶dym razem $S(n,k)=S(n-2,k-1)+S(n-3,k-1)+...+S(2(k-1)-1,k-1)$ A oczywi艣cie je艣li mamy $S(n,1)=n$, o ile oczywi艣cie $n\ge 1$ --- Mo偶esz zauwa偶y膰, 偶e zadanie to jest bardzo podobne do niedawnego zadania z ci膮gami binarnymi, w kt贸rych nie ma dw贸ch jedynek obok siebie. Mamy ci膮g 12 znak贸w, w tym 5 jedynek, kt贸re nie s膮siaduj膮 ze sob膮. Ile takich ci膮g贸w umiemy stworzy膰? Ka偶dy taki ci膮g m贸wi nam o jakim艣 wyborze. Tzn je艣li np na trzecim miejscu ci膮gu znajduje si臋 1, to ksi膮偶k臋 trzeci膮 wybieramy, a je艣li na czwartym jest 0, to czwartej nie wybieramy. Ka偶d膮 sytuacj臋 wyboru/podzia艂u mo偶emy przedstawi膰 w postaci pewnego ci膮gu o odpowiednich elementach. A ci膮gi si臋 niekiedy zlicza bardziej intuicyjnie. 2. Zadanie z ci膮gami binarnymi b臋dzie trzeba zmodyfikowa膰 w ten spos贸b, 偶e je艣li pierwsza w ci膮gu jest 1, to nie mo偶e by膰 1 na ostatnim miejscu. I tyle. Wiadomo艣膰 by艂a modyfikowana 2016-04-11 15:25:37 przez tumor |
brightnesss post贸w: 113 | 2016-04-11 13:52:12 Co do pierwszego to my艣la艂am, 偶e skoro wybieramy 5 ksi膮偶ek, ale nie mog膮 sta膰 obok siebie to mo偶emy ustawi膰 taki ci膮g: o|o|o|o|o o-ksi膮zka |-miesce z ktorego nie mozemy wybra膰 Ksi膮偶ek mamy 5, a miejsc 4. Wiemy te偶 偶e wszystkich element贸w mamy 12, wi臋c zosta艂o mnam 3 ksi膮zki kt贸re mo偶emy wsadzi膰 gdziekolwiek pomi臋dzy wybranymi. Czyli na ${7 \choose 3}$. Jednak odpowied藕 jest niepoprawna i nie wiem gdzie jest b艂膮d. |
tumor post贸w: 8070 | 2016-04-11 14:10:06 Je艣li 9 ksi膮偶ek wygl膮da tak: wnwnwnwnw, gdzie w to wybrana, n niewybrana, to wstawienie kolejnej niewybranej ksi膮偶ki mi臋dzy dwie pierwsze da w efekcie wnnwnwnwnw natomiast wstawienie mi臋dzy drug膮 i trzeci膮 da wnnwnwnwnw Widzisz jak膮艣 r贸偶nic臋? Bo zliczasz oba warianty jakby si臋 r贸偶ni艂y, podczas gdy si臋 nie r贸偶ni膮. Prosz臋 o podliczenie ci膮g贸w z zerami i jedynkami tak jak w zadaniu: http://www.math.edu.pl/forum/temat,studia,4443,0 |
brightnesss post贸w: 113 | 2016-04-11 15:12:52 No tak, widze blad. Jednak nadal nie rozumiem tego wczesniejszego zadania z zerem i jedynkami. Ps mozna jakos poprawic ta moja metode? |
tumor post贸w: 8070 | 2016-04-11 15:30:07 Mo偶na. Masz sytuacj臋 _w_n_w_n_w_n_w_n_w_ gdzie w oznacza wybran膮, n niewybran膮, a _ to miejsce, gdzie jeszcze mo偶emy co艣 da膰. No i mamy rozdysponowa膰 jeszcze nnn gdzie艣 tam. Sytuacje upraszczamy do _w_nw_nw_nw_nw_ Poniewa偶 nie ma znaczenia, czy nowe n wstawimy po prawej czy po lewej od poprzednich n. Mamy zatem 6 miejsc, gdzie mo偶emy wstawi膰 nasze nnn. Poza tym nnn mo偶emy wstawi膰 a) razem wszystkie trzy: to si臋 da zrobi膰 na 6 sposob贸w b) w systemie 2+1, czyli w jedno wolne miejsce nn, a w inne tylko n, to si臋 da zrobi膰 na 6*5 sposob贸w c) jako 1+1+1, czyli wybieraj膮c ${6 \choose 3}=20$ sposob贸w w艂o偶enia pojedynczych n w trzy spo艣r贸d 6 miejsc. Razem 56. --- Jednak偶e opcja z ci膮giem zerojedynkowym i rozwi膮zaniem jak poprzednio jest nieco lepsza. Za艂贸偶my, 偶e ostatnia nie jest jedynka. Mamy zatem 5 par (10) oraz dwa dodatkowe 0, razem 7 element贸w, co rozpatrzone jako permutacje z powt贸rzeniami da $\frac{7!}{5!2!}=21$ uk艂ad贸w. Je艣li ostatnia jest jedynka, to mamy w艣r贸d 11 pozosta艂ych cyfr ci膮gu cztery pary (10) i trzy 0. To te偶 7 element贸w, ale teraz $\frac{7!}{4!3!}=35$ Razem 56 uk艂ad贸w. ---- Rozpatruj膮c rekurencyjnie $S(12,5)=S(10,4)+S(9,4)+S(8,4)+S(7,4)= S(8,3)+2*S(7,3)+3*S(6,3)+4*S(5,3)= S(6,2)+3*S(5,2)+6*S(4,2)+10*S(3,2)= S(4,1)+4*S(3,1)+10*S(2,1)+20*S(1,1)= 4+12+20+20=56$ |
brightnesss post贸w: 113 | 2016-04-11 22:35:32 Dzi臋kuj臋 bardzo. Jednak mam ostatnie dwa pytania. Dlaczego w tym b mamy 6*5? A drugie, czy moglabym prosic o wytlumaczenie tego sposobu: http://www.matematyka.pl/215455.htm |
tumor post贸w: 8070 | 2016-04-11 23:06:16 Je艣li masz 6 miejsc, w kt贸rych dajesz dwa elementy (raz element nn, a raz n), przy tym nie mo偶e by膰 tak, 偶e oba elementy trafi膮 w jedno miejsce, to jeden element (na przyk艂ad podw贸jny) trafia w dowolne z 6 miejsc, a drugi element (tu: pojedynczy) trafia w jedno z pozosta艂ych 5 miejsc. Inaczej patrz膮c: wybieramy na ${6 \choose 2}$ sposob贸w dwa miejsca do rozlokowania tych element贸w, no ale elementy s膮 odr贸偶nialne, czyli lokujemy je na 2! sposob贸w. ${6 \choose 2}*2!=5*6$ ----- Rozwi膮zanie z matematyka.pl jest tylko uog贸lnionym zapisem pierwszego rozwi膮zania z mojego poprzedniego postu. Wz贸r u偶yty to tzw kombinacje z powt贸rzeniami. Je艣li wybieramy kombinacj臋 (czyli podzbi贸r) jakiego艣 zbioru $\{1,2,3,...,s\}$ to oczywi艣cie ten podzbi贸r tylko na jeden spos贸b mo偶emy uporz膮dkowa膰 rosn膮co. Zatem tyle jest kombinacji t-elementowych ile t-elementowych ci膮g贸w rosn膮cych. Zatem ${s \choose t}$ mo偶na rozumie膰 jako ilo艣膰 t-elementowych ci膮g贸w rosn膮cych o elementach ze zbioru s-elementowego. Wyobra藕my sobie jednak, 偶e mamy elementy $a_1\le a_2 \le a_3 \le ... \le a_t$, czyli t-elementowy ci膮g NIEMALEJ膭CY o elementach ze zbioru s-elementowego. Zr贸bmy teraz taki manewr, dodajmy do pierwszego wyrazu 0, do nast臋pnego 1, do kolejnego 2 i tak dalej: $a_1<a_2+1<a_3+2<...<a_t+(t-1)$ Zatem ci膮g贸w niemalej膮cych t-elementowych ze zbioru s-elementowego jest dok艂adnie tyle, ile ci膮g贸w rosn膮cych t-elementowych ze zbioru (s+t-1)-elementowego, czyli ${s+t-1 \choose t}$. Zarazem jednak taki ci膮g niemalej膮cy mo偶na rozumie膰 jak kombinacj臋, w kt贸rej elementy mog膮 si臋 powtarza膰 (tak jak mog膮 by膰 r贸wne pewne wyrazy ci膮gu niemalej膮cego). Wr贸膰my do naszego zadania. Mamy _w_nw_nw_nw_nw_ czyli k+1 miejsc, w kt贸re mo偶emy wrzuci膰 elementy. Wybieramy zatem trzy z tych miejsc, ale Z POWT脫RZENIAMI, czyli u偶ywamy wzoru na kombinacje z powt贸rzeniami. W naszym przypadku mamy zbi贸r (k+1)-elementowy (wybieramy spo艣r贸d k+1 miejsc wstawiania zer), a podzbi贸r (n-2k+1)-elementowy (poniewa偶 od n element贸w odj臋li艣my k jedynek i k-1 zer i tyle nam zosta艂o zer do wstawiania). Je艣li podstawimy $t=n-2k+1$ $s=k+1$, dostaniemy ${s+t-1 \choose t}={n-k+1 \choose n-2k+1}$ Jeszcze raz, w skr贸cie: - kombinacja bez powt贸rze艅 odpowiada ci膮gowi rosn膮cemu (elementy si臋 nie powtarzaj膮). - je艣li rozwa偶ymy ci膮g niemalej膮cy (elementy mog膮 si臋 powtarza膰) to otrzymamy tzw. kombinacj臋 z powt贸rzeniami, ale ci膮g niemalej膮cy sprytnym dodawaniem zmieniamy na rosn膮cy, wobec tego wz贸r na kombinacje z powt贸rzeniami te偶 korzysta z symbolu Newtona - podstawiaj膮c dane z naszego zadania, gdzie mamy k+1 dziur do wype艂niania (n-2k+1) elementami (by膰 mo偶e wiele element贸w w jednej dziurze) dostajemy od razu to, co autor rozwi膮zania |
brightnesss post贸w: 113 | 2016-04-12 11:39:31 Bardzo dzi臋kuj臋, ju偶 zaczyna mi si臋 co艣 rozja艣nia膰. Zaciekawi艂 mnie jeszcze ten ci膮g niemalej膮cy. Bo jesli na przyklad chcemy znalezc ile jest liczb naturalnych, w ktorych cyfry wystepuja w porzadku niemalejacym, to mo偶emy to zapisa膰 jako r贸wnanie : X1+x2+x3+...+x9=n Gdzie xi i$\in${1,2,...,9} to ilosc cyfr \"i\" w naszej liczbie. Wiec nasz wz贸r to b臋dzie ${n+9-1 \choose 9}$? Dobrze to rozumiem? |
tumor post贸w: 8070 | 2016-04-12 11:51:54 ${9+n-1 \choose n} $ gdzie n jest d艂ugo艣ci膮 liczby, a pierwsza cyfra nie jest zerem (dlatego dla liczb jednocyfrowych dostaniemy wynik 9, a nie 10). Wybieramy bowiem n liczb z powt贸rzeniami ze zbioru 9-elementowego. |
| strony: 1 2 | |
Prawo do pisania przys艂uguje tylko zalogowanym u偶ytkownikom. Zaloguj si臋 lub zarejestruj