Октябрь 2006, 9 задач
Кузнечик прыгает по целым точкам числовой прямой. Он начинает из точки 0 и прыгает только вперед (в положительном направлении). Точки, в которые он может попасть, назовем достижимыми, а остальные - недостижимыми. Начальная точка 0 считается достижимой, все отрицательные целые точки оказываются недостижимыми.
1. Кузнечик может прыгать вперед на 3 и на 5 единиц длины. Отметьте все достижимые точки. Докажите, что все точки, начиная с 8, оказываются достижимыми.
Отметим достижимую точку буквой A, а недостижимую - буквой B. Вот как расположатся пометки вблизи точки 0:
...BBBABBA...
Первая слева буква A отмечает точку старта (точку 0). До нее слева буквы B отмечают недостижимые отрицательные точки. Нужно продолжить пометки вправо. Интересно, как там расположены буквы?2. Кузнечик может прыгать вперед на 5 и на 7 единиц длины. Отметьте все достижимые точки (приведите слово из букв A и B). Начиная с какой достижимой точки все следующие за ней также будут достижимые?
3. Кузнечик может прыгать вперед на a и на b единиц длины, где a и b - взаимно простые числа. Докажите, что есть замечательная точка, которая достижимая, стоит после недостижимой, а все следующие за ней тоже достижимые. Найдите формулу замечательной точки (зависимость ее координаты от a и b).
4. Проверьте на примерах, что множества достижимых и недостижимых точек симметричны друг другу относительно некоторой точки, и докажите это утверждение в общем случае.
5. Подсчитайте количество положительных недостижимых точек.
