Как известно, шахматный конь ходит буквой «г». представим себе поле 2 × 2020 клеток. не перемещаясь за границы нашей импровизированной доски, конь может попасть в некоторые клетки. но не во все. какое минимальное количество клеток нужно добавить к доске, чтобы конь мог попасть в любую её клетку? добавление происходит, когда у добавляемой клетки есть общая грань с доской. форма доски не обязательно должна остаться прямоугольной.

Минимальное количество клеток, которое необходимо добавить к доске $2\times 2020$, чтобы шахматный конь мог попасть из любой её клетки в любую другую, равно 2. Анализ связности доски $2\times N$ На стандартной доске $2\times N$ движения коня сильно ограничены. Поскольку ширина доски всего 2 клетки, конь не может совершить прыжок, меняющий координату по горизонтали на 1, так как для этого ему пришлось бы изменить координату по вертикали на 2, выходя за границы (или наоборот). Единственный возможный ход для коня на такой узкой доске:

• Сдвиг на $1$ клетку по вертикали (из ряда 1 в ряд 2 или наоборот). Сдвиг на $2$ клетки по горизонтали.

Если обозначить клетку как $(x,y)$, где $x\in \{1,2\}$ — номер строки, а $y\in \{1,\dots ,2020\}$ — номер столбца, то из клетки $(1,y)$ конь может попасть только в $(2,y\pm 2)$, а из $(2,y)$ — только в $(1,y\pm 2)$. В результате вся доска распадается на 4 изолированные группы (компоненты связности), между которыми конь не может перемещаться:

1. Группа A: $\left\{\right(1,1),(2,3),(1,5),(2,7),\dots \}$ — клетки, где $(x+y)$ при делении на 4 дает остаток 2 или 1. Группа B: $\left\{\right(2,1),(1,3),(2,5),(1,7),\dots \}$ Группа C: $\left\{\right(1,2),(2,4),(1,6),(2,8),\dots \}$ Группа D: $\left\{\right(2,2),(1,4),(2,6),(1,8),\dots \}$

Обоснование минимального количества добавок Чтобы сделать доску полностью связной, нам нужно объединить эти 4 графа в один.

1. Недостаточность 1 клетки:
   Любая добавленная клетка вне основного поля (например, в 3-м ряду) имеет свои координаты $(x^{\prime },y^{\prime })$. Конь, стоящий в этой клетке, может атаковать только клетки с определенной четностью суммы координат. Как было показано в анализе, добавление одной клетки $(3,k)$ позволит ей связаться с клетками $(1,k-1),(1,k+1),(2,k-2),(2,k+2)$. Все эти клетки имеют одинаковую четность суммы координат $x+y$. Однако наши 4 компоненты в совокупности содержат клетки обеих четностей. Таким образом, одна клетка физически не может "дотянуться" до всех четырех групп одновременно так, чтобы связать их. Достаточность 2 клеток:
   Рассмотрим добавление двух клеток: $(3,3)$ и $(3,4)$.
   • Клетка $(3,3)$ может соединиться с клетками доски: $(1,2),(1,4),(2,1),(2,5)$. Это связывает между собой компоненты B, C и D. Клетка $(3,4)$ может соединиться с клетками доски: $(1,3),(1,5),(2,2),(2,6)$. Это связывает между собой компоненты A, B и D. Поскольку обе добавленные клетки связываются с общими компонентами (например, B и D), все четыре группы (A, B, C, D) становятся соединенными в единую сеть через эти две "транзитные" клетки.

Ответ Минимальное количество клеток, которые нужно добавить — 2. Хотите ли вы рассмотреть, как изменится решение, если форма доски должна обязательно остаться прямоугольной?