Подсчеты в клетчатых задачах

Назовем множество из клеток, никакие две из которых не находятся в одной строке или в одном столбце, ладейной расстановкой. Пусть — множество всех ладейных расстановок, — множество арифметический прогрессий длины все элементы которых натуральные числа, не превосходящие

Рассмотрим произвольную прогрессию из Если какие-то два ее элемента находятся в одной строке или столбце, то она не является подмножеством никакой ладейной расстановки из иначе есть ровно расстановок таких, что все элементы прогрессии, входят в данные расстановки. Достаточно доказать, что найдется ладейная расстановка такая, что никакой элемент множества не является ее подмножеством. Для этого покажем, что

Ясно, что следовательно, достаточно показать, что

Каждая арифметическая прогрессия задается парой где — первый элемент прогрессии, — ее разность. Несложно показать, что Таким образом, количество таких пар не превосходит Наконец, достаточно показать неравенство

при Расскрывая скобки и приводя подобные, имеем

Последнее является суммой неравенств