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