Задача 4.
Кузнечик прыгает по числовой прямой вправо на 2 или на 3. Ему запрещено попадать на простые числа. Сколькими способами он может попасть с 1 на 36?
Комментарий: Простое число — это натуральное число больше 1, у которого есть всего два делителя: единица и само число.
Ответ на Задачу 4.
Ответ: 48 способов.
Решение:
Есть пять «обязательных» чисел: 4, 6, 12, 18, 30 — и четыре неоднозначных участка: 6 − 12, 12 − 18, 18 − 30 и 30 − 36. Каждый участок, кроме 18 − 30, проходится двум способами (3 прыжка по 2 или 2 прыжка по 3). Длинный участок 18 − 30 хочется разбить на 2 коротких. У нас нет числа в промежутке, на которое кузнечик обязательно наступит. Однако, перепрыгнув через простое число 23, кузнечик наступит либо на 24, либо на 25. На оба числа в одном способе он наступить не может, поэтому либо будет пара участков 18 − 24, 24 − 30, либо пара 18 − 25, 25 − 30. Каждый из участков 18 − 24 и 24 − 30 проходится двумя способами, 18 − 25 единственным способом 18 − 20 − 22 − 25, а 25 − 30 двумя способами (25 − 27 − 30 и 25 − 28 − 30). Поэтому участок 18 − 30 проходится 2 ⋅ 2 + 1 ⋅ 2 = 6 способами, а весь маршрут — 2 ⋅ 2 ⋅ 6 ⋅ 2 = 48 способов.
