Задание №177349: Турнир городов

3. Изначально в бизнес-центре базировались 2n фирм, каждая занимала некоторую площадь,
все площади были различны. Каждый год фирмы объединялись в пары, и в каждой паре фирма с
меньшей площадью присоединилась к фирме с большей. При этом ни в какой момент времени не
1

было двух фирм с одинаковой площадью. Через n лет осталась одна фирма. Какое наименьшее
место по площади (считая от меньшей к большей) эта фирма могла занимать вначале?
Б. Френкин

Ответ: n + 1.
Решение. Занумеруем фирмы в порядке возрастания капиталов. Пусть фирма A из условия за-
дачи получила номер m < n + 1. Так как она сохранилась на первом шаге, то к ней присоединилась
некоторая фирма B с номером k < m. Было ещё не больше m − 2 пар, в которые вошли фирмы
с номерами меньше m. В остальных парах обе фирмы были больше, чем A и B, поэтому у остав-
шихся фирм капитал получился больше, чем у A. Занумеруем фирмы снова, в порядке возрастания

образовавшихся капиталов. Тогда фирма A получит номер не больше m−1. Аналогично на каждом
следующем шаге её номер убывает. Так как всего шагов n ≥ m, то не позже чем на предпоследнем
шаге A получит номер 1 и присоединится к другой фирме — противоречие.
Теперь построим один из возможных примеров, когда (n + 1)-я фирма (обозначим её F) при-
соединяет все остальные. Представим себе, что после каждого шага объединения общая площадь
уменьшается в два раза. Это значит, что большей из двух фирм достаётся не сумма, а среднее ариф-
метическое площадей. Ясно, что на каждом шаге будут оставаться те же фирмы, что и при исходной
процедуре. Теперь отметим на числовой прямой положительное число f и будем считать, что это
площадь фирмы F по окончании процесса. Отметим два числа g и h, симметричные относительно f.

Можно считать, что это площади, занятые фирмой F и другой фирмой G перед последним объедине-
нием. Каждая из них есть среднее арифметическое площадей двух фирм перед предыдущим шагом.
В качестве этих площадей выберем два числа, симметричных относительно g, и два симметричных
относительно h. Одно из них — площадь f′ фирмы F перед предпоследним шагом. Можно выбрать
эти числа так, что два из них меньше f′, а одно — больше. Повторим этот шаг, выбрав 8 чисел в
качестве площадей фирм, существовавших перед предыдущим шагом. Можно выбрать их так, что
площади трёх фирм будут меньше площади фирмы F, а остальные больше. Продолжая аналогично,
получим в качестве исходных площадей фирм 2n чисел, из которых только n меньше, чем исходная
площадь фирмы F. Если все упомянутые числа выбирать достаточно близко друг от друга, то все

они окажутся положительными, и мы получаем искомый пример.