Олимпиада Туймаада по математике. Старшая лига. 2019 год

На прямоугольной клетчатой доске отмечено $N$ клеток. Пусть $a_i$ — количество отмеченных клеток в $i$-й строке, $b_j$ — количество отмеченных клеток в $j$-м столбце. Докажите, что $$\prod_i a_i! \prod_j b_j !\leqslant N!$$ ( Ф. Петров )

Комментарий/решение

Прикольная задача на комбинаторный аргумент:

Пусть отмеченные клетки закрашены в $N$ различных цветов. Количество способов переставить клетки в каждой строке равна $\prod_{i}a_i!$. А для каждой такой перестановки $P$ количество перестановок клеток в каждом столбце для $P$ равна $\prod_{j}b_j!$ (причем заметим что никакие перестановки среди всех $P$ полностью не совпадают). Тогда общее количество данных различных перестановок $\prod_{i}a_i! \cdot \prod_{j}b_j!$, что не больше общего количества перестановок $N$ клеток равная $N!$, что и требовалось.