M1571. О доске, монете и возможных передвижениях

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

Условие

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

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

dim11.svg

Решение

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

Задание №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)
dim32.svg

Задание №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}. Поэтому требуемое невозможно.

Д. Терешин

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *