|
|
 |
Условие
В Чикаго живут 36 гангстеров, некоторые из которых враждуют между собой. Каждый гангстер состоит в нескольких бандах, причём нет двух банд с совпадающим составом. Оказалось, что гангстеры, состоящие в одной банде, не враждуют, но если гангстер не состоит в какой-то банде, то он враждует хотя бы с одним её участником. Какое наибольшее число банд могло быть в Чикаго?
Решение
Если гангстеры не враждуют, то будем считать, что они дружат. Тогда банда – это максимальная дружная компания (добавление любого гангстера нарушает её дружность). И всякую такую компанию объявим бандой, если она таковой ещё не является.
Пример. Пусть гангстеры разбиты на 12 троек, гангстеры из одной тройки враждуют, а из разных – дружат. Тогда каждая банда содержит из каждой тройки ровно по одному гангстеру. Поэтому будет 312 банд.Оценка. Первый способ. Назовём авторитетом гангстера количество банд, в которых он состоит.
Лемма. Пусть два гангстера враждуют. Тогда замена одного из них клоном другого, более авторитетного, увеличивает количество банд. Считаем, что гангстер и его клон враждуют.
Доказательство. Рассмотрим гангстера G. Каждая банда содержит его либо одного из его врагов. Пусть банды первого вида образуют множество A, второго – B. Удалим G.
При этом все банды из B остались бандами, а некоторые банды из A, лишившись члена, могли перестать быть бандами, утратив максимальность.
Итак, количество банд уменьшилось не более чем на авторитет G.
Пусть гангстер X был более авторитетным врагом гангстера G. Авторитет X не изменился. Каждая банда сейчас содержит X или врага X. Добавим гангстера K – клона X. Бывшие банды останутся бандами, но добавятся банды, содержащие K, а их количество равно авторитету X. Таким образом, за обе операции количество банд увеличилось.
Пусть взаимоотношения 36 гангстеров таковы, что количество банд наибольшее из возможных. Из леммы следует, что в этом случае у врагов одинаковые авторитеты. Возьмём любого гангстера X. Заменим его врага клоном X. Согласно лемме, количество банд не изменится. Поэтому опять у врагов одинаковые авторитеты. Следовательно, мы можем ещё одного врага X заменить клоном X, не изменив количество банд. Так поступим со всеми врагами X. Получим компанию враждующих гангстеров, которые дружат со всеми остальными гангстерами.
Возьмём гангстера не из этой компании и проделаем с ним то же самое, и так далее. В итоге все гангстеры разобьются на компании, причём гангстеры из одной компании враждуют, а из разных – дружат. Тогда количество банд равно произведению размеров компаний.
Задача свелась к такой: число 36 разложено на натуральные слагаемые; при каком разложении произведение этих слагаемых максимально?
Единичные слагаемые добавим к любому, произведение увеличится. Слагаемые вида n + 2, где n ≥ 2, будем разбивать на два, произведение не будет уменьшаться, поскольку 2n ≥ n + 2. Останутся только двойки и тройки. Заменяя три двойки на две тройки, будем увеличивать произведение. Так как 36 делится на 3, то в итоге получим 12 троек.
Таким образом, количество банд не больше 312.
Второй способ. Пусть B(n) – наибольшее возможное количество банд, образующихся во множестве из n гангстеров. Докажем индукцией по n, что B(n) ≤ 3n/3.
База. Нам удобнее начать с n = 0. В этом случае (и только в нём) пустое множество является бандой. Поэтому В(0) = 1 = 30/3.
Шаг индукции. Пусть имеется n > 0 гангстеров, и они составляют B(n) банд, причём самый дружелюбный гангстер A имеет a – 1 врага.
Рассмотрим произвольного гангстера C, имеющего c – 1 врага. Каждая "его" банда содержит кроме него только некоторых его друзей, которые, как легко проверить, образуют банду во множестве всех n – c его друзей. Поэтому, учитывая предположение индукции, "его" банд не больше
B(n – c) ≤ 3(n–c)/3 ≤ 3(n–a)/3.
Каждая банда содержит A или кого-то из его врагов. Как показано выше, для каждого из этих a гангстеров количество "его" банд не превосходит 3(n–a)/3. Значит, B(n) ≤ a·3(n–a)/3.
Поэтому достаточно доказать, что a·3(n–a)/3 ≤ 3n/3, то есть a3 ≤ 3a. Это неравенство верно для a = 1, 2 и 3. При каждом следующем увеличении a на единицу правая часть умножается на 3, а левая – на (a+1/a)3 ≤ (4/3)3 < 3.
Ответ
312 банд.
Замечания
1. Аналогично можно доказать, что при n = 3k (k ≥ 1) B(n) = 3k, при n = 3k + 2 (k ≥ 0) B(n) = 2·3k, при n = 3k + 1 (k ≥ 1) B(n) = 4·3k–1.
2. Ср. с задачей 66088.
3. 12 баллов.
