Задача 14
Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b), где a, b – целые числа. Эта команда перемещает Чертёжника из точки с координатами (x,y) в точку с координатами (x + a, y + b).
Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, −3) переместит Чертёжника в точку (6, −1).
Цикл
НАЧАЛО
ПОВТОРИ число РАЗ
последовательность команд
КОНЕЦ ПОВТОРИ
означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным).
Чертёжнику был дан для исполнения следующий алгоритм (число повторений и величины смещения в первой из повторяемых команд неизвестны):
НАЧАЛО
сместиться на (4, 6)
ПОВТОРИ … РАЗ
сместиться на (…, …)
сместиться на (4, -6)
КОНЕЦ ПОВТОРИ
сместиться на (-28, -22)
КОНЕЦ
В результате выполнения этого алгоритма Чертёжник возвращается в исходную точку. Какое наибольшее число повторений могло быть указано в конструкции «ПОВТОРИ … РАЗ»?
1. Запишем команду "ПОВТОРИ … РАЗ" в следующем виде: "ПОВТОРИ N РАЗ".
2. Команду "сместиться на (…, …)" запишем как "сместиться на (a, b)".
3. Запишем общее изменение координат Чертёжника в результате выполнения этого алгоритма:
4. Поскольку Чертёжник должен вернуться в исходную точку, то изменение координа должны быть равны нулю; следовательно, нужно найти набольшее натуральное n, при котором система уравнений
разрешима в целых числах относительно a и b.
5. Очевидно, что для этого число N должно быть одновременно делителем чисел 24 и 16.
6. Наибольший общий делитель чисел 24 и 16 равен 8.
Ответ: 8
