Ошибка.
Попробуйте повторить позже
Дана клетчатая доска 
Каждая клетка доски покрашена в один из двух цветов: белый или чёрный. Назовём раскраску доски
уравновешенной, если в каждой строке и в каждом столбце 50 белых и 50 чёрных клеток. За одну операцию разрешается выбрать две строки
и два столбца так, чтобы из 4 клеток на их пересечении две были чёрными, а две — белыми, и перекрасить каждую из этих 4 клеток в
противоположный цвет. Докажите, что из любой уравновешенной раскраски можно получить любую другую уравновешенную раскраску с
помощью указанных операций.
Источники:
Подсказка 1
Непонятно, как доказывать, что возможно перевести любую уравновешенную раскраску в любую другую. Может, тогда докажем, что любую уравновешенную раскраску можно перевести в какую-то конкретную, тогда из любой мы будем приходить в неё и уходить в любую другую, совершая в обратном порядке действия, с помощью которых мы бы приходили к ней. Надо подумать, к какой раскраске мы будем приходить...
Подсказка 2
На ум приходит, конечно же, шахматная раскраска. Но переводить доску целиком в шахматную как-то тяжеловато. Может, начать со столбцов?
Подсказка 3
Разобьем наши столбцы на пары и будем по очереди красить их в шахматную раскраску. Возьмем сейчас самую левую пару столбцов, которая еще не покрашена нужным нам образом. Будем приводить горизонтальные доминошки к шахматной раскраске сверху вниз. Что делать, если в какой-то момент у нас доминошка, которая содержит оба цвета, неправильно стоит?
Подсказка 4
Пускай для определённости левая клетка нашей доминошки черная:
Подсказка 5
А вывод такой: в какой-то доминошке, которая находится ниже нашей, левая клетка будет белой, а правая чёрной, ведь иначе суммарно чёрных клеток будет больше в первом столбце, чем во втором, а это противоречит тому, что раскраска доски уравновешенная. Тогда мы можем применить к этим двум доминошкам операцию и продолжить спуск вниз. Но что же делать, если в какой-то момент, идя вниз по столбцам, мы найдём одноцветную доминошку?
Подсказка 6
Пускай она чёрная. Можно заметить, что тогда ниже нашей доминошки существует белая доминошка (иначе в сумме по этим столбцам чёрных клеток будет слишком много). Что мы можем тогда сказать про строки, которые содержат наши доминошки?
Подсказка 7
На самом деле эти строки содержат две клетки, которые находятся в одном столбце, который находится правее наших, и при этом верхняя будет белая, а нижняя черная (Назовем этот столбец S). Это верно в силу того, что левее наших столбцов в этих строках поровну черных и белых клеток. Тогда мы можем выбрать один из наших столбцов, столбец S и поменять цвет клеток в них по этим строкам. Как же завершить решение?
Подсказка 8
Можно заметить, что, когда мы совершали операции по смене цвета, мы не нарушали уравновешенность таблицы. А это значит, что можно продолжать раскрашивать пары столбцов дальше и прийти к шахматной раскраске.
Докажем, что из любой уравновешенной доски можно получить доску, раскрашенную в шахматную раскраску, причём на каждом шаге доска будет оставаться уравновешенной. Из этого будет следовать, что из любой уравновешенной доски можно получить любую другую, так как операция обратима.
Будем получать шахматную раскраску следующим образом. Разобьём столбцы на пары подряд идущих. Выберем самую левую пару столбцов и в этой паре столбцов по очереди будем приводить строки (состоящие из двух клеток) к шахматной раскраске. После того как закончим с первой парой столбцов, перейдём ко второй и так далее.
Объясним, как делать следующий шаг внутри одной пары столбцов 
и 
Пусть в следующей строке 
сейчас находятся чёрная и
белая клетка, но в неправильном порядке. Например, слева стоит чёрная клетка, а справа белая, а должно быть наоборот.
Заметим, что во всех строках выше 
в первом столбце суммарно чёрных клеток не меньше, чем во втором, так как они уже
покрашены шахматным образом. Значит, в какой-то строке 
ниже 
должна быть ситуация, когда в левом столбце чёрных
клеток меньше, чем в правом, т.е. должна быть строка белая-чёрная (это следует из того, что суммарно в первом столбце
столько же чёрных клеток, сколько и во втором). Произведём операцию со строками 
и 
и текущими столбцами.
Пусть теперь у нас в строке 
стоят две одинаковые клетки, например чёрные. Тогда в какой-то строке 
должны оказаться две
белые клетки (иначе суммарно чёрных клеток в этих двух столбцах будет слишком много). Понятно, что эта строка расположена ниже
текущей, т.к. выше неё все строки разноцветные. Теперь заметим, что если посмотреть на эту пару строк во всей таблице, то должен быть
столбец 
правее 
и 
в котором в первой строке белая клетка, а во второй — чёрная. Тут мы пользуемся тем, что левее
наших столбцов в этих строках поровну чёрных и белых клеток. Теперь осталось лишь выбрать один из столбцов 
или
(в котором неправильный цвет в строке 
и столбец 
а также строки 
и 
и произвести операцию с ними.
Легко видеть, что на каждом шаге уравновешенность доски сохраняется. А так как мы всегда можем сделать шаг в нашем алгоритме, то в конце получится шахматная раскраска.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное обучение
в Школково
Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
