Задача 075 — Задачи на Графы

В некоторой компании любые двое знакомых имеют ровно $x$ общих знакомых, любые двое незнакомых имеют ровно у общих знакомых, Дима и Саша имеют не поровну знакомых ( $x, y$ — натуральные числа). Найдите все пары ( $x, y$ ), при которых так может быть.

Подсказка

Рассмотрим пару знакомых человек: назовем их $u$ и $v$ . В множестве членов компании, отличных от $u$ и $v$ , выделим три множества: $A$ — множество общих знакомых $u$ и $v ; B$ — множество знакомых с $v$ , но не с $u ; C$ множество знакомых с $u$ , но не с $v$ .

Решение

Ответ. ( $x, 1$ ) для любого $x$ .

Решение. Рассмотрим пару знакомых человек: назовем их $u$ и $v$ . В множестве членов компании, отличных от $u$ и $v$ , выделим три множества: $A$ — множество общих знакомых $u$ и $v ; B$ — множество знакомых с $v$ , но не с $u ; C$ множество знакомых с $u$ , но не с $v$ .

Если $V_{1}, V_{2}$ — два непересекающихся множества членов компании, то через $e\left(V_{1}\right)$ обозначаем количество пар знакомых в $V_{1}$ , через $e\left(V_{1}, V_{2}\right)$ — количество пар знакомых, один из которых в $V_{1}$ , а второй — в $V_{2}$ . Количество элементов множества $M$ обозначаем через $|M|$ .
$У$ каждого человека $w \in A$ имеется ровно $x-1$ знакомых в множестве $A \cup C$ (это его общие знакомые с $u$ , отличные от $v$ ). Просуммируем эти количества по всем $w \in A$ . Получаем $|A| \cdot(x-1)=2 e(A)+e(A, C)$ (здесь каждая пара знакомств внутри $A$ посчитана дважды, а каждое знакомство между $A$ и $C$ — один раз). Аналогично, $|A| \cdot(x-1)=2 e(A)+e(A, B)$ . Поэтому $e(A, B)=e(A, C)$ .

Далее, каждый человек в $B$ имеет $y-1$ соседей в $A \cup C$ (это его общие знакомые с $u$ , кроме $v$ ); Суммируя эти количества, получаем $(y-1)|B|=e(A, B)+e(B, C)$ . Аналогично, $(y-1)|C|=e(A, C)+e(C, B)$ . Поскольку $e(A, B)=e(A, C)$ и $e(B, C)= e(C, B)$ , мы приходим к выводу, что $(y-1)|B|=(y-1)|C|$ , а тогда $|B|=|C|$ или $y=1$ .

Если $y>1$ , то мы получили, что любые два знакомых человека имеют одинаковое число знакомых. А поскольку любые два либо знакомы, либо имеют общего знакомого, то такое невозможно, так как Дима и Саша имеют разное число знакомых.

Значит $y=1$ . Осталось показать, что такое действительно бывает. Рассмотрим компанию из $2 x+3$ человек, выделим в ней две группы по $x+1$ человеку и пусть оставшийся — Дима. Пусть Дима знаком со всеми, и внутри каждой из групп также все знакомы со всеми. Тогда для любых двух незнакомых людей (это люди из разных групп) у них есть единственный общий знакомый — Дима. У Димы с человеком из группы ровно $x$ общих знакомых — это остальные люди этой группы. У любых двух людей из одной группы $x$ общих знакомых — остальные люди этой группы и Дима. Также, Дима единственный, кто знаком со всеми, значит у них с Сашей разное число знакомых.