Задача 5. Звезда из ста шнуров

Что происходит после поджигания

Обозначим время горения шнура $OA_i$ через $t_i$ секунд. По условию оно не зависит от того, с какого конца шнур подожгли, а скорость горения может меняться как угодно — нам это не помешает: важно только полное время $t_i$.

Поджигаем звезду в точке $A_i$. Шнуры касаются друг друга только в точке $O$, поэтому сначала горит один шнур $OA_i$: через $t_i$ секунд огонь добирается до $O$. В этот момент загораются сразу все остальные 99 шнуров — у каждого подожжён конец $O$. Шнур $OA_j$ догорит ещё через $t_j$ секунд, а звезда сгорит целиком, когда догорит самый медленный из них. Значит, время полного сгорания при поджигании в $A_i$ равно

где $M_i$ — наибольшее из чисел $t_j$ при $j \ne i$, то есть время самого долгого из остальных шнуров (рисунок ниже).

Зачем это нужно: условие говорит о звезде и огне, а считать удобно с числами. Теперь каждое из чисел $201, 202, \ldots, 299$ — это сумма времён двух разных шнуров: того, который подожгли, и самого долгого из остальных.

Два самых долгих шнура дают одно и то же время

Пусть $OA_p$ — шнур, который горит дольше всех: $t_p = a$ (если таких несколько, возьмём любой из них). Среди остальных 99 шнуров тоже есть самый долгий — пусть это $OA_q$ с временем $t_q = b$. При этом $b \le a$, ведь $a$ — наибольшее из всех времён.

Подожжём звезду в точке $A_p$. Сначала $a$ секунд горит $OA_p$, потом одновременно горят остальные, и дольше всех из них — $OA_q$: ещё $b$ секунд. Итого $T_p = a + b$.

Теперь подожжём в точке $A_q$. Сначала $b$ секунд горит $OA_q$, потом среди остальных дольше всех горит $OA_p$: ещё $a$ секунд. Итого $T_q = b + a$.

Получилось одно и то же число $a + b$ (рисунок ниже). Как это заметить: при поджигании в $A_p$ второе слагаемое даёт шнур $OA_q$, а при поджигании в $A_q$ — шнур $OA_p$; два слагаемых просто меняются местами.

Дольше, чем $a + b$, звезда не горит

Подожжём звезду в любой точке $A_i$. По шагу 1 время $T_i$ — это сумма времён двух разных шнуров: подожжённого и самого долгого из остальных. Сравним эти два времени с $a$ и $b$.

Два разных шнура не могут оба быть шнуром $OA_p$, значит, хотя бы один из них — не $OA_p$, а время любого шнура, кроме $OA_p$, не больше $b$ (ведь $b$ — наибольшее среди всех времён без $t_p$). Время второго шнура не больше $a$, потому что $a$ — наибольшее из всех. Значит, $T_i \le b + a$.

Итак, среди ста чисел $T_1, T_2, \ldots, T_{100}$ наибольшее равно $a + b$, и оно встречается хотя бы дважды — в точках $A_p$ и $A_q$. Это главное наблюдение задачи: как ни подбирай времена шнуров, самое большое время сгорания обязательно повторится. В модели это видно сразу: все пять времён сделать разными не получается.

Применяем к звезде из условия

По условию $T_1 = 201$, $T_2 = 202$, …, $T_{99} = 299$ — все эти 99 чисел разные. Наибольшее из ста чисел $T_1, \ldots, T_{100}$ равно $a + b$ и встречается хотя бы дважды. Но среди первых 99 чисел нет двух одинаковых, так что среди них $a + b$ встречается не больше одного раза. Значит, второй раз — это обязательно $T_{100}$: получаем $T_{100} = a + b$.

Осталось найти $a + b$. Во-первых, это наибольшее из всех ста чисел, поэтому $a + b \ge T_{99} = 299$. Во-вторых, $a + b$ встречается и среди первых 99 чисел (это его второе появление), а все они не больше $299$. Поэтому $a + b = 299$, и

Заметь: мы так и не узнали, какие именно шнуры самые долгие и чему равны $a$ и $b$ по отдельности — для ответа нужна только их сумма (рисунок ниже).

Такая звезда существует

Чтобы убедиться, что условие не противоречиво и ответ $299$ действительно получается, построим пример. Пусть $t_i = 50 + i$ при $i = 1, 2, \ldots, 98$ (то есть $51, 52, \ldots, 148$), $t_{99} = 150$ и $t_{100} = 149$. Самый долгий шнур — $OA_{99}$, второй по времени — $OA_{100}$.

Проверяем. При поджигании в $A_i$, где $i \le 98$: сначала $50 + i$ секунд, потом самый долгий из остальных — $OA_{99}$, ещё $150$ секунд; всего $200 + i$, то есть $201, 202, \ldots, 298$ — как в условии. При поджигании в $A_{99}$: $150 + 149 = 299$. При поджигании в $A_{100}$: $149 + 150 = 299$.

Такой пример не единственный: подойдут, например, $t_i = 40 + i$ при $i \le 98$, $t_{99} = 160$, $t_{100} = 139$. Но по шагу 4 ответ один и тот же для любой звезды, удовлетворяющей условию.