Азиатско-Тихоокеанская математическая олимпиада, 2009 год

Ларри и Роб — два робота, которые едут в одном автомобиле из Арговы в Зилис. Роботы управляют автомобилем по следующему алгоритму: Ларри поворачивает влево на $90^\circ$ каждые $\ell$ километров, начиная от старта; а Роб поворачивает вправо на $90^\circ $ каждые $r$ километров, начиная от старта, причем $\ell$ и $r$ — взаимно простые натуральные числа. В случае, когда оба робота должны одновременно повернуть машину — автомобиль двигается без изменения направления. Предполагается, что поверхность плоская и неограниченная.
Пусть автомобиль стартует из Арговы в направлении к Зилис. При каких парах $(\ell, r )$ автомобиль гарантированно доедет до Зилиса, независимо от расстояния между этими городами?

Комментарий/решение

Чтобы автомобиль гарантированно доехал для зилиса необходимо чтобы за период НОК оба робота не поворачивали одновременно а это происходит когда НОК (L,r) является кратным 4 так как за один полный цикл в виде 4 поворотов по 90 градусов автомобиль вернется в исходное направление

Поскольку L,r взаимно простые числа

HOK(L,r)=L*r следовательно необходимо что бы произведение L и r было кратно 4

L*r=0 (mod 4) а это возможно если хотя бы одно из чисел является четным

Ответ:чтобы авто гарантированно доехало до зилиса надо чтобы хотя бы одно число из пары чисел (L,r) было четным