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