Kilka ciekawych problemów z kombinatoryki

[kriss240]

Witam serdecznie wszystkich czytających tego posta. Otóż jestem studentem informatki i otrzymałem kilka zadań do rozwiązania, niestety nie do końca wiem jak je "ugryźć". Zadania nie są zbyt skomplikowane rachunków ale liczby się pomysł, którego jeszcze nie mam, ale może ktoś z was ma i się zemną podzieli. Oto one.

---------------------------------------------------------

1. Na ile sposobów można obdarować 8 dzieci 36 cukierkami tak aby rozdać wszystkie cukierki,
nie pozostawiając żadnego z dzieci bez cukierków i tak aby każde dziecko miało parzystą liczbę cukierków.

2. W turnieju wzięło udział 9 szachistów. Rozegrano pewną liczbę spotkań singlowych, w których żadna para graczy nie bierze udziału więcej niż raz.
Należy wykazać że bez względu na liczbę rozegranych spotkań wśród zawodników jest co najmniej dwóch takich, którzy rozegrali tyle samo spotkań w tym turnieju.

3. W gonitwie bierze udział 4 psy ponumerowane kolejnymi liczbami od 1 do 4.
Na ile sposobów może zakończyć się gonitwa tak aby żaden z psów nie zajął miejsca zgodnego ze swoim numerem.

4. Ile jest permutacji słowa MATEMATYKA w których przynajmniej jedna z grup liter występuje więcej niż jeden raz w tym słowie i stoi obok siebie.

5. Na ile sposobów można ułożyć w ciąg 4 jednakowe kule zielone, 4 jednakowe kule żółte i 5 kul ponumerowanych.

6. W pewnym klubie trenuje 5 takich samych bokserów. Klub planuje rozgrywki ligowe w sezonie, w którym musi rozegrać 8 spotkań z innymi klubami. Na ile sposobów można zaplanować rozgrywki w tym sezonie jeśli w każdym meczu trzeba wystawić jedną parę bokserską?

7. Na ile sposobów można rozdzielić 6 ponumerowanych procesów pomiędzy 4 jednakowe procesory tak, aby żaden z procesorów nie był obciążany więcej niż 3 procesami?
Rozdzielić trzeba wszystkie procesy, żaden z procesorów nie może pozostać bezczynny i każdy proces będzie wykonywany na jednym procesorze.

8. Na ile sposobów można zaplanować wykonanie 5 różnych urządzeń na 3 stanowiskach pracy, tak aby żaden z nich nie pozostało bezczynne?
Plan musi podawać dla każdego urządzania numer stanowiska i określić w jakije kolejności urządzania będą składane na każdym stanowisku.

9 Na ile sposobów można przydzielić 5 ponumerowanych procesorów do wykonania na 3 ponumerowane procesory, jeżeli procesy są wykonywane przez procesor zawsze w całości i należy określić kolejność wykonywania procesów dla procesora, któremu przydzielono więcej niż jeden proces.

10. Do pracy zgłosiło się 22 tłumaczy. 13tu z nich znało język francuski, 14 znało włoski, język niemiecki znało tyle samo co francuski i włoski jednocześnie, 6 z tłumaczy znało francuski i niemiecki a 4 z tłumaczy znało język włoski i niemiecki ale nie znało francuskiego.
Ilu tłumaczy nie znało ani jednego z wymienionych języków?

[ellipsis]

1.a) Dla i=1,...,8 oznaczmy liczbę cukierków otrzymanych przez i-te dziecko
symbolem x_i.
Wartości tych zmiennych są liczbami całkowitymi, dodatnimi, parzystymi, a ich
suma wynosi 36.
b) Skoro każde dziecko ma dostać parzystą liczbę cukierków, to możemy
wprowadzić nowe zmienne całkowitoliczbowe:
y_i = x_i /2, dla i=1,...,8.
Wartości tych zmiennych są liczbami całkowitymi, dodatnimi, a ich suma wynosi 18.
c) Skoro każdy ma dostać po co najmniej 1 cukierku, to
wprowadzić nowe zmienne całkowitoliczbowe:
z_i = y_i - 1, dla i=1,...,8.
Wartości tych zmiennych są liczbami całkowitymi, nieujemnymi, a ich suma wynosi 10.
_______________

Skoro przyporządkowania
(x_1,...,x_8) <-> (y_1,...,y_8) <-> (z_1,...,z_8)
(gdzie układy te spełniają podane wyżej zależności) są wzajemnie jednoznaczne,
to takich układów jest tyle samo. Otrzymaliśmy zatem, że poszukiwana liczba
układów to liczba rozbić zbioru 10-elementowego na 8 numerowanych(?) zbiorów. Na
pewno znasz ten wzór...
PS. Pytajnik w powyższym tekście jest związany z tym, że nie wiem, czy np.
układy (2,2,2,2,2,2,2,22) i (22,2,2,2,2,2,2,2) traktujemy jako identyczne, czy
różne...

[ellipsis]

2. Przypuśćmy, że każdy z graczy rozegrał inną liczbę partii. Skoro liczba
partii rozegranych przez każdego z graczy jest liczbą całkowitą nieujemną
niewiększą niż 8, to któryś gracz rozegrał partie z wszystkimi pozostałymi
(rozegrał 8 partii), w szczególności rozegrał także partię z graczem, który nie
rozegrał ani jednej partii (rozegrał 0 partii). Otrzymaliśmy sprzeczność.

[ellipsis]

3. Dla i=1,...,4 niech x_i oznacza miejsce zajęte przez i-tego psa. Oznaczmy
literą Omega zbiór wszystkich permutacji zbioru {1,...,4}. Dla i=1,...,4 określmy
A_i = { (x_1,...,x_4) e Omega | x_i=i }.
Rozważmy zdarzenie przeciwne do podanego w zadaniu, tj.
A' = { (x_1,...,x_4) e Omega | x_i=i dla pewnego i=1,...,4 }.
Wtedy oczywiście
A' = A_1 u ... u A_4.
Ze wzoru podanego zapewne na wykładzie:
|A'| = (Suma _(1<=i<=4) |A_i|) - (Suma _(1<=i<j<=4) |A_i n A_j|) +
+ (Suma _(1<=i<j<k<=4) |A_i n A_j n A_k|) - (|A_1 n ... n A_4|).
Zauważ, że:
* |A_i| = 3! dla 1<=i<=4,
* |A_i n A_j| = 2! dla 1<=i<j<=4,
(...)
* |A_1 n ... n A_4| = 0!.
Teraz łatwo obliczysz |A'| i ostatecznie
|A| = |Omega| - |A'|.
PS. Oczywiście można to zadanie ,,rozwiązać" łatwiej, wypisując wszystkie
elementy zbioru Omega i wykreślając te spośród nich, które nie należą do
szukanego zbioru. Ale powyższe rozwiązanie ma tę zaletę, że łatwo je rozszerzyć
dla dowolnej liczby psów, a nawet wyprowadzić wzór ogólny...

[Gość: bartek]

Do zadania z psami wykorzystaj poniższą uwagę.
Dla n ponumerowanych przedmiotów rozmieszczonych pojedynczo w n ponumerowanych
szufladach tak, aby numery przedmiot-szuflada były różne,liczbę rozmieszczeń A_n
mozna wyrazić wzorem rekurencyjnym:
A_n=(n-1)*[A_(n-1)+A_(n-2)] przy czym A_1=0, A_2=1
z wzoru A_3=2*(1+0)=2, A_4=3*(2+1)=9, A_5=4*(9+2)=44

[ellipsis]

4. Nie rozumiem treści tego zadania - co to jest grupa liter? Sorry... :(

[kriss240]

Ile jest permutacji słowa MATEMATYKA, w których przynajmniej jedna z
grup liter występujących więcej niż jeden raz w tym słowie stoi
obook siebie.
Prawidłowy wynik to podobno 1 428 480.
Grupa liter to MM,AA,TT.

[ellipsis]

Niech Omega będzie zbiorem wszystkich permutacji słowa MATEMATYKA. Wtedy
|Omega| = 10!/[(2!)^2*3!].
(Wśród wszystkich permutacji zbioru 10-elementowego utożsamiamy te, które
różnią się kolejnością liter M, A lub T.)
Określmy:
A_M = { słowo e Omega | oba M są koło siebie },
A_A = { słowo e Omega | wszystkie A są koło siebie },
A_T = { słowo e Omega | oba T są koło siebie }.
Wtedy
|A_M| = |A_T| = 9!/(2!*3!),
|A_A| = 8!/(2!)^2.
(,,Sklejamy" wyróżnioną literą, a następnie wśród wszystkich permutacji zbioru
9-elementowego utożsamiamy te, które różnią się kolejnością pozostałych
,,wielokrotnych" liter.)
Ponadto
|A_M n A_A| = |A_A n A_T| = 7!/2!,
|A_M n A_T| = 8!/3!,
|A_M n A_A n A_T| = 6!.
Stosując odpowiedni wzór
|A_M u A_A u A_T| =
= (|A_M| + |A_A| + |A_T|) - (|A_M n A_A| + |A_M n A_T| + |A_A n A_T|) + |A_M n
A_A n A_T| =
= [9!/(2!*3!) + 8!/(2!)^2 + 9!/(2!*3!)] - (7!/2! + 8!/3! + 7!/2!) + 6! =
= 5! * [9*8*7*6/(2*6) + 8*7*6/(2*2) + 9*8*7*6/(2*6) - (7*6/2 + 8*7*6/6 + 7*6/2)
+ 6] =
= 5! * [252 + 84 + 252 - (21 + 56 + 21) + 6] =
= 5! * 494 = 59 280.
Uwaga. |Omega| = 302 400 < 1 428 480, więc ten wynik nie jest prawidłowy przy
utożsamieniu identycznych liter... Spróbujmy zatem nie utożsamiać tych liter.
Rozumujemy jak wyżej, więc tylko wypiszę liczebności zbiorów:
|A_M| = |A_T| = 9! * 2!,
|A_A| = 8! * 3!,
|A_M n A_A| = |A_A n A_T| = 7! * 2! * 3!,
|A_M n A_T| = 8! * 2! * 2!,
|A_M n A_A n A_T| = 6! * 2! * 3! * 2!.
Stosując odpowiedni wzór
|A_M u A_A u A_T| =
= (|A_M| + |A_A| + |A_T|) - (|A_M n A_A| + |A_M n A_T| + |A_A n A_T|) + |A_M n
A_A n A_T| =
= (9! * 2! + 8! * 3! + 9! * 2!) - (7! * 2! * 3! + 8! * 2! * 2! + 7! * 2! * 3!)
+ 6! * 2! * 3! * 2! =
= 6! * [(9*8*7*2 + 8*7*6 + 9*8*7*2) - (7*2*6 + 8*7*2*2 + 7*2*6) + 2*6*2] =
= 6! * [(1008 + 336 + 1008) - (84 + 224 + 84) + 24] =
= 6! * 1964 = 1 428 480.
HURRA! Udało się!!! ;)

[ellipsis]

5.
Metoda 1.
Najpierw traktujemy wszystkie kule jako rozróżnialne i ustawiamy je w ciąg
długości 13, a następnie utożsamiamy te spośród otrzymanych ciągów, które różnią
się jedynie kolejnością kul zielonych i/lub kolejnością kul żółtych. Poszukiwana
liczba jest ilorazem jednej silni przez iloczyn dwóch innych silni.
Metoda 2.
Najpierw wybieramy 4 miejsca spośród 13 dla kul zielonych, następnie spośród
pozostałych 9 miejsc wybieramy 4 dla kul żółtych, a na pozostałych 5 miejscach
ustawiamy kule ponumerowane w dowolny sposób. Poszukiwana liczba jest iloczynem
dwóch symboli (n po k) i jednej silni.

[ellipsis]

6. Nie rozumiem... Jeżeli wszyscy bokserzy są tacy sami, to każda para wybrana
spośród nich jest też taka sama... Sorry... :(

[ellipsis]

7. Dla i=1,...,6 oznaczmy symbolem x_i numer procesora, który obsłuży i-ty
proces. Wartości zmiennych x_i są liczbami całkowitymi między 1 a 4. Literą
Omega oznaczmy zbiór wszystkich wariacji 6-elementowych z powtórzeniami zbioru
{1,...,4}. Dla j=1,...,4 określmy
A_j = { (x_1,...,x_6) e Omega | j nie należy do zbioru {x_1,...,x_6} }.
Rozważmy zdarzenie przeciwne do podanego w zadaniu, tj.
A' = { (x_1,...,x_4) e Omega | j nie należy do zbioru {x_1,...,x_6} dla
pewnego j=1,...,4 }.
(Należy zauważyć, że wymaganie ,,żaden z procesorów nie może pozostać
bezczynny" implikuje, że ,,żaden z procesorów nie był obciążany więcej niż 3
procesami".) Dalej jak w zad. 3.

[ellipsis]

8. Podkreślmy, że tym razem istotna jest kolejność wykonywanych zadań.
a) Najpierw utożsamiamy wszystkie procesy i podobnie jak w zad. 1. rozbijamy 5
urządzeń na 3 stanowiska w taki sposób, aby na każdym stanowisku było obsłużone
przynajmniej jedno urządzenie.
* Dla i=1,2,3 oznaczmy liczbę urządzeń obsłużonych na i-tym stanowisku symbolem
x_i. Wartości tych zmiennych są liczbami całkowitymi, dodatnimi, a ich suma
wynosi 5.
* Skoro żadne ze stanowisk nie pozostaje bezczynne, to możemy
wprowadzić nowe zmienne całkowitoliczbowe:
y_i = x_i - 1, dla i=1,2,3.
Wartości tych zmiennych są liczbami całkowitymi, nieujemnymi, a ich suma wynosi 2.
b) Otrzymaną w punkcie a) liczbę rozbić liczby zadań na stanowiska mnożymy
przez 5!, bo każda kolejność zadań daje nam inny harmonogram pracy.

[ellipsis]

9. To uproszczona wersja zad. 8. - obliczenie liczby rozbić utożsamionych
procesów na poszczególne procesory otrzymujemy z odpowiedniego wzoru.

[ellipsis]

10. Niech A_f, A_w i A_n oznaczają odpowiednio zbiory tłumaczy znających język francuski, włoski i niemiecki. Rozważmy zdarzenie przeciwne do poszukiwanego, tzn.
A' = { tłumacz spośród 22 | tłumacz zna francuski, włoski lub niemiecki }.
Wtedy oczywiście
A' = A_f u A_w u A_n.
Z treści zadania:
|A_f| = 13,
|A_w| = 14,
|A_n| = |A_f n A_w|,
|A_f n A_n| = 6,
|A_w n A_n \ A_f| = 4.
Ze wzoru podanego w rozwiązaniu zad. 3. wnioskujemy, że
|A'| = |A_f u A_w u A_n| =
= (|A_f| + |A_w| + |A_n|) - (|A_f n A_w| + |A_f n A_n| + |A_w n A_n|) + (|A_f n A_w n A_n|) =
= |A_f| + |A_w| + (|A_n| - |A_f n A_w|) - |A_f n A_n| - (|A_w n A_n| - |A_f n A_w n A_n|) = ... .

[Gość: kolega]

1)Z 15 par cukierków daj po jednej każdemu dziecku - pozostałe 7par cukierków
rozdziel dowolnie. (C7z14)=3432.
2)Gdyby każdy rozegrał inną liczbę spotkań, to ich liczba wyniosłaby co najmniej
(0+1+2+...+8)/2=36 spotkań, a to jest liczba C(2z9)=36 oznaczająca,że każdy z 9
grających rozegrał 8 spotkań, co jest sprzeczne z przyjętym założeniem.
3)kazdy pies może byc na trzech miejscach róznych od jego numeru
V(4z3)=3^4
4) Niejaso sprecyzowane
5)13!/(4!)^2
6)Z pięciu zawodników mozna utworzyc 10 róznych par.Na kazdy mecz można
wytypowac dowolna z tych par. wariacja z powtorzeniami.
7)[C(3z6)+C(2z6)*C(2z4)] jezeli procesory numerowane, to [...]*4!
8) V(3z5)*3!+V(2z%)*V(2z3)*3!
9)Popraw tekst
10)5 - sprawdź, czy dokładnie przepisałeś treśc.

[ellipsis]

Gość portalu: kolega napisał(a):
> 1)Z 15 par cukierków daj po jednej każdemu dziecku - pozostałe 7par cukierków
> rozdziel dowolnie. (C7z14)=3432.
Zadanie stanowi, że należy rozdać 36 cukierków, czyli 18 par...
> 3)kazdy pies może byc na trzech miejscach róznych od jego numeru
> V(4z3)=3^4
Ale nie zawsze pies może zająć to miejsce - np. jeżeli pies #1 zajął miejsce
4., to pies #2 już nie może zająć tego miejsca... Poza tym
3^4 = 81 > 24 = 4!,
a jest tylko 4! możliwych wyników gonitwy...
> 6)Z pięciu zawodników mozna utworzyc 10 róznych par.Na kazdy mecz można
> wytypowac dowolna z tych par. wariacja z powtorzeniami.
Pozostaje pytanie, czy w meczu nie wystawiamy przypadkiem par uporządkowanych...
> 7)[C(3z6)+C(2z6)*C(2z4)] jezeli procesory numerowane, to [...]*4!
Nie.
> 8) V(3z5)*3!+V(2z%)*V(2z3)*3!
Nie.

[Gość: bartek]

7. Na ile sposobów można rozdzielić 6 ponumerowanych procesów pomiędzy 4
jednakowe procesory tak, aby żaden z procesorów nie był obciążany więcej niż 3
procesami?
Rozdzielić trzeba wszystkie procesy, żaden z procesorów nie może pozostać
bezczynny i każdy proces będzie wykonywany na jednym procesorze.
Jeżeli procesory są nierozróżnialne, to przy podanych warunkach można procesy
podzielić w sposób 3+1+1+1 lub 2+2+1+1. Ponieważ procesy są ponumerowane,
przykładowy pierwszy rozdział jest{{1,2,3},4,5,6}przy czym trójkę można wybrać
na C(3z6)sposobów. Drugi rozdział, np.
{{3,4},{2,5}, 1,6} można dokonać na C(2z6)*(2z4) wszystkich takich rozdzieleń
jest 5*4+3*5*3*2=110 -( kolejność procesów nie jest ważna, tyko ich dobór). Tak
prawdopodobnie rozumował kolega.

[Gość: bartek]

10. Do pracy zgłosiło się 22 tłumaczy. 13tu z nich znało język francuski, 14
znało włoski, język niemiecki znało tyle samo co francuski i włoski
jednocześnie, 6 z tłumaczy znało francuski i niemiecki a 4 z tłumaczy znało
język włoski i niemiecki ale nie znało francuskiego.
Ilu tłumaczy nie znało ani jednego z wymienionych języków?
Nnarysuj trzy okręgi,z których każdy przecina sie z dwoma pozostałymi.Okręgi te
wyznaczają 3 koła oznaczające zbiory W,F,N tłumaczy mówiących odpowiednio po
włosku, francusku i niemiecku.Powstalo 7 obszarów, które oznaczmy:
I - W.F.N -znajacy trzy języki
II -W.F\N, III -F.N|W, IV - N.W\F znajacy dokładnie dwa jeżyki
V - W\(NUF), VI - F\(WUN), VII - N|(WUF)
Oznaczmy liczby osób w kolejnych grupach na podstawie tresci zadania:
I - x,II - y,III - 6-x, IV - 4, V - 10-x-y, VI - 7-y, VII - x+y-10
dodajac ww liczby otrzymujemy 17, tzn. że 5 tłumaczy nie znało żadnego z
omawianych wyzej jężykow.