Программист Индусов работает с таблицей 2011×2013, в клетках которой произвольным образом расставлены числа 0 и 1.

Пример 1:

а) Программист Индусов работает с таблицей 2011×2013, в клетках которой произвольным образом расставлены числа 0 и 1. Он умеет за один шаг заменять одновременно все цифры в одном столбце или строке на ту цифру, которая там встречается чаще всего. Как ему сделать так, чтобы во всех клетках таблицы стояло одно и то же: только нули или только единицы?

б) А сумеет ли Индусов добиться этого для таблицы 2012×2012?

Решение от преподавателя:

а) В каждой строке от 1-й до 2011-й заменим все значения на то, которое в данной строке встречается чаще. (Поскольку в каждой строке 2013 символов, единиц и нулей в ней не может быть поровну, а значит, одно из чисел встречается чаще, чем другое.) Таким способов Индусов получит 2011 строк, каждая из которых состоит либо из одних нулей, либо из одних единиц. Теперь посмотрим на столбцы: они все стали одинаковыми. Поскольку каждый столбец имеет нечётную высоту (2011), то либо нулей, либо единиц в нём больше. А поскольку все столбцы одинаковые, то либо в каждом из них больше нулей, либо в каждом из них больше единиц. Так что если теперь заменить все числа в каждом столбце на то, которое там встречается чаще, то вся таблица будет заполнена одинаковыми числами.

б) Не обязательно. Например, если первые 1006 строк заполнены единицами, а остальные — нулями, то Индусов не сможет изменить ни одно значение в таблице.