Азия-тынық мұхит математикалық олимпиадасы, 2009 жыл

Екі робот — Ларри және Роб — бір автомобильде Арговадан Зилисқа кетіп барады. Олар автомобильді келесі алгоритм бойынша жүргізеді: Ларри автомобильді старттан кейінгі әрбір $l$ км-ден кейін $90{}^\circ $-қа солға бұрып отырады, ал Роб — старттан кейін әрбір $r$ км.-ден кейін $90{}^\circ $-қа оңға бұрып отырады. Мұндағы $l$ және $r$ — өзара жай натурал сандар. Екі робот та бір мезгілде бұру керек болғанда, автомобиль бағытын өзгертпейді. Жер беті шексіз жазықтық деп есептелсін. Автомобиль Арговадан шығып Зилиске бағыт алды. Қандай ${(l, r)}$ жұптары үшін екі қаланың ара қашықтығы қандай болғанына қарамастан автомобиль Зилис қаласына міндетті түрде жетеді?

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

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

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

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

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

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