Раскраски
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Каждая клетка квадрата 
может быть покрашена в белый или черный цвет. За один ход можно выбрать 
клетки, являющиеся
вершинами прямоугольника со сторонами, параллельными линиям сетки, и перекрасить их в противоположный цвет. Для какого
наибольшего 
можно найти 
различных раскрасок квадрата так, чтобы ни одну из выбранных раскрасок нельзя было бы привести ни к
одной другой с помощью выбранных операций?
Подсказка 1
Заметим, что любая клетка левого верхнего квадрата (n-1)×(n-1) является вершиной какого-то прямоугольника с тремя точками вне левого верхнего квадрата (n-1)×(n-1). Как тогда можно оценить количество раскрасок этого квадрата?
Подсказка 2
Верно, для любой изначальной раскраски квадрата n×n можно получить любую раскраску левого верхнего квадрата (n-1)×(n-1), например таких, где он весь белый. Таких существует 2²ⁿ⁻¹, а значит, ответ не более, чем это число. Будем теперь доказывать, что 2²ⁿ⁻¹ раскрасок, которые не получаются друг из друга, существуют. Рассмотрим произвольную строку или столбец. Какой инвариант для неё существует?
Подсказка 3
Верно, чётность. Для различных раскрасок n×n, при которых верхний левый (n-1)×(n-1) белый различаются какие-то клетки, а значит, в чётность в некоторой строке или столбце. Потому их нельзя получить друг из друга.
Покажем, что при 
существует две эквивалентные раскраски. Покажем, что любую раскраску разрешёнными операциями можно
перевести в раскраску, в которой верхний левый квадрат 
— белый. Действительно, для каждой клетки в квадрате
можно подобрать 
клетки, лежащие вне него так, чтобы они образовывали необходимий прямоугольник. Таким
образом, мы можем перекрасить любую клетку. А так как раскрасок, в которых верхний левый квадрат 
— белый, 
то по принципу Дирихле найдутся две совпадающих раскраски. Тогда две соответствующие исходные раскраски можно перевести друг в
друга.
Покажем, что все 
раскрасок, в которых верхний левый квадрат 
— белый, нельзя перевести друг в друга
операциями. Заметим, что чётность количества чёрных клеток в 
-м столбце — инвариант. Аналогичное утверждение верно для строк. А
так как в выбранных раскрасках левый верхний квадрат 
— белый, покраска оставшихся строки и столбца определяет
четность количества чёрных клеток во всех строках и столбцах.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
