Отбор Всесиба

Всего в строке и столбце, проходящих через данную клетку 19 клеток, поэтому если мы проделаем операции со всеми парами строк и столбцов таблицы (всего операций), то каждый знак в таблице поменяется 19 раз, став из минуса плюсом.

100 операций достаточно.

_________________________________________________________________________________________________________________________________________________________________________________

Операцию замены знаков во всех клетках некоторого столбца и некоторой строки будем называть операцией относительно клетки-пересечения этих строки и столбца. Клетки, относительно которых мы делали операции, назовём красными, остальные синими. Строки и столбцы, содержащие чётное число красных клеток назовём чётными, а содержащие нечётное число красных клеток — нечётными.

_________________________________________________________________________________________________________________________________________________________________________________

Допустим, можно поменять все знаки в таблице меньше чем за 100 операций, тогда рассмотрим некоторую синюю клетку в строке и столбце . Чтобы знак в поменялся, нужно, чтобы, чтобы и вместе содержали нечётное количество красных клеток, можно считать строку чётной, а столбец — нечётным.

Заметим, что на пересечении строки и столбца одинаковой чётности должна стоять красная клетка, а на пересечении строки и столбца разной чётности — синяя, иначе знак в этой клетке после всех операций не изменится. Следовательно, количество красных клеток в каждой чётной строке равно числу чётных столбцов, а количество синих — числу нечётных столбцов таблицы. Есть хотя бы одна чётная строка , значит, всего в таблице чётное число нечётных столбцов. Но количество красных клеток в каждой нечётной строке (нечётное!) равно числу нечётных столбцов, то есть чётному числу — противоречие с тем, что есть хотя бы один нечётный столбец. Следовательно, нельзя обойтись меньше, чем 100 операциями.