37-я Международная Математическая OлимпиадаИндия, Мумбаи, 1996 год

Прямоугольная доска $ABCD$ со сторонами $AB=20$, $BC=12$ разбита на единичные квадраты. Пусть $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, поэтому нам нужно нечетное количество переключений. Следовательно, задача невыполнима.