Раскраска клеток таблицы 100 × 100 в чёрный и белый цвета называется допустимой, если в каждой строке и каждом столбце от 50 до 60 чёрных клеток. Разрешается изменить цвет одной из клеток допустимой раскраски, если она остаётся допустимой. Докажите, что такими операциями можно получить из любой допустимой раскраски любую другую.
(О. Иванова)
Пусть θ — одна из допустимых раскрасок квадрата, а именно, та, в которой левый верхний и правый нижний квадpaты 
(назовём их ЛВ, ПН) полностью черные, а два других, ЛН и ПВ, — белые. Поскольку операции обратимы, достаточно научиться из любой допустимой раскраски получать раскраску θ. А для этого, в свою очередь, достаточно научиться в любой допустимой раскраске 
увеличивать число квадратов, раскрашенных так же, как в θ.
Предположим, что это невозможно. Если в раскраске τ все клетки в ЛВ и ПН чёрные, мы могли бы перекрасить все прочие черные клетки в белый цвет и получить раскраску 
Значит, τ содержит белые клетки в ЛВ, ни одну из которых нельзя перекрасить. Тогда каждая из этих белых клеток лежит либо в предельно черной строке (т. е. в строке, содержащей 60 черных клеток), либо в предельно черном столбце.
Пусть в ЛВ имеется k предельно черных строк, содержащих a белых клеток. Всего в этих строках 
черных клеток, из них 
клеток находятся в ЛВ, значит, остальные 
черных клеток расположены в ПВ. Ни одну из них тоже не перекрасить — это может быть лишь потому, что каждая стоит в столбце, содержащем 50 черных и 50 белых клеток. Так как в этих столбцах есть не менее черных клеток в ПВ, они содержат хотя бы белых клеток в ПН. (Эти клетки тоже нельзя перекрасить — потому, что они находятся в предельно черных строках.) Получается, что в ПН больше белых клеток, чем в ЛВ. Аналогично наоборот. Противоречие.