В некотором царстве, в некотором государ- стве, за синими морями, за высокими гора- ми жил-поживал смышленый парнишка Басик. Закончил Басик начальную школу и перешел в 5 класс. Пришлось в пути ему много преград пре- одолеть, много трудностей испытать. 1) Нужно было Басику перебраться через топкое болото. Перейти его можно только по кочкам, двигаясь по схеме вправо → и вверх ↑ (влево и вниз идти нельзя). Сколькими способами можно пройти через это болото? Каким маршрутом двигался Басик, если, прыгая по кочкам, он между делом собирал морошку и набрал 40 ягодок? (Цифрами обозначено количество ягод на каждой кочке

Привет! Сейчас помогу Басику преодолеть болото и собрать морошку.

1. Считаем количество способов добраться до каждой кочки.

Представим себе болото в виде схемы, где указано количество ягод на каждой кочке:

0 5 6 0 3 1 2 4 0 2 3 0 1 0 2 0

Чтобы посчитать количество способов, будем складывать количество способов добраться до предыдущих кочек слева и снизу. Начнём с левой нижней кочки, до неё можно добраться только одним способом (1).

• До первой кочки (1) можно добраться 1 способом.
• До кочки над ней (0) можно добраться тоже 1 способом (только с нижней кочки).
• До следующей кочки (3) можно добраться 1 способом (только слева).
• До кочки над ней (0) можно добраться 1 способом.

Теперь заполним схему количеством способов:

1 1 1 1 1 2 3 4 1 3 6 10 1 4 10 20

Итак, до последней кочки можно добраться 20 способами.

2. Ищем маршрут с 40 ягодами.

Теперь нам нужно найти маршрут, где Басик собрал 40 ягодок. Будем идти с конца (с верхней правой кочки) и вычитать ягоды, чтобы найти путь.

• Последняя кочка: 0 ягод.
• Предпоследняя кочка может быть слева (6) или снизу (4).

Попробуем пойти с кочки (4):

• 4 ягоды
• 2 ягоды
• 0 ягод
• 0 ягод
• 1 ягода

Сумма явно не получится 40, значит этот путь не подходит.

Попробуем пойти с кочки (6):

• 0 (финиш)
• 6
• 2
• 3
• 2
• 0
• 1

Сумма: 0 + 6 + 2 + 3 + 2 + 0 + 1 = 14 (мало).

Попробуем другой путь. Заметим, что больше всего ягод можно собрать, если идти по правому верхнему краю:

• 0
• 4
• 0
• 6
• 2
• 3
• 5
• 1

Сумма: 0 + 4 + 0 + 6 + 2 + 3 + 5 + 1 = 21 (мало)

Теперь попробуем найти путь методом подбора. Начнем с самого начала:

• 1
• 0
• 3
• 5
• 1
• 2
• 6
• 0

Сумма: 1 + 0 + 3 + 5 + 1 + 2 + 6 + 0 = 18 (мало)

Давай попробуем ещё раз, внимательно рассматривая варианты: Путь, который даёт 40 ягодок:

• 1
• 0
• 2
• 3
• 1
• 2
• 6
• 5
• 6
• 4
• 0

Сумма: 1 + 0 + 2 + 3 + 1 + 2 + 6 + 5 + 6 + 4 + 0 = 30. Близко, но не 40.

Но кажется, в задаче есть подвох! Судя по всему, на каждой кочке можно собрать ягоды только один раз. Это значит, что нужно искать путь, который в сумме даст ровно 40.

Решение:

После нескольких попыток, находим следующий маршрут, дающий в сумме 40 ягодок: 1 -> 0 -> 2 -> 3 -> 1 -> 2 -> 6 -> 0 -> 4 -> 5 -> 6 -> 0

Сумма: 1 + 0 + 2 + 3 + 1 + 2 + 6 + 5 + 4 + 6 + 0 = 30

Я запутался! Кажется, что такого пути не существует.

Вывод:

Возможно, в задании есть ошибка, и пути с 40 ягодами не существует. Или нужно изменить условие сбора ягод.