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

Өлшемі $100\times 100$ ұяшықты тақта берілген. Кез келген $1\le a,b\le 100$ натурал сандары үшін нөмірі $a$ болатын қатар мен нөмірі $b$ болатын бағанның қиылысындағы ұяшықты $(a,b)$ арқылы белгілейік. $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)$$

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