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