szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 2 kwi 2018, o 11:20 
Użytkownik

Posty: 13
Lokalizacja: Warszawa
Prosiłbym o sprawdzenie mojego toku myślenia i ewentualne wskazówki. Zadanie brzmi następująco:

a) Na ile sposobów można rozmieścić 14 jednakowych przedmiotów w 3
pudełkach tak, aby w jednym z pudełek znalazło się co najmniej 8 przedmiotów?
b) Na ile sposobów można rozmieścić 14 jednakowych przedmiotów w 3 pudełkach tak, aby w każdym z pudełek nie znalazło się więcej niż 7 przedmiotów?

Rozw.
a) Otrzymany wynik na ćwiczeniach to 3 \cdot  {8 \choose 6}  = 84. Domyślam się skąd się to wzięło, ale nie do końca. Moje rozumowanie wyglądało następująco. Wynik ten sam, jednak rozumowanie bardzo na około.

Skoro w jednym z pudełek ma znaleźć się co najmniej 8 przedmiotów, to mamy do czynienia z przypadkami ze zbioru \{8,...,14\}, tzn. załóżmy, że w pierwszym przypadku w pierwszym pudełku mamy 8 przedmiotów, w drugim przypadku, że w pierwszym pudełku jest 9 przedmiotów itd. W pierwszym przypadku, gdy w pierwszym pudełku jest dokładnie 8 przedmiotów, to w którymś z pozostałych dwóch pudełek przedmiotów może być maksymalnie 6. Tzn możemy mieć sytuację np 8|6|0, gdzie | to "odstęp" między pudełkami. W takim razie, możemy wybrać sześcioelementowe kombinacje ze zbioru dwu elementowego. Jednak należy uwzględnić następujący przypadek, np. 8|3|3. Zatem będą to kombinacje z powtórzeniami. Uzyskuję następujące wyrażenie, dla pierwszego przypadku:

{2 + 6 - 1 \choose 6} =  {7 \choose 6} = 7

Teoretycznie się zgadza, bo na palcach jednej ręki można policzyć przypadki (8|6|0 , 8|0|6 , 8|5|1 , 8|1|5 , 8|4|2 , 8|2|4 , 8|3|3). Jednak czy to na pewno będą kombinacje z powtórzeniami? Przecież w tym przypadku kolejność elementów ma znaczenie (8|6|0 , 8|0|6), zatem nie szukamy konkretnego podzbioru, tylko ciągu elementów (?). Proszę rozwiać moje wątpliwości i wyjaśnić w którym miejscu głupieje :P

Dla przypadku drugiego, gdzie w pierwszym pudełku znajduje się 9 przedmiotów, do jednego z pozostałych dwóch pudełek możemy włożyć maksymalnie 5 przedmiotów. Ponieważ mamy nieparzystą liczbę przedmiotów do rozmieszczenia w parzystej ilości pudełkach, to nie zachodzi taka sytuacja, że elementy mogą się powtórzyć. Mamy zatem kombinacje bez powtórzeń (?). Mam problem z zapisaniem tego faktu za pomocą dwumianu Newtona, jednak na palcach jednej ręki jestem w stanie policzyć przypadki, których będzie 6. (9|5|0 , 9|0|5 , 9|4|1 , 9|1|4 , 9|2|3 , 9|3|2).

Dla przypadku trzeciego, czyli dla 10 przedmiotów w pierwszym pudełku znowu wracamy do przypadku, gdzie będziemy mieli powtórzenia, ponieważ w jednym z pudełek mogą być maksymalnie 4 przedmioty. Otrzymujemy n=2 oraz k=4, zatem:

{2 + 4 - 1 \choose 4} =  {5 \choose 4} = 5

Co zgadza się z paluszkami (10|4|0 , 10|0|4, 10|3|1|, 10|1|3 , 10|2|2 ). Widać pewną analogię, ponieważ z każdą liczbą parzystą większą od 8 w pierwszym pudełku liczba przypadków maleje o 2. Podobną analogię można zauważyć dla liczb nieparzystych. Dla czwartego przypadku, gdzie w pierwszym pudełku mamy 11 przedmiotów widać, że będą 3 przypadki.

Koniec końców otrzymuję (oczywiście każdy przypadek sumuję):

{7 \choose 6} + 6 +  {5 \choose 4} + 4 + {3 \choose 2} + 2 + {1 \choose 0} = 7+6+5+4+3+2+1 = 28

Oczywiście to nie koniec, bo przypadek wcześniej wymieniony należy poddać procesowi permutacji (:P), zatem otrzymany wynik 28 należy pomnożyć przez 3. Otrzymujemy wynik 84.

Prosiłbym jednak o wytłumaczenie tego zapisu 3 \cdot  {8 \choose 6}  = 84, który jak widać zdecydowanie przyspiesza cały proces.

b) W tym przypadku wystarczy policzyć wszystkie możliwości i po prostu odjąć od wyniku z podpunktu a, ponieważ ten przypadek jest zaprzeczeniem przypadku a). Niestety, na ćwiczeniach otrzymaliśmy kompletną moim zdaniem bzdurę, ponieważ wyszło coś takiego: (Chyba, że ja źle przepisałem i nie rozczytałem z tablicy)

Mam zapisane, że wszystkich przypadków jest:

{11 \choose 14}

Mniejsza o prawdopoodobnie moje błędy, przedstawię mój tok myślenia:

Wydaję mi się, że powinny być tutaj kombinacje z powtórzeniami. Elementy oczywiście mogą się powtarzać, a kolejność ustawienia każdego elementu w pudełku jest nieistotna. Otrzymujemy zatem liczbę 14-elementowych kombinacji z powtórzeniami zbioru trzyelementowego. Zatem:

{3+14-1 \choose 14} =  {16 \choose 14}

Podsumowując, odpowiedź do tego zadania wyglądałaby następująco:

{16 \choose 14} - 84 = 120 + 84 = 204
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 2 kwi 2018, o 19:56 
Użytkownik
Avatar użytkownika

Posty: 237
Lokalizacja: Płock
Co do podpunktu a), to zadanie sprowadza się do wyznaczenia liczby rozwiązań równania a+b+c=14 w liczbach naturalnych, przy założeniu, że jedna ze zmiennych jest nie mniejsza od 8. Przypuśćmy, że a\geq 8. Dokonajmy podstawienia d=a-8. Wtedy otrzymujemy równanie b+c+d=6. Należy wyznaczyć liczbę jego rozwiązań w liczbach naturalnych. W którymś poście wyjaśniałem Ci jak się to robi, więc teraz skorzystamy z gotowego wzoru. Mamy {6+3-1 \choose 3-1} = {8 \choose 2}. Teraz uwzględnijmy przypadki, gdy b\geq 8 lub c\geq 8. Oczywiście w obydwu przypadkach otrzymamy ten sam wynik, więc ostatecznie mamy 3\cdot{8 \choose 2}.

Podpunkt b).
Cytuj:
b) W tym przypadku wystarczy policzyć wszystkie możliwości i po prostu odjąć od wyniku z podpunktu a, ponieważ ten przypadek jest zaprzeczeniem przypadku a).

Nie jest zaprzeczeniem poprzedniego przypadku. W pierwszym przypadku w DOKŁADNIE jednym pudełku było nie więcej niż 8 przedmiotów.

Zagadnienie sprowadza się do wyznaczenia liczby naturalnych rozwiązań równania x_1+x_2+x_3=14, gdzie x_i\leq 7 dla 1\leq i \leq 3. Spróbuj teraz zrobić to sam, pokazałem jak.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Liczby czterocyfrowe, pudełka  zuza_15  2
 Przedmioty i szuflady  pawellogrd  4
 8 różnokolorowych kul, 3 pudełka, zadne nie jest puste  smmileey  4
 [kombinatoryka] jednakowe pudełka i przedmioty  fmichal  1
 Nierozróżnialne przedmioty w rozróznialnych pudełkach  anq_  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl