|
|
 |
Условие
На шахматной доске N×N стоят N² шашек. Можно ли их переставить так, чтобы любые две шашки, отстоявшие на ход коня, после перестановки отстояли друг от друга лишь на ход короля (то есть стояли рядом)? Рассмотрите два случая:
а) N = 3;
б) N = 8.
Решение
а) Требуемая перестановка изображена на рисунке.
б) Введём два "расстояния" между клетками доски: d1(a, b) – наименьшее число ходов коня, необходимых для перехода из клетки a в клетку b, d2(a, b) – аналогичное число для ходов короля. Обозначим через a' и b' клетки, на которые попадают шашки из клеток a и b после перестановки. Тогда рассматриваемое в задаче условие, очевидно, влечёт неравенство d1(a, b) ≥ d2(a', b'). Докажем, что это невозможно.
Первый способ. Если a' и b' – противоположные угловые клетки, то d2(a', b') = 7, но для любых двух клеток a и b d1(a, b) ≤ 6. Чтобы в этом убедиться, достаточно проверить, что за три хода из любой клетки доски можно попасть в любую центральную клетку противоположного цвета, а за два хода – в одну из центральных клеток того же цвета).
Второй способ. Количество клеток, отстояших от центральной клетки a на расстояние d1 = 2, как нетрудно проверить, равно 25. Но от клетки a' на расстояние d2 ≤ 2 отстоят не более 24 клеток.
Ответ
а) Можно; б) нельзя.
Замечания
1. Баллы: 2 + 12.
2. Более сложный случай N = 4 разобран в решении задачи М863 из Задачника "Кванта".
