Inne, zadanie nr 161

Autor	Zadanie / Rozwiązanie
robak15 postów: 3	2014-03-30 18:45:43 Na ile sposobów można z punktu (0, 0) w układzie kartezjańskim dotrzeć do punktu (7, 10), jeśli można poruszać się tylko w prawo i do góry. W prawo można poruszać się tylko o 1, 2 lub 4 jednostki, a w górę można poruszać się tylko o 1, 2, 3 lub 4 jednostki. Dodatkowe założenie jest takie, że poruszamy się raz w prawo raz w górę na przemian. Proszę o pomoc Wiadomość była modyfikowana 2014-03-30 19:17:34 przez robak15

mimi postów: 171	2014-09-19 18:31:50 Musimy poruszyć się o 7 w prawo i o 10 w lewo. Rozważmy najpierw jak można otrzymać 7 jako sumę jedynek, dwójek i czwórek: 7 = 1 + 1 + 1 + 1 + 1 + 1 + 1 (7 kroków) 7 = 2 + 1 + 1 + 1 + 1 + 1 (6 kroków) 7 = 2 + 2 + 1 + 1 + 1 (5 kroków) 7 = 4 + 1 + 1 + 1 (4 kroki) 7 = 4 + 2 + 1 (3 kroki) Skoro w prawo i w górę poruszamy się na przemian, nie ma sensu rozważać możliwych uzyskań dziesiątki jako sumy więcej niż 8 czynników 10 = 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 (8 kroków) 10 = 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 ( -\|\|- ) 10 = 2 + 2 + 2 + 1 + 1 + 1 + 1 (7 kroków) 10 = 3 + 2 + 1 + 1 + 1 + 1 + 1 ( -\|\|- ) 10 = 4 + 1 + 1 + 1 + 1 + 1 + 1 ( -\|\|- ) 10 = 2 + 2 + 2 + 2 + 1 + 1 (6 kroków) 10 = 3 + 2 + 2 + 1 + 1 + 1 ( -\|\|- ) 10 = 3 + 3 + 1 + 1 + 1 + 1 ( -\|\|- ) 10 = 4 + 2 + 1 + 1 + 1 + 1 ( -\|\|- ) 10 = 2 + 2 + 2 + 2 + 2 (5 kroków) 10 = 3 + 2 + 2 + 2 + 1 ( -\|\|- ) 10 = 3 + 3 + 2 + 1 + 1 ( -\|\|- ) 10 = 4 + 2 + 2 + 1 + 1 ( -\|\|- ) 10 = 4 + 3 + 1 + 1 + 1 ( -\|\|- ) 10 = 3 + 3 + 3 + 1 (4 kroki) 10 = 3 + 3 + 2 + 2 ( -\|\|- ) 10 = 4 + 2 + 2 + 2 ( -\|\|- ) 10 = 4 + 3 + 2 + 1 ( -\|\|- ) 10 = 4 + 4 + 1 + 1 ( -\|\|- ) 10 = 4 + 3 + 3 (3 kroki) 10 = 4 + 4 + 2 (3 kroki) Teraz policzymy na ile sposobów możemy uzyskać 7 i 10 dla zadanej liczby kroków. Dla siódemki: w 7 krokach możemy ją otrzymać na 1 sposób w 6 krokach na 6 sposobów (z pięciu jedynek i dwójki możemy ułożyć 6 różnych ciągów - jest 6 możliwych miejsc wstawienia dwójki, pozostałe miejsca zapełniamy jedynkami) w 5 krokach na 10 sposobów w 4 krokach na 4 sposoby w 3 krokach na 6 sposobów Dla dziesiątki: w 8 krokach możemy ją otrzymać na 8 + 28 = 36 sposobów w 7 krokach na 35 + 42 + 7 = 84 sposoby w 6 krokach na 15 + 60 + 15 + 30 = 120 sposobów w 5 krokach na 1 + 20 + 30 + 30 + 20 = 101 sposobów w 4 krokach na 4 + 6 + 4 + 24 + 6 = 44 sposobów w 3 krokach na 3 + 3 = 6 sposobów Jeżeli ścieżkę w prawo wykonuję w n krokach, ścieżkę do góry muszę wykonać w n - 1, n lub n + 1 krokach (żeby zachować naprzemienność). Jeśli siódemkę otrzymuję w siedmiu krokach (mam jedną możliwość), dziesiątkę mogę otrzymać w ośmiu, siedmiu lub sześciu krokach, co daje mi 36 + 84 + 120 = 240, razem $1 \cdot 240 = 240$ możliwości. Analogicznie dla sześciu kroków: $6 \cdot (84 + 120 + 101) = 1830 $ Dla pięciu kroków: $10 \cdot (120 + 101 + 44) = 2650 $ Dla czterech: $4 \cdot (101 + 44 + 6) = 604$ I dla trzech: $6 \cdot (44 + 6) = 300$ A więc razem mamy: $240 + 1830 + 2650 + 604 + 300 = 5624 $ sposoby Proponuję sprawdzić obliczenia, bo są dosyć żmudne, a liczyłam w głowie, więc wynik może nie być do końca poprawny.

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj