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

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

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

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

Елена Васильевна

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

Роман

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

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

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