Задача 093 — Задачи на Графы

В компании из 100 человек среди любых 50 есть одно и то же (ненулевое) количество пар знакомых. Какое наименьшее количество пар знакомых может быть среди всех 100?

Подсказка

Рассмотрим любую группу из 51 человека. Если выкинуть любого из них, среди оставшихся будет одно и то же число знакомств. Поэтому в этой группе каждый имеет среди остальных 50 одно и то же число знакомых.

Решение

Ответ: $99 \times 50=4950$ .

Решение. Рассмотрим любую группу из 51 человека. Если выкинуть любого из них, среди оставшихся будет одно и то же число знакомств. Поэтому в этой группе каждый имеет среди остальных 50 одно и то же число знакомых. Пусть оно равно $a$ . Тогда общее число знакомств среди 50 человек должно равняться $51 a / 2-a$ . Значит, значение а будет одним и тем же для всех компаний из 51 человека. Возьмем любого человека Ч. Среди остальных 99 есть либо 50 знакомых с ним, либо 50 незнакомых с ним. Добавляя их к Ч, получим компанию, где в первом случае $a=50$ , а во втором $a=0$ . Но второй случай невозможен по условию, а в первом случае, очевидно, каждый знаком с каждым. Отсюда получаем ответ.