Азиатско-Тихоокеанская математическая олимпиада, 2024 год

Рассмотрим клетчатую таблицу $100\times 100$ и определим клетку упорядоченной парой $(a,b)$, если она находится на пересечении строки с номером $a$ и столбца с номером $b$, здесь $1\le a,b\le 100$ — натуральные числа. Пусть $k$ — целое число такое, что $51\le k\le 99$. Конём $k$-го порядка назовём фигуру, которая ходит на одну клетку вертикально или горизонтально, а затем на $k$ клеток в другом направлении; то есть, она ходит из клетки ${(a,b)}$ в ${(c,d)}$ так, что $({|a-c|},{|b-d|})={(1,k)}$, либо $({|a-c|},{|b-d|})= {(k,1)}$. Конь $k$-го порядка начинает движение из клетки ${(1,1)}$ и совершает несколько ходов. Последовательность ходов — это последовательность клеток ${(x_0,y_0)}={(1,1)}$, ${(x_1,y_1)}$, ${(x_2,y_2)}$, $\ldots$, ${(x_n,y_n)}$ таких, что для всех $i=1,2,\ldots,n$, $1\le x_i,y_i\le 100$, конь $k$-го порядка может перейти из ${(x_{i-1},y_{i-1})}$ в ${(x_i,y_i)}$. В этом случае каждая клетка ${(x_i,y_i)}$ называется достижимой. Для каждого $k$ найдите количество $L(k)$ достижимых клеток.

Комментарий/решение

Ответ: $L(k)=\left\{\begin{gathered} \dfrac{100^2-(2k-100)^2}{2},~2\nmid k\\ 100^2-(2k-100)^2,~2\mid k \end{gathered}\right.$

Отметим что любой ход обратимый. Также отметим что если $101-k \leq x,~y \leq k$, то из $(x,y)$ нельзя будет выбраться, а значит и войти в него тоже нельзя. Таких назовем изолированными.

Предположим что $(x,y)$ достижимо. Тогда хотя бы один из $(x,y)$ не лежит в $[101-k,k]$.

Б.О.О, $x\notin [101-k,k]$. Тогда из $(x,y)\leftrightarrow (x\pm k,y \pm 1)\leftrightarrow (x,y \pm 2)$ достижимо, учитывая что координаты не выходят из $[1,100]$.

Покажем что если $k$ четное, то $(x,y)$ достижимо для $\forall y$.

Достаточно показать что $(1,2),~(2,1),~(2,2)$ достижимы:

$$(1,1)\leftrightarrow(2,k+1)\leftrightarrow\dots\leftrightarrow(2,1)$$

$$(1,1)\leftrightarrow(k+1,2)\leftrightarrow\dots\leftrightarrow(1,2)$$

$$(1,1)\leftrightarrow\dots\leftrightarrow(2,1)\leftrightarrow(k+2,2)\leftrightarrow\dots\leftrightarrow(2,2)$$

Аналогично $(x,y)$ достижимо при $\forall y\in[101-k,k]$. Отсюда все клетки достижимы кроме изолированных, образующие квадрат длины $2k-100$ в центре.

Пусть $k$ нечетное. Покрасив доску в шахматную раскраску очевидно что конь ходит по клеткам одного цвета с $(1,1)$. Докажем что все неизолированные $(x,y)$ одного цвета с $(1,1)$ достижимы. Это очевидно для $k=99$.

Достаточно показать что $(2,2)$ достижимо для $k<99$:

$$(1,1)\leftrightarrow(2,k+1)\leftrightarrow\dots\leftrightarrow(2,2)$$

Отуда половина неизолированных клеток достижимы.