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