Граф Дружбы

Крепко-накрепко дружить, с детства дружбой дорожить – учат в школе… Помните эту песню? Может быть, это про ваш класс говорят учителя – ой, какие дружные ребята? Или в социальных сетях у вас больше сотни друзей и еще столько же подписчиков? Как бы то ни было, дружба – удивительное явление, мимо которого не смогли пройти даже суровые математики.

Как можно изучать дружбу? Разумеется, изучать дружбу не получится в одиночку: ведь с кем-то надо дружить! Вот и ребята из 11А пришли к выводу, что проводить подобное полномасштабное исследование придется в группах. Остался только один вопрос: какой минимальной численности группы подойдут для данной задачи?

Исследователи из 11А не привыкли останавливаться на малом, поэтому в группе для исследования у каждого юного математика должно быть не менее 15 друзей – должен быть простор для экспериментов. Кроме того, чтобы не повторяться слишком сильно, число человек с одинаковым количеством друзей не должно превышать 15. Итак, всего два условия. Как же собрать подходящую группу?

На самом деле, решение ищется очень просто – нам нужно построить граф дружбы! В таком графе каждая вершина соответствует человеку из группы, а каждое ребро – отношению дружбы между людьми, чьи вершины оно соединяет.

Так как у каждого исследователя должно быть не менее 15 друзей, меньше 16 человек в группе быть не может – сам исследователь + 15. Нарисуем такой граф:

Красиво, правда? Это полный граф с 16-ю вершинами: каждая вершина соединена с каждой, то есть все дружат со всеми, и у каждого ровно 15 друзей.

Однако вернемся к условию задачи: у нас с вами остался еще второй пункт, который гласит, что более 15 человек с одинаковым количеством друзей – недопустимо. При этом в нашей схеме таких людей с 15-ю друзьями шестнадцать. Что-то придется менять, но соблюсти первое условие, про 15 друзей минимум, в группе с 16 людьми мы можем только так, как показано на графе выше. Придется для выполнения второго пункта добавлять еще одного человека. Хватит ли этого?

Мы доказали, что меньше 17 человек в группе быть не может. Но для того, чтобы решение задачи засчитали на полный балл, нужно еще доказать, что 17 – действительно минимум, привести пример, доказав, что это количество подходит. Давайте попробуем!

Если 17 человек дружат все со всеми, то у каждого из них 16 друзей, что больше 15, но все 17 человек имеют одинаковое число друзей – и таких людей больше 15. Разорвем всего одну «связь дружбы» – уберем одно ребро. Теперь у двух человек, которых оно связывало, стало на одного друга меньше – 15. Первое условие все еще выполняется. А у оставшихся 17 – 2 = 15 человек все еще по 16 друзей, но теперь таких людей всего 15, поэтому выполнено и второе условие!

Поздравляем, друзья, мы собрали полноценную исследовательскую группу – можно приступать к экспериментам!