допустимое значение n n такое, что он мог оказаться в подобной ситуации.
Для начала определим, какой может быть максимальное значение d i d_i d i для каждого человека i i. В случае, если каждый человек знаком со всеми остальными, максимальное значение d i d_i d i будет равно n − 1 n-1 n − 1 для каждого i i. В противном случае, максимальное значение d i d_i d i будет меньше.
Заметим, что если у двух человек, сидящих у костра, d i ≠ d j d_i neq d_j d i =d j , то они не могут быть знакомыми друг с другом, так как условие гласит, что два человека с номерами i i и j j ( i ≠ j i neq j i =j) знакомы друг с другом тогда и только тогда, когда d i = d j d_i = d_j d i =d j . Поэтому, чтобы минимально возможное значение n n было допустимым, все d i d_i d i должны быть одинаковыми.
Пусть d d будет это значение. Тогда, для каждого i i, количество людей с номерами j j таких, что d j = d d_j = d d j =d, будет равно d i d_i d i – 1, так как i i сам себе не может быть знаком. Таким образом, общее количество знакомых пар будет равно
∑ i = 1 n ( d i − 1 ) = n d − n ∑_{i=1}^n (d_i – 1) = nd – n ∑ i = 1 n ( d i − 1 ) = n d − n
Но общее количество знакомых пар также равно половине от суммы всех значений d i d_i d i , так как каждая пара учитывается дважды (для i-го человека и для j-го человека). То есть
∑ i = 1 n d i 2 = 1 2 ( n d ∑_{i=1}^n d_i^2 = frac{1}{2}(nd ∑ i = 1 n d i 2 = 2 n d
Сравнивая эти две суммы, получаем уравнение:
nd – n = 2nd
Отсюда следует, что n = 2. Подставим это значение в исходное уравнение и убедимся, что условия выполняются.
Итак, минимальное возможное значение n такое, что Николай мог оказаться в подобной ситуации, равно 2.
