Задача из журнала «Квант» (1996, №6)

Условие

Дана прямоугольная доска $ABCD$ со сторонами $AB=20$ и $BC=12$, разбитая на $20\times12$ единичных квадратов. Пусть $r$ — данное положительное целое число. За один ход монету можно передвинуть из одного единичного квадрата в другой в том и только том случае, когда расстояние между их центрами равно $\sqrt{r}$. Требуется найти последовательность ходов, переводящую монету из единичного квадрата с вершиной $A$ в единичный квадрат с вершиной $B$.

1. Докажите, что это невозможно, когда $r$ делится на $2$ или на $3$.
2. Докажите, что это можно сделать при $r=73$.
3. Можно ли это сделать при $r=97$?

Решение

Введем прямоугольную систему координат с началом в точке $A$ и направим оси $Ax$ и $Ay$ вдоль отрезков $AB$ и $AD$ соответственно. Единица длины будет равна стороне единичного квадрата. Нам необходимо найти путь из точки $(0;0)$ в точку $(19;0)$ такой, что для каждого хода $(x;y)\rightarrow(x+a,y+b)$ выполняется равенство $a^2+b^2=r^2$.

Задание №1

Если $r$ чётно, то для каждого целого решения уравнения $a^2+b^2=r^2$ сумма $a+b$ чётна. Для каждой точки $(x;y)$, в которую можно попасть из $(0;0)$, $x+y$ чётно. Следовательно, в точку $(19;0)$ попасть невозможно.

Задание №2

Один из примеров продвижения монеты из $(0;0)$ в $(19;0)$ при $r=73$ такой: $(0;0)\rightarrow(3;8)\rightarrow(11;5)\rightarrow(19;2)\rightarrow(16;10)\rightarrow(8;7)\rightarrow(0;4)\rightarrow(8;1)\rightarrow(11;9)\rightarrow(3;6)\rightarrow(11;3)\rightarrow(19;0)$

Задание №3

Пусть $R=\left\{(i;j);0\leq{i}\leq19,0\leq{j}\leq19\right\}$, $P=\left\{(i;j);0\leq{i}\leq49,4\leq{j}\leq7\right\}$, $Q$ — их разность: $Q=R\setminus{P}$. Так как число $97$ представимо в виде суммы квадратом единственным образом: $9^2+4^2$, то каждый ход состоит из одного из векторов $(\pm4;\pm9)$, $(\pm9;\pm4)$. Ход типа $(\pm9;\pm4)$ приводит нас в точку $Q$ из точки из множества $P$ и наоборот, тогда как ход $(\pm4;\pm9)$ не выводит нас из множества $Q$ (заметим, что за один шаг нашими ходами нельзя попасть из точки из $P$ в точку из $P$). Каждый ход типа $(\pm9;\pm4)$ изменяет чётность $x$-координаты, поэтому, чтобы попасть из $(0;0)$ в $(19;0)$, требуется нечётное число таких ходов. Каждый такой ход от точки из $P$ в точку из $Q$ и наоборот. Значит после нечётного числа ходов из точки $(0;0)\in{Q}$ попадаем в точку из $P$, но $(19;0)\in{Q}$. Поэтому требуемое невозможно.

Д. Терешин