Разбиение доски на части
Ошибка.
Попробуйте повторить позже
В каждой клетке доски растет дерево высотой
сантиметр. Садовник и жук короед играют в игру, начинает садовник. В свой ход
он может выбрать произвольную клетку доски и увеличить высоту дерева в этой клетке, а также в клетках, соседних с выбранной по
стороне или вершине, на
сантиметр. Жук же в свой ход может уменьшить на
сантиметр высоту не более чем у четырех
любых деревьев. Назовем дерево развившимся, если его высота не менее
сантиметров, такие деревья жук короед
обходит стороной. Какое наибольшее количество развившихся деревьев может вырастить садовник независимо от действий
жука?
Подсказка 1
Задача на оценку плюс пример, нужно сделать две вещи: показать, как садовнику гарантировать присутствие искомого количества развившихся деревьев и показать, как жуку гарантировать отсутствие определённого количества развившихся деревьев. Начнём со второго: давайте выберем как можно больше конкретных деревьев, рост которых жук сможет полностью контролировать, для этого может быть полезна какая-нибудь раскраска.
Подсказка 2
Так можно подобрать раскраску доски в два цвета, что одного из цветов ровно 100 и жук может делать ходы так, что все деревья на выбранном цвете не станут развившимися. Теперь займёмся доказательством того, что садовник сможет развить 125 деревьев.
Подсказка 3
Доску разобьём на фигуры, в которых происходят действия садовника - квадраты 3 на 3, сходим равное количество раз в центр каждого из квадратов. Осталось показать, что при достаточном количестве ходов разовьётся достаточное количество, то есть 125 деревьев.
Сначала докажем, что жук короед может действовать так, чтобы не допустить появления более развившихся деревьев. Раскрасим
клетки доски в два цвета как на рисунке. Заметим, что садовник каждым своим ходом увеличивает высоту не более
деревьев, стоящих на
черных клетках. Тогда жук будет ходить в те же самые черные клетки ответным ходом. Тогда развившиеся деревья могут возникнуть
только на белых клетках, то есть их не более
Теперь докажем, что садовник всегда сможет вырастить хотя бы развившихся деревьев. Разобьем доску на квадраты
Пусть
садовник по очереди сходит в центр каждого из этих квадратов по
раз. Предположим, что, если некоторое фиксированное дерево
не
стало развившимя, то жук ходил в это дерево не менее
раз. Поскольку садовник всего сделал
ходов, жук также
сделал такое же количество ходов, то есть сходил в
клеток. С другой стороны, если он смог помешать садовнику
сделать
деревьев развивмися, то он сделал не менее
хода в клетки. Выбрав
получаем, что
— противоречие. Значит, садовник может сделать хотя
развившихся
деревьев.
Специальные программы

Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!