2019-04-29
На некотором собрании присутствовало $n$ человек. Известно, что каждые два знакомых из них не имеют никаких общих знакомых, а каждые два незнакомых между собой лица имеют ровно двух общих знакомых.
а) Доказать, что все присутствующие имеют одно и то же число знакомых.
б) При каких $n$ возможно условие задачи?
Решение:
а) Выберем одного из собравшихся $A$; всех знакомых с ним лиц мы обозначим через $A_1, A_2, \cdots, A_k$. Ясно, что никакие два из этих двух лиц не знакомы друг с другом и каждые два лица - скажем, $A_i$ и $A_j$ - имеют двух общих знакомых: $A$ и некоторое лицо $A_{ij}$; здесь $i, j = 1, 2, \cdots, k$ и $i \neq j$. При этом никакие два из $\frac {k(k-1)}{2}$ лиц $A_{ij}$, очевидно, не совпадают, ибо в противном случае это лицо имело бы с $A$ не менее трех общих знакомых. С другой стороны, так как каждое не знакомое с $A$ лицо имеет с $A$ двух общих знакомых (очевидно, из числа лиц $A_1, A_2, \cdots, A_k$), то $A_{12}, A_{13}, \cdots, A_{k-1, k}$ - это все не знакомые с $A$ лица, и, значит, общее число $n$ присутствующих на собрании людей равно
$n = 1 + k + \frac {k(k-1)}{2}$ (*)
(1 - это $A$; $k$ - это лица $A_i$; $\frac {k(k-1)}{2}$ - это лица $A_{ij}$).
Заметим теперь, что в силу равенства (*), которое можно переписать еще и так:
$k^2 + k - (2n - 2) = 0$, (**)
имеем
$k = - \frac{1}{2} + \sqrt { \frac{1}{4} + (2n - 2)} = \frac {\sqrt{8n - 7} - 1}{2}$
(второй корень квадратного уравнения (**) $k^{ \prime} = - \frac{1}{2} - \sqrt { \frac{1}{4} + 2n - 2}$ не подходит, ибо он отрицателен). Таким образом, число $k$ знакомых с некоторым лицом $A$ лиц однозначно определяется по общему числу $n$ присутствующих на собрании лиц, т. е. оно является одним и тем же для всех лиц $A$.
б) В силу (*) имеем
$n = \frac {k(k+1)}{2} + 1$, (***)
т. е. $n$ должно быть на единицу больше так называемого треугольного числа $\frac {k(k+1)}{2}$. При этом для записываемого по формуле (***) числа $n$ количество знакомых у каждого из присутствующих лиц равно $k$; здесь $k = 1, 2, 3, \cdots$ - произвольное натуральное число.
Ответ: $n = \frac {k(k+1)}{2} + 1$, где $k$ - целое.