10 подписчиков

Разбор задачи "Количество треугольников". Темы: комбинаторика, динамика

5 мая 20205 мая 2020

1 мин

Во время подготовки к олимпиадам по информатике мне попалась довольно-таки интересная задача. После двухчасового размышления над ней на уроке литературы, светлых идей мне в голову не пришло. Однако, вернувшись к ней через месяц, я смог относительно легко придумать решение за полчаса, и демонстрирую его вам.

Задача:

Рассмотрим фигуру, аналогичную показанной на рисунке (большой равносторонний треугольник, составленный из маленьких равносторонних треугольников). На рисунке приведена фигура, состоящая из 4-х уровней треугольников.

Требуется написать программу, которая будет определять, сколько всего в ней треугольников (необходимо учитывать не только "маленькие" треугольники, а вообще все треугольники — в частности, треугольник, выделенный жирным, а также вся фигура, являются интересующими нас треугольниками). На вход программе подаётся N - высота главного треугольника.

Путей решения данной задачи существует великое множество. Так как я не силен в комбинаторике, то именно динамика сразу пришла мне в голову.

Можно заметить, что в каждый следующий треугольник, начиная с треугольника высоты 3, входит ровно три треугольника высоты N - 1. Соответственно, мы можем использовать вычисленное для них значение треугольников. Однако, т.к. часть треугольников накладывается друг на друга, нам необходимо это учесть

Можно также заметить, что при наложении получается три треугольника величины N-2. Соответственно, значения для данных треугольников надо вычесть трижды. Тогда мы потеряем треугольник в центре высоты N-3, в котором все наложения сходятся. Чтобы этого не случилось, добавляем кол-во треугольников для треугольника высоты N-3 в решение.

Внимательный читатель также может заметить, что в нашей модели не учтен большой треугольник, а также то, что при четных N в центре появляется дополнительный треугольничек, повернутый вниз. Добавив соответствующие правки, получим готовую формулу!