Задача 66482

Тема:    [ Теория алгоритмов (прочее) ]

Сложность: 4 Классы: 8,9,10,11

Условие

Автор: Рябов П.

Карлсон ест треугольный торт. Он режет торт по биссектрисе одного из углов, съедает одну из частей, а с другой повторяет ту же операцию. Если Карлсон съест больше половины торта, он станет не в меру упитанным мужчиной в самом расцвете сил. Докажите, что рано или поздно это произойдёт.

Решение

Обозначим через $D$ наибольшую из длин сторон торта. Тогда длины всех сторон всех треугольников, которые будут получаться у Карлсона в процессе поедания торта, не будут превосходить $D$.

Предположим, что Карлсон может сделать сколько угодно описанных операций так, чтобы площадь съеденного торта не превосходила $1/2$ от площади всего торта.

Возьмем треугольник, который получается на $(k-1)$-м шаге, и обозначим его площадь через $S_k$, а стороны, между которыми проходит $k$-й разрез, через $a_k$ и $b_k$. Будем считать, что Карлсон съедает кусок, примыкающий к стороне $a_k$. Тогда по теореме о биссектрисе площадь съеденного на $k$-м шаге куска равна $S_k-S_{k+1}=\frac{S_ka_k}{a_k+b_k}$.

Рассмотрим длины всех сторон $a_k$. Возможны два случая: либо они все больше некоторого положительного числа $\ell>0$, либо такого числа $\ell$ не существует.

В первом случае получается, что на $k$-м шаге Карлсон съедает кусок торта площадью не меньше чем $$\frac{a_k S_k}{a_k+b_k}>\frac{a_k S_k}{2D}>\frac{\ell S_k}{2D}.$$ Можно оценить площадь оставшегося куска: $$S_{k+1} < S_k\left(1-\frac{\ell}{2D}\right).$$ Поэтому $S_{k+1} < S_1(1-\frac{\ell}{2D})^k$. Но выражение в скобках строго меньше 1, то есть при достаточно больших $k$ его $k$-я степень будет меньше $1/2$.

Допустим теперь, что $a_k$ могут быть сколь угодно близки к нулю. Возьмем такое $a_k$, для которого $a_k < S_1/D$. Оценим площадь треугольника $S_k$ сверху как половину произведения сторон: $S_k\leq a_k D/2$. Но, поскольку $a_k < S_1/D$, отсюда следует, что $S_k < S_1/2$, то есть к $k$-му шагу больше половины торта уже окажется съедено.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	81
Год	2018
класс
Класс	10
задача
Номер	5