2014-06-08
В некотором обществе любые два знакомых не имеют общих знакомых, а любые два незнакомых имеют ровно двух общих знакомых. Доказать, что в этом обществе все имеют одинаковое число знакомых.
Решение:
Докажем, во-первых, что любые два знакомых имеют одинаковое число знакомых. Действительно, пусть $A$ и $B$ знакомы, а $A_{1}, A_{2}, \cdots, A_{n}$ - все знакомые $A$, отличные от $B$. Тогда, согласно условию задачи, никакие двое среди $B, A_{1}, A_{2}, \cdots, A_{n}$ не знакомы между собой. Рассмотрим $A_{1}$. Поскольку $A_{1}$ не знаком с $B$, то он имеет с $B$ двух общих знакомых: $A$ и, например, $B_{1}$. Так как $B_{1}$ и $A$ не знакомы друг с другом, то, кроме $B$ и $A_{1}$, у них нет общих знакомых, а значит, $B_{1}$ не знаком с $A_{2}, \cdots, A_{n}$. Аналогично находим $B_{2}$ - общего знакомого $A_{2}$ и $B$ (отличного от $B_{1}$, так как $B_{1}$ не знаком с $A_{2}$) и т. д. Таким образом, всем знакомым $A$ (отличным от $B$) соответствуют разные знакомые $B$ (отличные от $A$), а значит, число знакомых $A$ не превосходит числа знакомых $B$. Аналогично доказывается, что число знакомых $B$ не превосходит числа знакомых $A$. Поэтому $A$ и $B$ имеют одинаковое число знакомых. Во-вторых, если $C$ и $D$ не знакомы, то они имеют общего знакомого $E$. Тогда по доказанному выше $C$ и $E$ имеют одинаковое число знакомых, то же имеет место и для $D$ и $E$. Следовательно, $C$ и $D$ также имеют одинаковое число знакомых, совпадающее с числом знакомых $E$.