Прямоугольные задачи
Прямоугольные задачи — это комбинаторные задачи на клетчатой доске, где нужно расставлять шахматные фигуры, считать клетки, искать максимум или минимум и доказывать невозможность некоторых расположений.
В этой подборке под прямоугольными задачами понимаются задачи на квадратных и прямоугольных клетчатых досках. Шахматные фигуры здесь используются прежде всего как удобный способ задать ограничения: ладья контролирует строку и столбец, король — соседние клетки, а конь перемещается особым образом между клетками.
Попробуйте сначала решить каждую задачу самостоятельно. Ответ и объяснение можно открыть после условия.
Задача 1. 51 ладья на доске 8 × 8
На шахматной доске 8 × 8 стоят 51 ладья. Докажите, что каждая ладья бьёт хотя бы одну другую.
Решение. Предположим, что одна из ладей не бьёт ни одной другой. Тогда в её строке и столбце других ладей нет. Для остальных 50 ладей остаётся квадрат 7 × 7, содержащий только 49 клеток. Разместить на них 50 ладей невозможно. Значит, изолированной ладьи быть не может.
Задача 2. Ладьи, которые не бьют друг друга
Какое максимальное число ладей можно поставить на доску 8 × 8 так, чтобы ни одна из них не била другую?
Решение. 8 ладей. В каждой строке и каждом столбце может находиться не больше одной ладьи, поэтому поставить больше восьми невозможно. Восемь ладей разместить можно, например по одной на каждой клетке главной диагонали.
Задача 3. Короли на шахматной доске
Какое максимальное число королей можно расставить на доске 8 × 8 так, чтобы они не били друг друга?
Решение. 16 королей. Разобьём доску на шестнадцать квадратов 2 × 2. В каждом таком квадрате может стоять не больше одного короля, потому что любые две его клетки соседствуют по стороне или диагонали. Значит, больше 16 королей поставить нельзя. Такое количество достижимо, если занимать каждую вторую строку и каждый второй столбец.
Задача 4. Кони, которые не атакуют друг друга
Какое максимальное число коней можно поставить на доску 8 × 8 так, чтобы ни один конь не атаковал другого?
Решение. 32 коня. Разобьём доску на восемь прямоугольников 2 × 4. В каждом из них восемь клеток можно разбить на четыре пары, внутри каждой из которых клетки соединены ходом коня. Поэтому из каждой пары можно занять не более одной клетки — максимум четыре коня на прямоугольник, а всего 32. Такое количество достигается ещё проще: достаточно поставить коней на все 32 клетки одного цвета.
Задача 5. Раскраска клетчатой доски
В какое минимальное число цветов нужно раскрасить клетки доски 8 × 8 так, чтобы любые две клетки, соседние по стороне или вершине, имели разные цвета?
Решение. 4 цвета. Любой квадрат 2 × 2 содержит четыре клетки, каждая из которых соседствует с тремя остальными, поэтому четырём клеткам нужны четыре разных цвета. Четырёх цветов достаточно: один четырёхцветный узор 2 × 2 можно повторить по всей доске.
Задача 6. Пять закрашенных клеток
В квадрате 3 × 3 закрашено пять клеток. Докажите, что найдётся закрашенная клетка, у которой есть другая закрашенная клетка и в той же строке, и в том же столбце.
Решение. Предположим обратное. Среди трёх строк обязательно есть строка как минимум с двумя закрашенными клетками. Столбцы этих клеток больше не могут содержать закрашенных клеток, иначе одна из них имела бы закрашенного соседа и по строке, и по столбцу. Все остальные закрашенные клетки пришлось бы размещать только в третьем столбце. В двух оставшихся строках там помещаются лишь две клетки, поэтому всего можно получить не более четырёх закрашенных клеток. Получили противоречие.
Как искать решение подобных задач
Во многих задачах на клетчатой доске полезно сначала отказаться от перебора конкретных позиций и посмотреть на структуру доски. Строки и столбцы помогают считать ладьи, блоки 2 × 2 — королей и раскраски, а разбиение доски на небольшие прямоугольники может дать верхнюю границу для числа фигур.
Полезный первый вопрос: на какие одинаковые части можно разбить доску и сколько объектов максимально помещается в каждой части? Именно такой взгляд часто превращает внешне сложную шахматную задачу в короткую задачу по комбинаторике.