Question

У вас есть три пользователя: Виталий, Андрей и Павел, которые не дружат друг с другом. Известно, что у Виталия и Андрея 56 общих друзей, у Андрея и Павла 96 общих друзей, а у Павла и Виталия 76 общих друзей. Известно также, что всего у Виталия 96 друзей, у Павла 162 друзей, а у Андрея 108 друзей. Каково минимальное количество пользователей соцсети, которые дружат и с Павлом, и с Виталием, и с Андреем?

Answer 1

Прежде чем начать рисовать взаимопересекающиеся множества общих друзей, я заглянул в Словарь иностранных слов, вошедших в состав русского языка.- Чудинов А.Н., 1910., и нашел толкование слова «МИНИМАЛЬНЫЙ» - (от лат. minimi — малейший). Наименьшая из рассматриваемых величин.
      Исходя из этого определения и логики, у трёх этих пользователей обязательно найдётся хотя бы 1 (один) общий друг. Это и есть ответ на поставленный вопрос: минимальное количество пользователей соцсети, которые дружат и с Павлом, и с Виталием, и с Андреем — один.

Answer 2

Для решения этой задачи можно использовать принцип включения-исключения.

Обозначим множество друзей Виталия за A, множество друзей Андрея за B, а множество друзей Павла за C. Пусть X обозначает множество пользователей соцсети, которые дружат и с Павлом, и с Виталием, и с Андреем.

Из условия задачи у нас есть следующие данные:

|A| = 96 (количество друзей Виталия) |B| = 108 (количество друзей Андрея) |C| = 162 (количество друзей Павла)

|A ∩ B| = 56 (количество общих друзей Виталия и Андрея) |B ∩ C| = 96 (количество общих друзей Андрея и Павла) |C ∩ A| = 76 (количество общих друзей Павла и Виталия)

Мы хотим найти |X| (мощность множества X).

Используем принцип включения-исключения:

|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |B ∩ C| - |C ∩ A| + |X|

Теперь подставляем значения:

96 + 108 + 162 - 56 - 96 - 76 + |X| = |X|

Отсюда можно выразить |X|:

|X| = 96 + 108 + 162 - 56 - 96 - 76 = 238

Минимальное количество пользователей соцсети, которые дружат и с Павлом, и с Виталием, и с Андреем, равно 238.