Задание 2 "Кузнечик"

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

2.1. Кузнечик может прыгать  на 3 и на 5 единиц длины  как впе-
ред, так и назад. Покажите, что он может попасть как в точку 1,
так и в точку -1.

2.2. Покажите, что в ситуации задачи 2.1 Кузнечик может попасть
в любую целую точку (то есть в точку числовой прямой, координа-
та которой - целое число).

2.3.  Что  можно сказать про путешествия Кузнечика (см.  пункты
2.1 и 2.2), если у него прыжки длиной (а) 4 и 6; (б) 5 и 7; (в)
6 и 9. Докажите свои утверждения.

   Далее Кузнечик начинает свое путешествие из точки 0, но пры-
гает по числовой прямой только вперед  (в положительном направ-
лении). Точки, в которые он может  попасть, называются достижи-
мыми, остальные  -  недостижимыми.  Начальная точка 0 считается
достижимой. Все отрицательные целые точки оказываются  недости-
жимыми.

2.4. Кузнечик может прыгать вперед  на  3 и на 5 единиц  длины.
Отметьте все достижимые точки. Докажите, что все точки, начиная
с 8, оказываются достижимыми.

Замечание. Пометим достижимую точку буквой A,  а недостижимую -
буквой B. Вот как раположатся пометки вблизи точки 0:
                         ...BBBABBA...
Первая слева  буква A отмечает точку  старта (точку 0).  До нее
слева буквы  B отмечают недостижимые отрицательные точки. Нужно
продолжить пометки  вправо, интересно, как там расположены бук-
вы.

2.5. Кузнечик может прыгать вперед  на  5 и на 7 единиц  длины.
Отметьте все достижимые точки (приведите слово из букв  A и B).
Начиная с какой достижимой точки все следующие за ней также бу-
дут достижимые?

2.6. Кузнечик может прыгать вперед  на  a и на b единиц  длины,
где a и b - взаимно простые числа (их наибольший общий делитель
равен 1). Докажите, что есть замечательная  точка, которая дос-
тижимая и все следующие за ней тоже достижимые. Найдите формулу
замечательной точки (зависимость ее координаты от a и b).

   Как устроены множества достижимых и недостижимых точек?

2.7. Проверьте в случаях 2.4 и 2.5, что  множества достижимых и
недостижимых точек симметричны друг другу относительно  некото-
рой точки. Докажите это утверждение в общем случае 2.6.

2.8. Опираясь на  результат 2.7, подсчитайте в случае 2.6 коли-
чество положительных недостижимых точек.

2.9. Кузнечик может прыгать вперед  на  a, b и c единиц  длины,
где a, b и c  -  попарно взаимно простые числа. Исследуйте  эту
ситуацию, сформулируйте  свои гипотезы и расскажите о результа-
тах.

   Не обязательно отвечать на все вопросы. Выберите то, что Вам
интересно и доступно. Это одни вопросы для младших (6-7 классы)
и другие для старших (10-11 классы, студенты младших курсов).

                           О задачах

   Прежде всего отметим,  что для того, чтобы решать задачи, не
требуются никакие книжки, нужно только желание.
   Кузнечик -  исполнитель  из  учебника  "Алгоритмика" для 5-7
классов. Обобщения пунктов  2.1  - 2.3 затрагивают алгоритм Ев-
клида. В Заочной Математической Школе при МГУ (позднее ОЛ ВЗМШ)
было  очень  хорошее  задание  "Целые  числа"  Н.Б.Васильева  и
В.Л.Гутенмахера, в нем  есть  решение уравнений ax+by=c в целых
числах (a,b и c - целые), причем и с геометрической  точки зре-
ния. Задача 2.4 (в формулировке с  трехкопеечными и пятикопееч-
ными монетами) - стандартный пример на метод математической ин-
дукции: "Если первая в очереди женщина  и  за  каждой  женщиной
стоит женщина, то  все в очереди женщины". Задачу об устройстве
множества достижимых точек  в  общем случае (прыжки длиной a_1,
..., a_n) недавно (примерно год назад)  упомянул В.И.Арнольд. С
помощью вычислительного эксперимента можно исследовать, с какой
частотой встречаются достижимые точки на различных участках от-
резка [0,L], где L - замечательная точка.

(С) С.И.Соболев, 1999-2002