Question

Вы разрабатываете социальную сеть. В данный момент вы работаете над алгоритмом, который рекомендует пользователям новых друзей на основе того, с кем они уже дружат.

ДАЮ 29 БАЛЛОВ!!! У вас есть три пользователя: Виталий, Андрей и Павел, которые не дружат друг с другом. Известно, что у Виталия и Андрея 50 общих друзей, у Андрея и Павла 91 общих друзей, а у Павла и Виталия 56 общих друзей. Известно также, что всего у Виталия 90 друзей, у Павла 132 друзей, а у Андрея 121 друзей.

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

Answer 1

Перепишем условие. Обозначим множество друзей Виталия через V, Андрея - A, Павла - P, тогда:
$|V|=90\ |P|=132\ |A|=121\ |A cap V|=50\ |Acap P|=91\ |Pcap V|=56 \ |Acap V cap P| = ?$
Используя формулу включения-исключения для трех множеств:
$|Acup V cup P| = |A| + |V| + |P| - |A cap V| - |Acap P| -|Pcap V|+\+ |Acap V cap P|$
Очевидно, что $|Acap V cap P|$ будет минимальным, когда $|Acup V cup P|$ будет максимальным, а это возможно только, когда $|Acup V cup P| = |A| + |V| + |P|$
$90+132+121=90+132+121-50-91-56+x Rightarrow x=197$