Kombinatoryka, zadanie nr 4299

Autor	Zadanie / Rozwiązanie
swist10 postów: 2	2014-05-03 19:14:59 Mamy 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 19876=3024 kiedy tylko 4 198710=5040 tylko3 1981010=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 109874 (4 rózne i 4 żeby powtorzyc jedna z poprzednich 4), czy 101098*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{987}{123}$ - 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{89}{21}$ 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}28=451016=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 $109874$ 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. $109874=633210=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: $109873$ sposoby, czyli $632410=15120$ Dodajmy wyniki, w których jako ostatnia losowana jest trzecia cyfra, a może być identyczna z pierwszą lub drugą: $109872=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). $10987*1=5040$. Po dodaniu dostajemy 50400. Teraz się zgadza.

strony: 1

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