Zbiór zadań, (zadania różne)
Zadanie 234
Dana jest nieograniczona liczba monet 10, 20 i 50 gr. Na ile sposobów można wybrać 20 monet?
Rozwiązanie
Rozwiązanie 1
Jeśli wybrano k monet 10-groszowych, to monety 20-groszowe można wybrać na 0, 1, 2, ..., 20-k sposobów.
Razem na 21-k sposobów. Ale ponieważ k zmienia się od 0 do 20, więc łącznie mamy 1 + 2 + 3 + ... + 21 = 231 sposobów wyboru.
Rozwiązanie 2
Wybieramy k elementów ze zbioru przedmiotów n rodzaju, przy czym dopuszczamy możliwość braku wyboru przedmiotu pewnego rodzaju.
Można tę sytuację przedstawić jako (k+n-1)-wyrazowy ciąg binarny, w którym (n-1) jedynek reprezentuje granicę między zbiorami poszczególnych przedmiotów danego rodzaju.
W naszym przypadku mamy 22-wyrazowy ciąg binarny, w którym trzy zbiory reprezentowane są przez 2 jedynki.
Np. ciąg 0000000000000000100010 oznacza, że wybrano 16 monet pierwszego rodzaju (10 gr), 3 monety drugiego rodzaju (20 gr) i 1 monetę trzeciego rodzaju (50 gr)
Problem sprowadza się do wyboru n-1 jedynek spośród k + n-1 elementów.
Zatem 20 monet spośród nieograniczonej liczby monet trzech rodzajów można wybrać na sposobów.
powrót do zbioru zadań | wersja do druku << poprzednie zadanie następne zadanie >>