kombinatoryka 3 zadania

anetaaneta1 · Post autor: **anetaaneta1** » 4 lis 2012, o 20:14

Zad. 1.
Planszą do japońskiej gry GO jest kwadrat podzielony na 169 małych kwadratowych oczek w układzie 13×13. W każdym oczku stawiamy kamień - czarny lub biały. Nazwijmy obrazem każde możliwe zapełnienie tej planszy czarnymi i białymi kamieniami. Ile takich obrazów można utworzyć?

zad 2.
Ojciec chce oddać swoim trzem synom swój majątek w postaci dziesięciu jednakowych złotych monet. Na ile sposobów może to zrobić, przy założeniu, że każdemu synowi chce przekazać co najmniej jedną monetę?
Zad. 3.
W woreczku znajduje się 12 jednakowych białych kul. Na ile sposobów można te kule pomalować trzema kolorami: czerwonym, zielonym i niebieskim, każdy kolor wykorzystując do pomalowania co najmniej jednej kuli?

Z góry bardzo dziękuje za pomoc

tometomek91 · Post autor: **tometomek91** » 4 lis 2012, o 20:50

1) Miejsc jest \(\displaystyle{ 169}\) i na każdym może stać albo biały albo czarny kamień, czyli dwie możliwości, więc obrazów jest \(\displaystyle{ 2^{169}}\).

2) Pytamy ile jest rozwiązań równania \(\displaystyle{ x+y+z=10}\) w liczbach całkowitych dodatnich, czyli ile jest rozwiązań równania \(\displaystyle{ (a+1)+(b+1)+(c+1)=10}\) w liczbach całkowitych nieujemnych, lub równoważnie \(\displaystyle{ a+b+c=7}\). Takich rozwiązań jest \(\displaystyle{ {10 \choose 3}}\).

3) Podobnie jak 2).

anetaaneta1 · Post autor: **anetaaneta1** » 4 lis 2012, o 22:24

a odnośnie zad 1 skąd wiadomo że to wariacje z powtórzeniami a nie np. kombinacje ?

Vardamir · Post autor: **Vardamir** » 4 lis 2012, o 22:32

Czasem wystarczy się zastanowić co chcemy liczyć, a nie zastanawiać jaki schemat będzie tu pasował.

W zadaniu 1 :

Dla każdego ze 169 miejsc masz dwie możliwości (biały albo czarny kamień).

Zatem mamy \(\displaystyle{ \underbrace{2\cdot 2 \cdot \cdots \cdot 2 }_{169}}\) możliwości.

anetaaneta1 · Post autor: **anetaaneta1** » 4 lis 2012, o 22:35

aha dzięki wielkie
a jeszcze nie za bardzo rozumiem w zadaniu 2 skąd się wzięło \(\displaystyle{ {10 \choose 3}}\)
mógłbyś mi to tak łopatologicznie jak w pierwszym wytłumaczyć ?

mat_61 · Post autor: **mat_61** » 5 lis 2012, o 00:07

tometomek91, Twoje rozwiązanie zadania 2 nie jest poprawne.

Załóżmy, że mamy na stole dziesięć monet:

\(\displaystyle{ x x x x x x x x x x}\)

Jeżeli teraz chcemy je podzielić na trzy części tak aby w każdej była co najmniej jedna moneta to wystarczy pomiędzy nimi (dziewięć możliwości) postawić dwie przegródki, np. tak:

\(\displaystyle{ x x x x | x x x x x| x}\)

co oznacza, że pierwszy syn dostanie cztery monety, drugi pięć, a trzeci jedną.

Wszystkich możliwości podziału jest więc \(\displaystyle{ {9 \choose 2}}\)

-- 5 lis 2012, o 00:13 --

Ewentualnie odnosząc się do rozwiązania w liczbach całkowitych nieujemnych równania \(\displaystyle{ a+b+c=7}\) mamy 7-elementową kombinację z powtórzeniami ze zbioru 3-elementowego, czyli \(\displaystyle{ {7+3-1 \choose 7}= {9 \choose 7}}\)