Математикадан 37-ші халықаралық олимпиада, 1996 жыл, Мумбаи

Қабырғалары $AB=20$, $BC=12$ болатын $ABCD$ тіктөртбұрышты тақтасы бірлік квадраттарға бөлінген. $r$ — берілген натурал сан болсын. Егер екі квадраттың центрлерінің қашықтығы $\sqrt{r}$ болса, онда сол екі квадраттың бірінен біріне монетаны қозғау жүріс болып табылады. Монетаны төбесі $A$ болатын квадраттан төбесі $B$ болатын квадратқа ауыстыру қажет.
а) $r$ саны 2--ге немесе 3--ке бөлінсе, онда монетаны ауыстыруға болмайтынын дәлелдеңдер.
б) $r=73$ болса монетаны ауыстыруға болатынын дәлелдеңдер.
в) $r=97$ болса, ауыстыруға бола ма?

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

Предположим, что перемещение составляет a единиц в одном направлении и b в ортогональном направлении. Итак, $а^2 + b^2 = r.$ Если r делится на 2, то a и b либо четные, либо оба нечетные. Но это означает, что мы можем получить доступ только к черным или белым квадратам (при условии, что прямоугольник раскрашен как шахматная доска). Два угла имеют противоположный цвет, поэтому задачу выполнить невозможно. Все квадраты конгруэнтны 0 или 1 по модулю 3, поэтому, если r делится на 3, то a и b должны быть кратны 3. Это означает, что если начальный квадрат имеет координаты (0,0), мы можем перейти только к квадраты вида (3m,3n). Требуемый пункт назначения — (19,0), который не имеет этой формы, поэтому задачу невозможно выполнить.

(б) Если r = 73, то должно быть a = 8, b = 3 (или наоборот). Существует 4 типа хода:

A: от (x,y) до (x+8,y+3)

B: от (x,y) до (x+3,y+8)

C: от (x,y) до (x+8,y-3)

D: от (x,y) до (x+3,y-8)

Мы рассматриваем ход от (x,y) до (x-8,y-3) как отрицательный ход типа А и так далее. Тогда если у нас есть ходы типа A, b типа B и так далее, то нам потребуется:

$8(a + c) + 3(b + d) = 19; 3(а - c) + 8(b - d) = 0.$

Простое решение — это a = 5, b = -1, c = -3, d = 2, поэтому начнем с поиска решений этого типа. После некоторых возни находим:

(0,0) до (8,3) до (16,6) до (8,9) до (11,1) до (19,4) до (11,7) до (19,10) до (16) ,2) до (8,5) до (16,8) до (19,0).

(c) Если r = 97, то мы должны иметь a = 9, b = 4. Как и раньше, предположим, что мы начинаем с (0,0). В результате многих попыток найти решение не удается, поэтому мы ищем причины, по которым оно невозможно. Вызов ходов, которые меняют y на 4 «переключательных» хода. Рассмотрим центральную полосу y = 4, 5, 6 или 7. Движения переключения должны включать и выключать нас из полосы. Движения без переключения нельзя делать, если мы находимся на полосе, и удерживать нас от нее, если мы находимся вне нее. Переключения с переключением также меняют четность координаты X, тогда как движения без переключения этого не делают. Теперь мы начинаем и заканчиваем за пределами полосы, поэтому нам нужно четное количество переключений. С другой стороны, мы начинаем с четного x и заканчиваем нечетным x, поэтому нам нужно нечетное количество переключений. Следовательно, задача невыполнима.