Во время IT-бума в некоторой стране образовалось 100 фирм, работающих в этой отрасли. Некоторые фирмы были поглощены другими. При этом, как выяснили аналитики, из любых 10 фирм всегда найдется две фирмы, одна из которых поглотила другую (если фирма А поглотила фирму В, которая ранее поглотила фирму С, то считается, что фирма А поглотила фирму С). Назовем цепочкой длины n ситуацию, когда фирма 1 была поглощена фирмой 2, та была поглощена фирмой 3, и так далее до фирмы (n−1), которая поглотила все предыдущие и была поглощена фирмой n. В принципе, могло оказаться, что максимальная цепочка имеет длину 100. А какова минимально возможная длина такой максимальной цепочки?

Для решения этой задачи давайте проанализируем ситуацию, описанную в условии. 1. **Понимание условия:** У нас есть 100 фирм. Из условия мы знаем, что среди любых 10 фирм всегда найдется пара фирм, одна из которых поглотила другую. Это означает, что существует иерархическая структура — некоторые фирмы поглощают другие, и этот процесс может повторяться. 2. **Формулировка задачи:** Нам нужно выяснить, какова минимально возможная длина максимальной цепочки поглощений, то есть, на сколько уровней можно «разделить» цепочку поглощений. 3. **Модель:** Рассмотрим эту ситуацию как ориентированный граф, в котором: - Вершины (узлы) — это фирмы, - Ребра (стрелки) указывают на поглощение (если фирма A поглотила фирму B, то мы рисуем стрелку от A к B). 4. **Анализ цепочки:** Для того чтобы определить минимально возможную длину максимальной цепочки, введем понятие "длинные цепочки". Давайте предположим, что максимальная длина цепочки составляет \(k\). Это означает, что могут существовать \(k\) фирм, где каждая следующая фирма поглощает предыдущую. 5. **Применение принципа Дирихле:** Если у нас есть 100 фирм и мы хотим рассмотреть подгруппы по 10 фирм (как указано в задаче), то по принципу Дирихле, из 100 фирм и 10 подгрупп всегда будет существовать связь между двумя фирмами в каждой группе. Это предполагает, что связь между поглощениями достаточно сильная. 6. **Определим длину цепочек:** Основная идея в том, что для каждой из 10 формируемых подгрупп может существовать одна "верхняя" фирма (через общие цепочки). Таким образом, если мы разделим 100 фирм на группы по 10 фирм, то у нас будет 10 верхних фирм, каждая из которых может являться вершиной своей цепочки. 7. **Подсчет:** Если мы рассматриваем \(x\) как количество "верхних" фирм, каждая из которых может поглотить 9 фирм из своей группы, получается: - В каждой группе по 10 только одна верхняя может вести свою цепочку до 10 (поглощенные). 8. **Значение:** Если мы повторим данный процесс для других групп, тогда минимальная длина максимальной цепочки измеряется как: \[ k = \lceil 100 / 10 \rceil = 10 \] То есть, для 100 фирм непрерывно будет максимальная длина цепочки 10, так как в каждой группе по 10 фирм одна поглощает другую. 9. **Ответ:** Следовательно, минимально возможная длина максимальной цепочки поглощений составляет 10. Таким образом, долгосрочный анализ показывает, что минимальная длина этой цепочки — **10**.