7 попарно знакомых людей

[ihq.pl]

Gagarin1968 в сообщении #1623073 писал(а):

Doctor Boom решил совсем другую задачу, а именно: в группе из 42 человек каждый знаком ровно с 36 определёнными людьми из группы.

Я бы переформатировал: в группе из 42 человек каждый не знаком ровно с пятью людьми. Это худшее из того, что можно придумать в том смысле, что если найдется семерка в этом случае, то найдется и в остальных. В этом случае участники разбиваются на семь подгрупп незнакомых друг с другом людей.

-- 20.12.2023, 11:32 --

Gagarin1968 в сообщении #1623073 писал(а):

Такую задачу можно решить с помощью графа, а можно и обычным школьным рассуждением.

Попробую школьным. Берем одного из участников. Не важно скольких он не знает, вычеркиваем вместе с ним 5 участниковё, среди которых все его незнакомые (которых может быть и ноль). Из оставшихся выбираем одного и вычеркиваем вместе с ним еще пять, среди которых все незнакомые второго. Минимальное число невычеркнутых равно $42-12$. Из них выбираем третьего и вычеркиваем вместе с ним еще пять, среди которых... Итак, осталось $42-18$ не вычеркнутых участников. Все они - общие знакомые выбранных трех. Продолжаем в том же духе. После выбора четвертого остается $42-24$, а после выбора шестого остается $42-36$, из которых выбираем седьмого.

Теперь, если начертить граф этой схемы, увидим, что множество всех участников разбилось на 7 подгрупп "гипотетически" незнакомых друг с другом, в том смысле, что в подгруппе могут оказаться и знакомые. Главное, что участник из одной подгруппы точно знаком с участниками из других подгрупп.

[Doctor Boom]

Gagarin1968 в сообщении #1623073 писал(а):

Doctor Boom решил совсем другую задачу, а именно: в группе из 42 человек каждый знаком ровно с 36 определёнными людьми из группы. Докажите, что в этой группе найдется компания из 7 человек, в которой все знают друг друга.
Согласитесь, что это несколько отличается от первоначальной постановки задачи.

Там элементарно допилить решение до первоначальной постановки