Kombinatoryka, zadanie nr 4299
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
swist10 post贸w: 2 |  2014-05-03 19:14:59Mamy kod 5 cyfrowy(0 mo偶e by膰 na 1-wszym miejscu) i ile jest takich liczb, 偶e kod zawiera co najmniej 3 rozne liczby? |
abcdefgh post贸w: 1255 | 2014-05-03 19:48:48 kiedy wszystkie s膮 r贸偶na czyli 1*9*8*7*6=3024 kiedy tylko 4 1*9*8*7*10=5040 tylko3 1*9*8*10*10=7200 $P(A)=15264$ |
tumor post贸w: 8070 | 2014-05-03 20:22:42 abcdefgh, nie masz jeszcze WYRZUT脫W SUMIENIA, 偶e odnosisz KORZY艢CI MAJ膭TKOWE wprowadzaj膮c ludzi W B艁膭D? 1) pierwszy b艂膮d polega na tym, 偶e wg polecenia 0 mo偶e by膰 na pierwszym miejscu, natomiast nie musi 2) drugi polega na tym, 偶e mamy jakie艣 P(A). Liter膮 P oznaczamy prawdopodobie艅stwo czyli miar臋 unormowan膮, kt贸ra NIE PRZYJMUJE warto艣ci wi臋kszych ni偶 1. ;) 3) trzeci b艂膮d jest najistotniejszy, bo polega na niedoliczeniu Dla pi臋ciu r贸偶nych cyfr wynik by艂 blisko, bo mia艂o by膰 $30240$ (w tym $3024$ kod贸w zaczynaj膮cych si臋 od zera). Dla czterech r贸偶nych cyfr mamy $10*{9 \choose 3}*\frac{5!}{2!}=50400$ Dla trzech r贸偶nych cyfr mamy dwie mo偶liwo艣ci. Mo偶e by膰 tak, 偶e jedna z cyfr powtarza si臋 trzykrotnie, tych mo偶liwo艣ci jest $10*{9 \choose 2}*\frac{5!}{3!}=7200$ ale mo偶e by膰 te偶 tak, 偶e dwie cydry maj膮 po dwa powt贸rzenia, takich przypadk贸w jest $10*{9 \choose 2}*\frac{5!}{2!2!}=10800$ -------------- absurdalno艣膰 wyniku abcdefgh rzuca si臋 w oczy, je艣li zauwa偶ymy, 偶e wszystkich kod贸w pi臋ciocyfrowych jest $10^5$, podczas gdy liczba kod贸w pi臋ciocyfrowych, w kt贸rych wyst臋puj膮 najwy偶ej dwie r贸偶ne cyfry, jest nie wi臋ksza ni偶 ${10 \choose 2}*2^5=1440$ Ze $100000$ kod贸w absdefgh gubi gdzie艣 w pr贸偶ni ponad $83000$, traktuj膮c je jak samorz膮dy pieni膮dze unijne. Fe. |
swist10 post贸w: 2 | 2014-05-03 22:14:55 Dzi臋ki tumor :), mam tylko 2 pytania. 1 wynika z mojej slabej pami臋ci i tego, 偶e kombinatoryke mia艂em dawno temu i nie pamietam kiedy stosowalo sie takie cos {5! \choose 2!} czy {5! \choose 2!2!}. I 2: dla np. czeterech r贸znych mamy 10*{9 \choose 3}*...., a nie 10*9*8*7*4 (4 r贸zne i *4 偶eby powtorzyc jedna z poprzednich 4), czy 10*10*9*8*7(tu akurat wynik wychodzi taki sam, ale w ten spsob tylko przy 4 roznych liczbach tak jest, w innych przypadkach zle) Wiadomo艣膰 by艂a modyfikowana 2014-05-03 22:16:20 przez swist10 |
tumor post贸w: 8070 | 2014-05-04 06:55:33 Dla 4 r贸偶nych mamy $10$ - na tyle sposob贸w wybieramy cyfr臋, kt贸ra si臋 powt贸rzy, ${9 \choose 3}=\frac{9!}{6!3!}=\frac{9*8*7}{1*2*3}$ - na tyle sposob贸w wybieramy pozosta艂e 3 cyfry (bez uwzgl臋dnienia ich kolejno艣ci). Jedna z cyfr jest powt贸rzona, dlatego jej wyb贸r traktujemy oddzielnie. Jest czym艣 innym wyb贸r np cyfry 7 by si臋 powt贸rzy艂a i 3,5,9 by wyst膮pi艂y raz, a wyb贸r 9 do powt贸rzenia i 3,5,7 by wyst膮pi艂y raz. To chyba jasne, 偶e maj膮c cyfry 3,5,7,7,9 nie u艂o偶ymy tych samych kod贸w co z cyfr 3,5,7,9,9. Natomiast te 3 cyfry niepowtarzaj膮ce si臋 s膮 r贸wnorz臋dne, st膮d ich wyb贸r za pomoc膮 kombinacji. Wz贸r $\frac{5!}{2!}$ jest na permutacje z powt贸rzeniami. Maj膮c do wyboru cyfry 7,7,3,5,9 mo偶na je u艂o偶y膰 w kod na $5!$ sposob贸w, ale zamiana identycznych cyfr 7 miejscami da ten sam kod. Czyli licz膮c 5! ka偶dy kod liczyli艣my 2-krotnie, st膮d dzielenie przez 2. Oznaczmy sobie chwilowo cyfry tak: $7_a,7_b,3,5,9$, czyli udawajmy, 偶e umiemy odr贸偶ni膰 dwie identyczne si贸demki. P贸ki odr贸偶niamy, kod $7_a7_b953$ jest inny ni偶 kod $7_b7_a953$. Natomiast gdy nie odr贸偶niamy, okazuje si臋, 偶e te kody s膮 identyczne. St膮d to dzielenie przez 2 (bo ka偶dy kod ma w艣r贸d liczonych takiego bli藕niaka). --- Dla trzech r贸偶nych cyfr mo偶emy mie膰 przypadek, gdy dwie s膮 pojedyncze, a jedna potr贸jna. Na $10$ sposob贸w wybieramy potr贸jn膮, na ${9 \choose 2}=\frac{9!}{7!2!}=\frac{8*9}{2*1}$ sposob贸w wybieramy te kt贸re b臋d膮 pojedyncze. Sposob贸w u艂o偶enia jest $5!$, ale ka偶de u艂o偶enie liczyli艣my $6$ razy (czyli $3!$), bowiem zamiana kolejno艣ci tych cyfr identycznych daje to samo u艂o偶enie, a nie inne. Inny przypadek dla trzech cyfr to wyb贸r jednej cyfry, kt贸ra si臋 nie powtarza (na $10$ sposob贸w) i dw贸ch cyfr, kt贸re si臋 powt贸rz膮 dwukrotnie (na ${9 \choose 2}$ sposob贸w). Nast臋pnie uk艂ada si臋 te cyfry na $5!$ sposob贸w, ale gdy zamienimy kolejno艣ci膮 te powt贸rzone cyfry (jedn膮 na $2!$ sposob贸w i drug膮 na $2!$ sposob贸w) to nic si臋 nie zmieni, dlatego dzielimy przez $2!2!$, bo jednego uk艂adu nie chcemy liczy膰 wielokrotnie. ----- Jest takie typowe zadanie, w kt贸rym pyta si臋, na ile sposob贸w mo偶na przemiesza膰 litery s艂owa MATEMATYKA. Jest to $\frac{10!}{3!2!2!}$, bo wszystkich liter jest 10, litera A powtarza si臋 3 razy, litera M dwa razy, litera T dwa razy. Wz贸r $\frac{n!}{a!b!c!...} $ (tzw permutacje z powt贸rzeniami) stosuje si臋 w艂a艣nie wtedy, gdy w sumie mieszamy $n$ element贸w, ale w艣r贸d nich wyst臋puj膮 powt贸rzone, jeden powt贸rzony $a$ razy, drugi powt贸rzony $b$ razy, trzeci powt贸rzony $c$ razy,... ------ Wz贸r ${n \choose k}=\frac{n!}{(n-k)!k!}$ to symbol Newtona, wz贸r na liczb臋 kombinacji k-elementowych (inaczej k-elementowych pozbior贸w) zbioru n-elementowego. Kombinacja nie uwzgl臋dnia kolejno艣ci. W moim mno偶eniu uwzgl臋dni艂em INN膭 ROL臉 cyfr, kt贸re si臋 powtarzaj膮 i tych, kt贸re si臋 nie powtarzaj膮, bo daje to inne kody. U偶y艂em jednak kombinacji, by stwierdzi膰 pocz膮tkowo na ile sposob贸w daje si臋 wybra膰 same cyfry, kt贸re stworz膮 kod. Nast臋pnie mno偶臋 przez ilo艣膰 permutacji z powt贸rzeniami, 偶eby opisa膰, na ile sposob贸w da si臋 te cyfry pouk艂ada膰. ---------------- Wszystkich uk艂ad贸w jest $10^5=100000$. Policzyli艣my ju偶 uk艂ady z co najmniej 3 r贸偶nymi cyframi. Mo偶emy policzy膰 pozosta艂e i sprawdzi膰, 偶e w sumie dostaniemy 100000. Mo偶emy liczy膰 tak: $ {10 \choose 2}*(2^5-2)+10$ gdzie na ${10 \choose 2}=45$ sposob贸w wybiera si臋 dwie cyfry kt贸re maj膮 tworzy膰 kod, a na $2^5$ sposob贸w uk艂ada si臋 z nich liczb臋. Ale w艣r贸d tych $2^5$ sposob贸w s膮 zawsze dwie liczby z jednej powt贸rzonej cyfry: Np je艣li otrzymamy cyfry 1 i 2, to mo偶emy z nich zrobi膰 dwie liczby z powt贸rzonych cyfr 11111 22222 oraz $2^5-2=30$ liczb w kt贸rych u偶ywa si臋 i 1 i 2, tzn: 11112 11121 ... 22212 22221 Licz臋 wi臋c ilo艣膰 uk艂ad贸w u艂o偶onych przy u偶yciu dw贸ch cyfr ${10 \choose 2}*(2^5-2)=1350$ a nast臋pnie dodaj臋 do tego 10 kod贸w u艂o偶onych ka偶dy z jednej powt贸rzonej cyfry 00000 11111 22222 ... 99999. Ostatecznie $50400+7200+10800+30240+1350+10=100000$ ------- Uwaga. Stara艂em si臋, 偶eby po wzorze by艂o wida膰, 偶e najpierw wybieram cyfry do mieszania, potem mieszam (st膮d zachowanie zapisu dla kombinacji i dla permutacji). Da艂o si臋 to zadanie przemy艣le膰 nieco inaczej. Mo偶na my艣le膰 na przyk艂ad tak: je艣li tworzymy kod z 3 cyfr, z kt贸rych jedna powtarza si臋 trzykrotnie, to najpierw wybieramy na ${10 \choose 2}$ sposob贸w dwie cyfry, kt贸re si臋 nie powt贸rz膮. Potem na ${5 \choose 2}$ wybieramy dla tych cyfr dwa miejsca (kod ma 5 znak贸w $xyzts$, wybieramy kt贸re zajmiemy tymi niepowtarzaj膮cymi cyframi), a poza tym mo偶emy te cyfry zamieni膰 miejscami na $2$ sposoby. Nast臋pnie pozosta艂e miejsca wolne w kodzie uzupe艂niamy jedn膮 z $8$ pozosta艂ych, nieu偶ytych jeszcze cyfr. Dostaniemy ${10 \choose 2}*{5 \choose 2}*2*8=45*10*16=7200$ Mimo innego przemy艣lenia do艣wiadczenia, wci膮偶 ten sam wynik. :) Da艂o si臋 tu my艣le膰 bardzo r贸偶nie i wynik by si臋 nie zmieni艂. ---- Mno偶enie $10*9*8*7*4$ jest zapisem wariacji. Wariacja uwzgl臋dnia kolejno艣膰. Ten zapis m贸wi: Pierwsz膮 cyfr臋 wybieramy dowolnie, drug膮 dowolnie (ale nie tak膮 jak pierwsza), trzeci膮 dowolnie (ale nie tak膮 jak poprzednie) i czwart膮 dowolnie (ale nie tak膮 jak poprzednie). W efekcie dostajemy R脫呕NE cyfry na miejscach 1-4. Nast臋pnie wybieramy pi膮t膮 cyfr臋 jako jedn膮 z wybranych poprzednio. W efekcie takiego wyboru pi膮ta cyfra jest identyczna z jedn膮 z poprzednich. Gdzie艣 si臋 jednak gubi膮 te wszystkie kody, gdy np druga cyfra jest identyczna z trzeci膮 albo pierwsza z czwart膮. To te偶 mo偶liwe, a wariacj膮 tego sposobu nie opisujesz. $10*9*8*7*4=63*32*10=20160$ Dodajmy do tego te偶 wyniki, w kt贸rych cyfry losujemy w innej kolejno艣ci (ostatnia cyfra czwarta), a identyczne s膮 cyfry czwarta z pierwsz膮 lub czwarta z drug膮 lub czwarta z trzeci膮. To: $10*9*8*7*3$ sposoby, czyli $63*24*10=15120$ Dodajmy wyniki, w kt贸rych jako ostatnia losowana jest trzecia cyfra, a mo偶e by膰 identyczna z pierwsz膮 lub drug膮: $10*9*8*7*2=10080$ Dodajmy wyniki, w kt贸rych jako ostatnia losowana jest druga cyfra, a mo偶e by膰 identyczna tylko z pierwsz膮 (czyli nawet musi by膰 z ni膮 identyczna). $10*9*8*7*1=5040$. Po dodaniu dostajemy 50400. Teraz si臋 zgadza. |
| strony: 1 | |
Prawo do pisania przys艂uguje tylko zalogowanym u偶ytkownikom. Zaloguj si臋 lub zarejestruj