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