Можно ли подобрать компанию где у каждого ее члена было бы ровно пять друзей, а у любых двух - ровно два общих друга?

По факту нам известно, что подобрать нельзя. Но как это доказать?
Дополнительный вопрос: а можно, если у каждого члена ровно шесть друзей?

Лучший ответ по мнению автора

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

Михаил Александров

Сейчас на сайте
Михаил Александров
Михаил Александров
Эксперт месяца
Читать ответы

Eleonora Gabrielyan

Сейчас на сайте
Читать ответы

Александр Калихевич

Сейчас на сайте
Читать ответы
Посмотреть всех экспертов из раздела Учеба и наука > Математика
Пользуйтесь нашим приложением Доступно на Google Play Загрузите в App Store