Witam
Mam następujące zadanie:
Roztargniony Mikołaj przygotował 100 różnych paczek, w rozwożeniu których pomagają mu 3 identyczne renifery zaprzężone w sanie. Na ile sposobów Mikołaj może rozłożyć paczki do sań jeśli nie wszystkie sanie muszą wyruszyć w podróż z Mikołajem?
Moja pierwsza myśl to \(\displaystyle{ 3^{100}}\)
Każdą paczkę możemy spakować na trzy sposoby, bo mamy trzy sanie do wyboru.
Sprawdziłem to dla dwóch paczek i po rozpisaniu wyszło mi 6 sposobów zamiast 9.
Prosiłbym o weryfikację mojego rozumowania i nakierowanie na właściwe tory z wytłumaczeniem czemu rozumowanie jest nieprawidłowe. Zależy mi równie mocno na zrozumieniu co na dobrej odpowiedzi.
Święty mikołaj i prezenty
-
- Użytkownik
- Posty: 39
- Rejestracja: 16 sty 2008, o 08:33
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 4 razy
Święty mikołaj i prezenty
Ostatnio zmieniony 18 cze 2012, o 22:32 przez ares41, łącznie zmieniany 1 raz.
Powód: Błąd ortograficzny w nazwie tematu.
Powód: Błąd ortograficzny w nazwie tematu.
- Kacperdev
- Użytkownik
- Posty: 3260
- Rejestracja: 23 mar 2010, o 19:19
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 17 razy
- Pomógł: 686 razy
Święty mikołaj i prezenty
Problem z metodą wariacji polega, że bierze ona także pod uwagę "sposoby" kolejności ułożenia prezentów na saniach tzn. sanie 1 {prezent1, prezent2} metoda ta dolicza takze {prezent2, prezent1}
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Święty mikołaj i prezenty
Nieprawda.Kacperdev pisze:Problem z metodą wariacji polega, że bierze ona także pod uwagę "sposoby" kolejności ułożenia prezentów na saniach tzn. sanie 1 {prezent1, prezent2} metoda ta dolicza takze {prezent2, prezent1}
Dla dwóch paczek prawidłowym wynikiem jest \(\displaystyle{ 2}\): obie paczki na jednych saniach albo na różnych saniach. Na pewno bierzesz pod uwagę, że renifery z saniami są nierozróżnialne?Gwynnbleid1 pisze: Sprawdziłem to dla dwóch paczek i po rozpisaniu wyszło mi 6 sposobów zamiast 9.
-
- Użytkownik
- Posty: 39
- Rejestracja: 16 sty 2008, o 08:33
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 4 razy
Święty mikołaj i prezenty
Wiec muszą zatem to być kombinacje z powtórzeniami.
k = 100
n = 3
\(\displaystyle{ {k + n -1 \choose k} = \frac{(k + n - 1)!}{(k!(n - 1)!)!} = \frac{(100 + 3 - 1)!}{(100!(3 - 1)!)!} = \frac{(102)!}{100!2!} = \frac{101 \cdot 102}{2} = 51 \cdot 101 = 5151}\)
Po wysłaniu dopiero zobaczyłem post Kacperdev'a:
każdy w jednej, dwie w jednej i jedna w drugiej i trzy w różnych, razem \(\displaystyle{ 3}\) sposoby.
Natomiast dla 100 paczek dalej będzie \(\displaystyle{ 3}\), ponieważ nie mamy już więcej możliwości. Czy tak ?
k = 100
n = 3
\(\displaystyle{ {k + n -1 \choose k} = \frac{(k + n - 1)!}{(k!(n - 1)!)!} = \frac{(100 + 3 - 1)!}{(100!(3 - 1)!)!} = \frac{(102)!}{100!2!} = \frac{101 \cdot 102}{2} = 51 \cdot 101 = 5151}\)
Po wysłaniu dopiero zobaczyłem post Kacperdev'a:
Co masz na myśli mówiąc nieprawda. To że nie ma tutaj zastosowania, czy że całe stwierdzenie jest nieprawidłowe ?Kacperdev pisze:Nieprawda.norwimaj pisze:Problem z metodą wariacji polega, że bierze ona także pod uwagę "sposoby" kolejności ułożenia prezentów na saniach tzn. sanie 1 {prezent1, prezent2} metoda ta dolicza takze {prezent2, prezent1}
Rzeczywiście nie wziąłem tego zupełnie pod uwagę. Czyli dla trzech prezentów byłoby:Kacperdev pisze:Dla dwóch paczek prawidłowym wynikiem jest \(\displaystyle{ 2}\): obie paczki na jednych saniach albo na różnych saniach. Na pewno bierzesz pod uwagę, że renifery z saniami są nierozróżnialne?Gwynnbleid1 pisze: Sprawdziłem to dla dwóch paczek i po rozpisaniu wyszło mi 6 sposobów zamiast 9.
każdy w jednej, dwie w jednej i jedna w drugiej i trzy w różnych, razem \(\displaystyle{ 3}\) sposoby.
Natomiast dla 100 paczek dalej będzie \(\displaystyle{ 3}\), ponieważ nie mamy już więcej możliwości. Czy tak ?
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Święty mikołaj i prezenty
Nie. Kombinacje z powtórzeniami są, gdy są nierozróżnialne kule i rozróżnialne pojemniki, a nie na odwrót.Gwynnbleid1 pisze:Wiec muszą zatem to być kombinacje z powtórzeniami.
Że zdanie napisane przez Kacperdev'a jest fałszywe. Pomylił się on i wskazał błąd tam, gdzie akurat tego błędu nie było.Gwynnbleid1 pisze: Co masz na myśli mówiąc nieprawda.
Nie. Jeśli mamy prezenty \(\displaystyle{ p_1,p_2,p_3}\), to mamy następujące możliwości podziału bagażu na renifery:Gwynnbleid1 pisze: Czyli dla trzech prezentów byłoby:
każdy w jednej, dwie w jednej i jedna w drugiej i trzy w różnych, razem \(\displaystyle{ 3}\) sposoby.
- \(\displaystyle{ \{\{p_1,p_2,p_3\},\{\},\{\}\}}\)
- \(\displaystyle{ \{\{p_1,p_2\},\{p_3\},\{\}\}}\)
- \(\displaystyle{ \{\{p_1,p_3\},\{p_2\},\{\}\}}\)
- \(\displaystyle{ \{\{p_2,p_3\},\{p_1\},\{\}\}}\)
- \(\displaystyle{ \{\{p_1\},\{p_2\},\{p_3\}\}}\)
-
- Użytkownik
- Posty: 39
- Rejestracja: 16 sty 2008, o 08:33
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 4 razy
Święty mikołaj i prezenty
Trochę mi się to w głowie komplikuje. Czy znasz może jakąś rozpiskę, która podpowiada z czym mamy doczynienia ? Rozróżnialne to to, nierozróżnialne to to, kolejność ważna i nieważna itp? Wkułbym to na pamięć i ułatwiłoby mi to niezmiernie życie. Znalazłem wcześniej coś takiego: , ale jak widzę daleko temu do perfekcji...norwimaj pisze:Nie. Kombinacje z powtórzeniami są, gdy są nierozróżnialne kule i rozróżnialne pojemniki, a nie na odwrót.Gwynnbleid1 pisze:Wiec muszą zatem to być kombinacje z powtórzeniami.
Myślałem, że wariacje rzeczywiście uwzględniają kolejność i a,b to nie to samo co (b,a)norwimaj pisze:Że zdanie napisane przez Kacperdev'a jest fałszywe. Pomylił się on i wskazał błąd tam, gdzie akurat tego błędu nie było.Gwynnbleid1 pisze: Co masz na myśli mówiąc nieprawda.
Teraz dopiero spojrzałem, że prezenty są różne. Przyznam się szczerze, że teraz nie wiem jak ugryźć ten problem dla 100 prezentów. Jakaś wskazówka ?norwimaj pisze:Nie. Jeśli mamy prezenty \(\displaystyle{ p_1,p_2,p_3}\), to mamy następujące możliwości podziału bagażu na renifery:Gwynnbleid1 pisze: Czyli dla trzech prezentów byłoby:
każdy w jednej, dwie w jednej i jedna w drugiej i trzy w różnych, razem \(\displaystyle{ 3}\) sposoby.
- \(\displaystyle{ \{\{p_1,p_2,p_3\},\{\},\{\}\}}\)
- \(\displaystyle{ \{\{p_1,p_2\},\{p_3\},\{\}\}}\)
- \(\displaystyle{ \{\{p_1,p_3\},\{p_2\},\{\}\}}\)
- \(\displaystyle{ \{\{p_2,p_3\},\{p_1\},\{\}\}}\)
- \(\displaystyle{ \{\{p_1\},\{p_2\},\{p_3\}\}}\)
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Święty mikołaj i prezenty
Zacznij tak jak zacząłeś, czyli jeśli rozróżniamy renifery, to mamy \(\displaystyle{ 3^{100}}\) możliwości. Teraz trzeba się zastanowić, jak ten wynik się zmieni, gdy przestaniemy renifery rozróżniać. Rozróżniając renifery liczymy poszczególne ustawienia wielokrotnie, tak jak w poprzednim przykładzie ustawienie \(\displaystyle{ \{\{p_1,p_2\},\{p_3\},\{\}\}}\) by było liczone sześciokrotnie:
\(\displaystyle{ (\{p_1,p_2\},\{p_3\},\{\}),}\)
\(\displaystyle{ (\{p_1,p_2\},\{\},\{p_3\}),}\)
\(\displaystyle{ (\{p_3\},\{p_1,p_2\},\{\}),}\)
itd.
a ustawienie \(\displaystyle{ \{\{p_1,p_2,p_3\},\{\},\{\}\}}\) trzykrotnie.
\(\displaystyle{ (\{p_1,p_2\},\{p_3\},\{\}),}\)
\(\displaystyle{ (\{p_1,p_2\},\{\},\{p_3\}),}\)
\(\displaystyle{ (\{p_3\},\{p_1,p_2\},\{\}),}\)
itd.
a ustawienie \(\displaystyle{ \{\{p_1,p_2,p_3\},\{\},\{\}\}}\) trzykrotnie.