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