Задача на логику про бухгалтеров

Question

В бухгалтерском отделе работают 150 сотрудников. Каждые двое из них — друзья
или враги. Причем известно, что у любых двух врагов есть общий друг-бухгалтер. Какое наименьше количество пар друзей-бухгалтеров может быть?

Answer 1

Пусть все 150 сотрудников являются врагами друг друга. Тогда есть ${150 \choose 2} = 11175$ пар врагов. По условию задачи, у каждой такой пары есть общий друг, который тоже является бухгалтером. Но это значит, что число бухгалтеров должно быть не меньше, чем число пар врагов. Таким образом, наименьше количество пар друзей-бухгалтеров равно 11175. Но это означает, что весь отдел состоит из врагов друг друга, что маловероятно. Если бы среди сотрудников были и друзья, то число пар друзей-бухгалтеров было бы меньше.