Dziewięć kul (trzy białe, trzy czerwone i trzy czarne) ustawiamy losowo w ciąg. Ile jest takich ciągów, w których żadne dwie kule tego samego koloru nie będą stały obok siebie.
Kule tego samego koloru traktujemy jako nierozróżnialne.
Układanie kolorowych kul w ciąg
-
124K
- Użytkownik
- Posty: 30
- Rejestracja: 22 paź 2009, o 19:29
- Płeć: Mężczyzna
- Lokalizacja: Koszalin
- Pomógł: 5 razy
Układanie kolorowych kul w ciąg
Trudne zadanie i nie znam na nie prostego sposobu, ale widać po nim, że nie trzeba liczyć wszystkiego na piechotę a można rozpisać sobie tylko jedną gałąź i dojś do wyniku.
Będę zbiory kul reprezentował jako wektor ilości kul które w zbiorach zostały i zaznaczał zbiór z którego w następnym kroku kuli wziąść nie mogę. [3 3 3]
W pierwszym kroku zabieramy 1 kule na 3 sposoby. (powstają 3 wektory z takimi samymi składowymi i w następnym kroku nie można wziąść ze zbioru z 2 elementami)
[2 3 3]
W drugim kroku zabieramy 1 kule na 2 sposoby. (powstają 2 wektory z elementami 2 2 3 i w następnym kroku zawsze nie można wziąść z jednego ze zbiorów z 2 elementami)
[2 2 3]
W trzecim kroku kule możemy zabrać na 2 sposoby. (powstają 2 wektory, ale z różniącymi się elementami 1 2 3 i 2 2 2 ...)
[1 2 3] [2 2 2]
W czwartym kroku z każdego z powyższych wektorów powstają po dwa wektory...
[1 1 3] (2 rozw.) [1 2 2] (10 rozw.)
[1 2 2] (7 rozw.) [2 1 2] (10 rozw.)
I z tych 4 wektorów (rozpisując dalej) ostatecznie powstaje 29 rozwiązań.
Należy zauważyć, że wektory [1 2 2] i [2 1 2] to taki sam przypadek, a [1 2 2] to już coś zupełnie innego.
Podsumowując: pierwsze 3 kroki można wymnożyć, a później pomnożyć to przez 29 bo każda z 12 gałęzi z 3 poziomu ostatecznie się na dokładnie tyle rozwiązań rozbije.
Odp.: 3*2*2*29.
Będę zbiory kul reprezentował jako wektor ilości kul które w zbiorach zostały i zaznaczał zbiór z którego w następnym kroku kuli wziąść nie mogę. [3 3 3]
W pierwszym kroku zabieramy 1 kule na 3 sposoby. (powstają 3 wektory z takimi samymi składowymi i w następnym kroku nie można wziąść ze zbioru z 2 elementami)
[2 3 3]
W drugim kroku zabieramy 1 kule na 2 sposoby. (powstają 2 wektory z elementami 2 2 3 i w następnym kroku zawsze nie można wziąść z jednego ze zbiorów z 2 elementami)
[2 2 3]
W trzecim kroku kule możemy zabrać na 2 sposoby. (powstają 2 wektory, ale z różniącymi się elementami 1 2 3 i 2 2 2 ...)
[1 2 3] [2 2 2]
W czwartym kroku z każdego z powyższych wektorów powstają po dwa wektory...
[1 1 3] (2 rozw.) [1 2 2] (10 rozw.)
[1 2 2] (7 rozw.) [2 1 2] (10 rozw.)
I z tych 4 wektorów (rozpisując dalej) ostatecznie powstaje 29 rozwiązań.
Należy zauważyć, że wektory [1 2 2] i [2 1 2] to taki sam przypadek, a [1 2 2] to już coś zupełnie innego.
Podsumowując: pierwsze 3 kroki można wymnożyć, a później pomnożyć to przez 29 bo każda z 12 gałęzi z 3 poziomu ostatecznie się na dokładnie tyle rozwiązań rozbije.
Odp.: 3*2*2*29.
-
Majorkan
- Użytkownik
- Posty: 128
- Rejestracja: 14 paź 2007, o 18:45
- Płeć: Mężczyzna
- Lokalizacja: Kraków/Jasło
- Podziękował: 13 razy
- Pomógł: 33 razy
Układanie kolorowych kul w ciąg
Wielkie dzięki za pomoc, przy czym mam drobną uwagę co do tego rozwiązania.
Mianowicie, gałęzi trzeciego poziomu jest rzeczywiście 12, ale połowa z nich produkuje wektory typu [1 1 3] i [1 2 2] dające w sumie 9 rozwiązań, zaś druga połowa produkuje wektory typu [1 2 2] oraz [2 1 2] dające razem 20 rozwiązań.
Zatem w sumie będzie \(\displaystyle{ 6 \cdot 9 + 6 \cdot 20 = 6 \cdot 29 = 174}\) rozwiązań.
W każdym razie, ogólna idea jest chyba dobra; tak więc jeszcze raz dzięki.
Mianowicie, gałęzi trzeciego poziomu jest rzeczywiście 12, ale połowa z nich produkuje wektory typu [1 1 3] i [1 2 2] dające w sumie 9 rozwiązań, zaś druga połowa produkuje wektory typu [1 2 2] oraz [2 1 2] dające razem 20 rozwiązań.
Zatem w sumie będzie \(\displaystyle{ 6 \cdot 9 + 6 \cdot 20 = 6 \cdot 29 = 174}\) rozwiązań.
W każdym razie, ogólna idea jest chyba dobra; tak więc jeszcze raz dzięki.