Если гангстеры не враждуют, то будем считать, что они дружат. Тогда банда – это максимальная дружная компания (добавление любого гангстера нарушает её дружность). И всякую такую компанию объявим бандой, если она таковой ещё не является.  Пример. Пусть гангстеры разбиты на 12 троек, гангстеры из одной тройки враждуют, а из разных – дружат. Тогда каждая банда содержит из каждой тройки ровно по одному гангстеру. Поэтому будет 3¹²банд.   Оценка. Первый способ. Назовём авторитетом гангстера количество банд, в которых он состоит.   Лемма. Пусть два гангстера враждуют. Тогда замена одного из них клоном другого, более авторитетного, увеличивает количество банд. Считаем, что гангстер и его клон враждуют.

  Доказательство. Рассмотрим гангстера G. Каждая банда содержит его либо одного из его врагов. Пусть банды первого вида образуют множество A, второго – B. Удалим G.

  При этом все банды из B остались бандами, а некоторые банды из A, лишившись члена, могли перестать быть бандами, утратив максимальность.   Покажем, что новых банд не образовалось. Рассмотрим новую банду. Если она содержит кого-то из враговG, то она и ранее была бандой изB. Если же она состоит только из друзейG, то к ней не получается добавить враговG, поэтомуGвходил в неё до удаления. Таким образом, эта банда и ранее была бандой из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 троек.

  Таким образом, количество банд не больше 3¹².   Второй способ. Пусть B(n) – наибольшее возможное количество банд, образующихся во множестве из n гангстеров. Докажем индукцией по n, что  B(n) ≤ 3^n/3.

  База. Нам удобнее начать с  n = 0.  В этом случае (и только в нём) пустое множество является бандой. Поэтому  В(0) = 1 = 3^0/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 ≤ 3^n/3,  то есть  a³ ≤ 3^a.  Это неравенство верно для  a = 1, 2 и 3.  При каждом следующем увеличении a на единицу правая часть умножается на 3, а левая – на   (^a+1/_a)³ ≤ (⁴/₃)³ < 3.

3¹² банд.