1. Кузнечик может прыгать на 3 и на 5 единиц длины как вперед, так и назад. Покажите, что он может попасть как в точку 1, так и в точку −1.
2. Покажите, что в ситуации задачи 1 Кузнечик может попасть в любую целую точку (то есть в точку числовой прямой, координата которой — целое число).
3. Что можно сказать про путешествия Кузнечика (см. задачи 1 и 2), если у него прыжки длиной: а) 4 и 6; б) 5 и 7; в) 6 и 9? Докажите свои утверждения.
Далее Кузнечик начинает свое путешествие из точки 0, но прыгает по числовой прямой только вперед (в положительном направлении). Точки, в которые он может попасть, называются достижимыми, а остальные — недостижимыми. Начальная точка 0 считается достижимой. Все отрицательные целые точки оказываются недостижимыми.
4. Кузнечик может прыгать вперед на 3 и на 5 единиц длины. Отметьте все достижимые точки. Докажите, что все точки, начиная с 8, оказываются достижимыми.
Пометим достижимую точку буквой A, а недостижимую — буквой B. Вот как расположатся пометки вблизи точки 0:
...BBBABBA...
Первая слева буква A отмечает точку старта (точку 0). До нее слева буквы B отмечают недостижимые отрицательные точки. Нужно продолжить пометки вправо. Интересно, как там расположены буквы?
5. Кузнечик может прыгать вперед на 5 и на 7 единиц длины. Отметьте все достижимые точки (приведите слово из букв A и B). Начиная с какой достижимой точки все следующие за ней также будут достижимые?
6. Кузнечик может прыгать вперед на a и на b единиц длины, где a и b — взаимно простые числа (их наибольший общий делитель равен 1). Докажите, что есть замечательная точка, которая достижимая, стоит после недостижимой, а все следующие за ней точки тоже достижимые. Найдите формулу замечательной точки (зависимость ее координаты от a и b).
Интересно, как устроены множества достижимых и недостижимых точек?
7. Проверьте в случаях 4 и 5, что множества достижимых и недостижимых точек симметричны друг другу относительно некоторой точки. Докажите это утверждение в общем случае 6.
8. Опираясь на результат 7, подсчитайте в случае 6 количество положительных недостижимых точек.
О задачах. Кузнечик — исполнитель из учебника "Алгоритмика" для 5-7 классов. Близкая тема: алгоритм Евклида. Задача 4 в формулировке с трехкопеечными и пятикопеечными монетами — часто используемый пример на метод математической индукции: "Если первая в очереди женщина и за каждой женщиной стоит женщина, то все в очереди женщины".
Alpha (10-12 лет): задачи 1, 2, 3 и какое-то продвижение в задачах 4 и 5.
Beta (13-14 лет): задачи 4 и 5 и продвижения в задачах 6-8.
