Задание №208
Условие
У Пети есть клетчатая доска размером 9\times9. Соседними считаются клетки, границы которых имеют общий отрезок. Начальной клеткой будем считать клетку, расположенную в левом нижнем углу доски. В левом нижнем углу доски стоит фигура «Кентавр». «Кентавр» ходит по клеткам доски ходом (k;m), то есть сначала перемещается на k клеток по горизонтали или вертикали, а затем на m клеток в перпендикулярном направлении. Числа k и m — целые неотрицательные.
а) Может ли «Кентавр» через несколько ходов оказаться в клетке, соседней с начальной, если k=1, m=2?
б) Может ли «Кентавр» через несколько ходов оказаться в клетке, соседней с начальной, если k=1, m=3?
в) При каком наибольшем k «Кентавр» через несколько ходов может оказаться в клетке, соседней с начальной, если m=8?
Решение
а) Введем на клетках систему координат.
Изначально «Кентавр» стоит в клетке (1;1). Тогда последовательность ходов (1;1) \rightarrow (2;3)\rightarrow (4;2)\rightarrow (2;1) приведет его в клетку (2;1), соседнюю с начальной.
По сути ход «Кентавра» совпадает с ходом обычного шахматного коня.
б) Не может. Если «Кентавр» стоит в клетке (i; j), то после хода он окажется в одной из клеток (i\pm 1; j\pm 3) или (i\pm 3; j\pm 1). Таким образом, сумма координат станет равной одному из чисел i+j-4, i+j-2, i+j+2,i+j+4, то есть изменится на четное число по сравнению с значением i+j. Значит, четность суммы координат клетки, на которой стоит «Кентавр», остается неизменной. Сначала «Кентавр» стоит на клетке (1;1). Следовательно, сумма координат занимаемой клетки всегда будет четной, в то время как соседние с начальной клетки (1;2) и (2;1) имеют нечетную сумму координат.
в) Очевидно, что k\leqslant8, иначе «Кентавр» первым же ходом выскочит за доску. Ясно, что для четных k требуемое невозможно, так как в этом случае «Кентавр» всегда будет оказываться в клетках с черной суммой координат и никогда не сможет попасть ни в клетку (1;2), ни в клетку (2;1). Кроме того, при k>4 после первого хода «Кентавр» окажется либо в клетке (9; k+1), либо в клетке (k+1;9) и следующим ходом вынужден будет вернуться в клетку (1;1), так как 2k+1>9 и, следовательно у него не будет выбора. Тогда все клетки, на которых может побывать «Кентавр», исчерпываются клетками (1;1), (k+1;9) и (9; k+1), то есть в соседней с начальной клетке «Кентавр» никогда не окажется.
Предположим, что k=3. Тогда после первого хода «Кентавр» окажется в клетке (9;4) или (4;9). Будем считать, что он окажется в клетке (9;4), так как второй случай полностью симметричен. Из клетки (9;4) вторым ходом он может либо вернутся в начальную, либо перейти в клетку (1;7), из которой следующим ходом можно лишь вернуться в клетку (9;4). Значит при k=3 «Кентавру» доступны только клетки (1;1), (9;4), (1;7), (4;9), (7;1), и этот случай не подходит.
Наконец при k=1 требуемое возможно, что доказывается примером последовательности шагов, приводящих «Кентавра» в соседнюю клетку (1;1)\;\rightarrow\; (2;9)\;\rightarrow\; (3;1)\;\rightarrow\; (4;9)\;\rightarrow\; (5;1)\;\rightarrow\; (6;9)\;\rightarrow\; (7;1)\;\rightarrow\; (8;9)\;\rightarrow\; (9;1)\;\rightarrow\; (1;2)
Ответ
а) да; б) нет; в) 1.