Задача 4. Шесть друзей, два общих

Рисуем класс и называем уголки

Изобразим учеников точками, а каждую дружбу — отрезком между двумя точками. Тогда условие говорит две вещи: из каждой точки выходит ровно $6$ отрезков, и у любых двух точек ровно $2$ общих соседа (точки, соединённые с обеими).

Пусть в классе $n$ учеников; это число и нужно найти. Оба требования говорят о разном: первое — об одном ученике, второе — о паре учеников. Чтобы связать их, придумаем предмет, в котором участвуют и один ученик, и пара. Назовём уголком тройку «ученик $X$ и двое его друзей $A$ и $B$»: на рисунке это два отрезка $A$—$X$ и $X$—$B$ с общим концом (рисунок ниже). Ученика $X$ назовём серединой уголка, а $A$ и $B$ — его концами. Заметим: $A$ и $B$ при этом могут дружить между собой, а могут и не дружить — уголку это не важно.

План: посчитаем, сколько всего уголков в классе, двумя способами — по серединам и по концам. Первое требование условия даёт один счёт, второе — другой, а число уголков одно и то же.

Считаем уголки по серединам

Возьмём любого ученика $X$. Уголки с серединой $X$ — это пары его друзей: каждая пара $\{A, B\}$ друзей $X$ даёт ровно один уголок $A$—$X$—$B$, и наоборот. Друзей у $X$ ровно $6$. Сколько из них можно составить пар? Первого друга пары выбираем $6$ способами, второго — $5$ способами, получаем $6 \cdot 5 = 30$ вариантов; но каждая пара посчитана дважды (сначала $A$, потом $B$ — и сначала $B$, потом $A$), поэтому пар $30 : 2 = 15$.

Итак, каждый ученик — середина ровно $15$ уголков (рисунок ниже). У каждого уголка ровно одна середина, поэтому, складывая по всем $n$ ученикам, мы посчитаем каждый уголок ровно один раз. Всего уголков $15n$.

Считаем уголки по концам

Теперь возьмём любых двух учеников $A$ и $B$ — друзей или нет, условие говорит про любых двух. Уголки с концами $A$ и $B$ — это $A$—$X$—$B$, где $X$ — общий друг $A$ и $B$. Общих друзей ровно $2$, значит, каждая пара учеников — концы ровно $2$ уголков (рисунок ниже).

Сколько пар учеников в классе? Первого выбираем $n$ способами, второго — $n - 1$ способами, и каждая пара посчитана дважды: пар $\dfrac{n(n-1)}{2}$. У каждого уголка ровно одна пара концов, поэтому, складывая по всем парам, мы снова посчитаем каждый уголок ровно один раз. Всего уголков $2 \cdot \dfrac{n(n-1)}{2} = n(n-1)$.

Два счёта одного числа

В шагах 2 и 3 мы считали одно и то же — все уголки класса. Значит,

Учеников в классе хотя бы один, $n \ne 0$, поэтому можно разделить обе части на $n$: $15 = n - 1$, откуда $n = 16$.

Что мы доказали: если класс из условия существует, то в нём ровно $16$ учеников — при любом другом числе два счёта дали бы разные числа, чего не бывает. Но такой счёт ничего не говорит о том, бывает ли такой класс вообще. Если бы его не было, задача не имела бы ответа. Поэтому нужен пример.

Пример: таблица 4 × 4

Расставим $16$ учеников в таблицу из $4$ строк и $4$ столбцов и договоримся: дружат те, кто стоит в одной строке или в одном столбце. Проверим оба требования (рисунок ниже).

• Друзья одного ученика: трое остальных в его строке и трое остальных в его столбце, всего $3 + 3 = 6$. Ровно шесть.

• Общие друзья двух учеников из одной строки: двое остальных из этой строки — они дружат с обоими. Ученик из другой строки дружит с кем-то из наших двоих только по столбцу, а столбцы у них разные, так что общим другом он быть не может. Ровно два. Для двух учеников из одного столбца — так же.

• Общие друзья двух учеников из разных строк и разных столбцов: тот, кто стоит в строке первого и столбце второго, и тот, кто стоит в столбце первого и строке второго, — два «угла» прямоугольника с нашими учениками в противоположных углах. Другой ученик не может стоять одновременно в строке первого и в строке второго (строки разные) и дружит с каждым из двоих только через одну из этих двух клеток. Ровно два.

Такой класс существует, и в нём $16$ учеников. Вместе с шагом 4: в классе из условия ровно $16$ учеников.