В каждой клетке доски $n\times n$ стоит по фишке. Можно ли переставить их так, чтобы любые две фишки, угрожавшие друг другу ходом коня, после перестановки стали угрожать друг другу ходом короля, если
а) Ответ: можно. Требуемая перестановка изображена на рисунке 1.
Рис. 1
б) Ответ: нельзя. Для доказательства введём два «расстояния» между клетками доски: $d_1(a,b)$ — наименьшее число ходов коня, необходимых для перехода из клетки $a$ в клетку $b$, $d_2(a,b)$ — аналогичное число для ходов короля. Обозначим через $a'$ и $b'$ клетки, на которые попадают фишки из клеток $a$ и $b$ после перестановки. Тогда рассматриваемое в задаче условие, очевидно, влечёт неравенство $d_1(a, b)\ge d_2(a',b')$. Если $a'$ и $b'$ — противоположные угловые клетки, то (при $n=6$) $d_2(a',b')=5$, но для любых двух клеток $a$ и $b$ $d_1(a,b)\le4$. В этом можно убедиться непосредственно, причём достаточно рассмотреть случай, когда $a$ — угловая клетка (например, $d_1$-расстояние между голубыми клетками на рисунке 2 заведомо не превосходит $d_1$-расстояния между розовыми клетками; цифры на этом рисунке равны $d_1$-расстояниям от соответствующих клеток до левой нижней).
Рис. 2
Точно так же рассматривается случай любого $n\gt6$: можно показать, что наибольшее значение $d_1(a,b)$ для доски $n\times n$ равно $\left[\dfrac{2(n+1)}3\right]$ (при $n\ge5$), т. е. $M$ меньше, чем $n-1-d_2$-расстояние между противоположными углами.
Рис. 3
в) Ответ: нельзя. Пусть $a_1$, $a_2$, $a_3$, $a_4$ — поля, на которых стояли фишки, попавшие после перестановки в углы доски. Тогда $d_1(a_i,a_j)\ge3$ при $1\le i\lt j\le4$ (см. пункт б)). На рисунке 3 для трёх существенно различных положений (с учетом симметрий) клетки $a_1$ отмечены клетки, расположенные на $d_1$-расстоянии 3, 4 или 5 от $a_1$. Пользуясь этим рисунком, нетрудно проверить прямым перебором, что ни в одном из случаев нельзя подыскать клетки $a_2$, $a_3$, $a_4$ с соблюдением условия $d_1(a_i,a_j)\ge3$.
Аналогично доказывается, что и при $n=5$ требуемой перестановки не существует.
