8-я Балканская математическая олимпиада среди юниоров Нови-Сад, Югославия, 2004 год

Рассмотрим выпуклый $n$-угольник $(n \geq 4)$. Разобьём многоугольник произвольным образом на треугольники так, что их вершины являются вершинами многоугольника, и любые два треугольника не пересекаются. Покрасим в чёрный цвет те треугольники, у которых две стороны являются сторонами многоугольника; в красный цвет — те треугольники, у которых только одна сторона является стороной многоугольника; в белый цвет — те треугольники, у которых стороны не являются сторонами многоугольника.
Докажите, что чёрных треугольников да два больше чем белых.

Комментарий/решение

Пусть $b,r,w$ - количества черных, красных и белых треугольников, соответственно.

Лемма 1. $r+2b=n$.

Доказательство: сложим количества сторон, являющихся общими для треугольников и данного $n$-угольника

Лемма 2. $b+r+w=n-2$.

Доказательство: По индукции докажем, что количество треугольников равно $n-2$. База $n=3,4$ очевидна. Пусть утверждение верно при всех $3\le n\le k$. Проведённая в разбиении $k+1$-угольника диагональ, разделяет его на $r$-угольник и $s$-угольник, причем $r+s=n+2$. Количество треугольников в $r$-угольнике равно $r-2$, в $s$-угольнике $s-2$. В итоге их сумма $(r-2)+(s-2)=n-2$ является искомым количеством. Лемма доказана.

Вычитаем условие первой леммы из второй, тогда $b-w=2$, что требовалось