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

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

Условие

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

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

dim11.svg

Решение

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

Задание №1

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

Задание №2

Один из примеров продвижения монеты из [latex](0;0)[/latex] в [latex](19;0)[/latex] при [latex]r=73[/latex] такой: [latex](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)[/latex]
dim32.svg

Задание №3

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

Д. Терешин

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

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