Комбинаторика на Изумруде: клетчатые задачи, игры, способы, процессы

Для начала рассмотрим, сколько различных наборов из клеток можно выбрать, чтобы никакие две не находились в одной строке или столбце. Всевозможных способов выбрать клеток так, чтобы в каждой строке и в каждом столбце была ровно одна — ровно число перестановок Это можно объяснить тем, что, допустим, выбирая по клетке в строке, с каждой строкой количество "разрешённых"вариантов уменьшается ровно на 1.

Теперь рассмотрим четвёрки клеток, центры которых лежат на одной прямой. Ясно, что их координаты по оси ординат и абсцисс образуют арифметическую прогрессию с начальным членом и шагом для которых выполняется:

Шаг может принимать значения от 1 до можем оценить сверху количество плохих расстановок по строкам и столбцам (отдельно):

"Запрещённая"четвёрка определяется выбором прогрессии по столбцам, по строкам, направлением (по строкам и столбцам). Каждая "запрещённая"четвёрка клеток встречается в любом наборе из содержащем эти четыре клетки. Остальные клетки можно выбрать произвольно (с учётом строки–столбца), то есть из вариантов.

Получается, что количество всех "плохих"(содержащих хотя бы одну "запрещённую"четвёрку) наборов не превосходит:

Если бы решений не было, то все вариантов были бы плохими, и мы получили бы неравенство:

Разделим на и упростим:

Но при неравенство не выполняется. Получили противоречие.

Остаётся проверить вручную случаи Примеры правильных построений легко построить, используя вышеуказанные ограничения и запреты на расположения клеток.