Задача М695‍‍‍

Предположим, что требуемая раскраска возможна. Будем называть столбец белым или чёрным в соответствии с тем, какой цвет в нём преобладает. Аналогичные названия будут употребляться и для строк.

Пусть $m_0$‍,‍ $m_1$‍‍ — количества белых и чёрных строк, $n_0$‍,‍ $n_1$‍‍ — количества белых и чёрных столбцов соответственно, $m_0+m_1=m$‍,‍ $n_0+n_1=n$‍.‍

Все клетки, лежащие на пересечении белых строк с чёрными столбцами и чёрных строк с белыми столбцами, отличаются по цвету либо от содержащего их столбца, либо от содержащей их строки. Число таких клеток равно $m_0n_1+m_1n_0$‍.‍ Не уменьшая общности, можно считать, что более половины этого числа клеток отличается по цвету от содержащих их строк. Опять-таки, не уменьшая общности, можно считать, что $m_0\le m_1$‍.‍ В чёрных строках содержится по условию более $\dfrac34m_1n$‍‍ чёрных клеток. Значит, в белых строках содержится менее $\dfrac{mn}2-\dfrac34m_1n$‍‍ чёрных клеток. Но в чёрных строках содержится менее $\dfrac14m_1n$‍‍ белых клеток. Таким образом, число клеток, цвет которых отличается от цвета содержащих их строк, меньше $$ \dfrac{mn}2-\dfrac34m_1n+\dfrac14m_1n=\dfrac{m_0n}2. $$ Получаем неравенство $$ \dfrac12(m_0n_1+m_1n_0)\lt\dfrac{m_0n}2, $$ откуда $m_1\lt m_0$‍,‍ что противоречит предположению относительно $m_0$‍‍ и $m_1$‍.‍