Кузнечик

Кузнечик прыгает по целым точкам числовой прямой и всегда начинает свое путешествие из точки 0.

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.