Задача 30810

Темы:    [ Степень вершины ] [ Принцип Дирихле (прочее) ]

Сложность: 3+ Классы: 7,8

Условие

На конференции присутствуют 50 учёных, каждый из которых знаком по крайней мере с 25 участниками конференции.
Докажите, что найдутся четверо из них, которых можно усадить за круглый стол так, чтобы каждый сидел рядом со знакомыми ему людьми.

Подсказка

Рассмотрите двух незнакомых учёных и их знакомых.

Решение

Рассмотрим двух незнакомых учёных (если таких нет, то всё в порядке). Каждый из них имеет по 25 знакомых среди оставшихся 48, значит, у них есть по крайней мере два общих знакомых. Этих четверых и усадим за стол.

Источники и прецеденты использования

книга
Автор	Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания	1994
Название	Ленинградские математические кружки
Издательство	Киров: "АСА"
Издание	1
глава
Номер	13
Название	Графы-2
Тема	Теория графов
задача
Номер	032