Учеба и наука
Решено
Закрыт
vip
Можно ли подобрать компанию где у каждого ее члена было бы ровно пять друзей, а у любых двух - ровно два общих друга? - вопрос №2922475
По факту нам известно, что подобрать нельзя. Но как это доказать?
Дополнительный вопрос: а можно, если у каждого члена ровно шесть друзей?
июль 4, 2018 г.
-
Всего ответов: 1
-
Пусть такая компания возможна и состоит из n человек. Тогда в ней имеется n(n − 1)/2 пар, у каждой из которых список общих друзей состоит из 2-х человек. Если записать эти списки подряд, то получим список, в котором n(n − 1) позиций. При этом каждый участник компании является общим другом для каждой пары своих друзей (всего таких пар 5*4/2 = 10) и ни для какой другой пары. Поэтому он упомянут в списке 10 раз, и всего в списке 10n позиций. Таким образом, должно выполняться равенство n(n − 1) = 10n, откуда n=11. Но количество нечётных вершин у графа должно быть чётным. Получили противоречие.
Лучший ответ по мнению автора
