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

задан 30 Мар '18 18:58

10|600 символов нужно символов осталось
1

Если каждый знает каждого, то всё очевидно. В противном случае находим двоих, не знакомых между собой. Пусть это A и C. Все их знакомые находятся в числе 48. Отметим 25 знакомых A. Тогда, даже если C знает всех 23 не отмеченных, для него найдутся по крайней мере два знакомых среди отмеченных. Пусть это B и D. Они являются общими знакомыми для A и C. Усадим тогда их в порядке A, B, C, D.

Судя по всему, число 25 здесь можно уменьшить, и утверждение останется верным. Но тогда задача будет сложнее решаться.

ссылка

отвечен 30 Мар '18 19:34

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×310

задан
30 Мар '18 18:58

показан
528 раз

обновлен
30 Мар '18 19:34

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru