Question

Кенгуру прыгает только вперёд на 3 или на 5 метров. Он хочет преодолеть ровно 21 метр. Сколькими способами он может это сделать?Нашёл 10 комбинаций (типа 5+3+5+3+5)И вариант с семью тройкамиОтветы: 9, 15, 16, 8

Answer 1

Есть 4 варианта представления числа 10 в виде суммы троек или единиц:
10=1+1+1+1+1+1+1+1+1+1=1+1+1+1+1+1+1+3=1+1+1+1+3+3=1+3+3+3
Первое разбиение предлагает всего один способ преодоления расстояния в 10 метров.
Во втором разбиении единственная тройка может быть одним из восьми слагаемых, что даёт 8 вариантов.
Из третьего разбиения можно получить  вариантов расположения прыжков в 3 метра.
В третьем разбиении единственная единица может быть одним из четырёх слагаемых, что даёт ещё 4 варианта.
Всего 1+8+15+4=28 вариантов.

Answer 2

3+3+3+3+3+3+3=21

5+5+5+3+3=21

 

Answer 3

Чтобы рассмотреть все возможные варианты, можно использовать динамическое программирование. Давайте обозначим F(n) как количество способов, которыми кенгуру может преодолеть n метров. Тогда:

- F(0) = 1 (если кенгуру не нужно прыгать, то есть уже на месте, это один способ). - F(1) = 0 (кенгуру не может преодолеть 1 метр одним прыжком). - F(2) = 0 (кенгуру не может преодолеть 2 метра одним прыжком). - F(3) = 1 (кенгуру может преодолеть 3 метра одним прыжком). - F(4) = 0 (кенгуру не может преодолеть 4 метра одним прыжком). - F(5) = 1 (кенгуру может преодолеть 5 метров одним прыжком).

Теперь рекуррентное соотношение:

\[ F(n) = F(n-3) + F(n-5) \]

Посчитаем значения:

\[ F(6) = F(3) + F(1) = 1 + 0 = 1 \]

\[ F(7) = F(4) + F(2) = 0 + 0 = 0 \]

\[ F(8) = F(5) + F(3) = 1 + 1 = 2 \]

\[ F(9) = F(6) + F(4) = 1 + 0 = 1 \]

\[ F(10) = F(7) + F(5) = 0 + 1 = 1 \]

\[ F(11) = F(8) + F(6) = 2 + 1 = 3 \]

\[ F(12) = F(9) + F(7) = 1 + 0 = 1 \]

\[ F(13) = F(10) + F(8) = 1 + 2 = 3 \]

\[ F(14) = F(11) + F(9) = 3 + 1 = 4 \]

\[ F(15) = F(12) + F(10) = 1 + 1 = 2 \]

\[ F(16) = F(13) + F(11) = 3 + 3 = 6 \]

\[ F(17) = F(14) + F(12) = 4 + 1 = 5 \]

\[ F(18) = F(15) + F(13) = 2 + 3 = 5 \]

\[ F(19) = F(16) + F(14) = 6 + 4 = 10 \]

\[ F(20) = F(17) + F(15) = 5 + 2 = 7 \]

\[ F(21) = F(18) + F(16) = 5 + 6 = 11 \]

Таким образом, кенгуру может преодолеть 21 метр 11 различными способами. Это соответствует одному из ваших ответов.