22. Вся королевская конница

В задаче о ферзях мы легко определили максимальное число фигур, которые можно поставить на доску, чтобы они не били друг друга, — для этого достаточно было пересчитать число горизонталей. ШахматНЫй конь ходит хитрее чем ферзь, — он перемещается или на 2 поля по вертикале и одно по горизонталИ, или па 2 поля по горизонтали и одНО по вертикали. Поэтому сразу сказать, чему равно наибольшее число коней, которых можно поставить на ШАхматНУю доску, чтобы они не били друг друга, сложнее. Впрочем, нетрудно найти нижНЮю оценку для этого Числа. Ведь при ходе коня каждый раз меняется цвет занятого им поля. Поэтому кони, поставленные на черные поля, бьют только белые поля, а друг друга бить не могут. Так как на доске 32 чЕРНЫх поля, то можно Поставить Требуемым образом 32 коней. Они держат под боем все белые поля. Проблема заключается в том, нельзя лИ как-то перестроить расположение коней, поместив часть из них на черные поля, а часть на белые, чтобы нашлось место для 33-го коня. И хотя интуИЦия подсказывает, что это невозможно, нам нужно строгое математическое доказательство этой невозможности.

Здесь помогает общий принцип решения ОптималЬных Проблем, — Если решение является оптимальным в Целом, То оно должно быть оптималЬНым и в любой сВОей части - Иначе, улучшив его в этой части, мы добьемся лучшего Результата и в целом. Разделим всю доску на 8 частей, имеющих По 4 горизонтали и 2 вертикалА (рис. 4) Но каждой из них можно расположить четырех коней — любой конь на (2 ´ 4)-доске держит под боем ровно одно поле. Отсюда и следует, что на всю (8 ´ 8)-доску можно Поставить лишь 8×4 = 32 коней, а это число коней мы уже умеем ставить. Второй способ расстановки заключается в том, что коней ставят на белые поля.

Точно таК жЕ доказывается, что на (N ´ N)-доску можНО поставить Не бьющих друг друга коней, если П Четно, и коней, если П нечетно.

< Предыдущая		Следующая >