Question

..................................

Answer 1

Возьмем некоторого человека А. По условию у него есть хотя бы 2 друга. Обозначим их В и С. Тогда образуются следующие пары друзей: АВ и АС. Кроме того, по условию если два человека имеют общего друга, то и они друзья между собой. Тогда, имеем еще одну пару друзей ВС.

Берем еще одного человека D. Есть два случая: он дружит с А или не дружит с А. Если он дружит с А, то в силу того что А дружит с В и С, то и D должен будет дружить с В и С. Так как в вопросе нас спрашивают о минимальном числе пар друзей, то выгоднее рассмотреть случай, когда D не дружит с А. По тем же причинам он не дружит ни с В, ни с С. Тем не менее, какие-то друзья у D должны быть. Поэтому, сформируем некоторую тройку {D; E; F} аналогично друзьям {A; B; C}, а затем еще и тройку {G; H; I}. Каждый дружит с каждым внутри своих групп, но не дружит ни с кем из другой группы.

Пока мы рассмотрели 9 человек. Значит, осталось еще 2 человека: J и K. Поскольку каждый из них должен иметь хотя бы по 2 друга, то один из этих друзей будет человек, уже распределенный в группы.

Как было рассмотрено выше на примере D, если человек имеет друга в некоторой группе, то все остальные люди в этой группе также являются его друзьями. Другими словами, J и K нужно присоединить к каким-то группам. Нужно понять, выгоднее их присоединять к одной группе или к разным.

Пусть J присоединился к группе {A; B; C} (выбор группы не важен, так как во всех группах пока по 3 человека). Тогда возникает 3 новых пары друзей: AJ, BJ, CJ.

Теперь K нужно присоединить либо к группе {A; B; C; J} из 4 человек, либо к одной из групп из 3 человек. Понятно, что в первом случае образуется 4 новых пары друзей, а во втором случае - только 3. Значит, выгоднее K присоединить к группе из 3 человек, например, к группе {D; E; F}.

Итак, считаем общее число пар друзей. Можно сосчитать их просто: в каждой группе было по 3 пары друзей (об этом мы говорили), после присоединения каждого из двух последних человек к группам мы получали по 3 новых пары в каждом случае. Итого:

$3\cdot3+3+3=15$

Можно воспользоваться формулами комбинаторики. Для группы из 4 человек количество пар друзей определяется числом сочетаний из 4 по 2, для групп из 3 человек - соответственно числом сочетаний из 3 по 2:

$C_4^2+C_4^2+C_3^2=\dfrac{4\cdot3}{2} +\dfrac{4\cdot3}{2} +3=4\cdot3+3=15$

Ответ: 15