3
1

В некотором клубе состоит 100 джентльменов, у каждого из которых не более троих знакомых в этом клубе, причем среди любых четверых джентльменов какие-то два не знакомы. Докажите, что из клуба можно исключить 33 джентльмена таким образом, что среди любых троих оставшихся в клубе джентльменов какие-то двое будут не знакомы.

задан 6 Май '14 15:18

изменен 7 Май '14 22:03

Deleted's gravatar image


126

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

Рассмотрим граф знакомств. Пусть в нём имеется треугольник ABC. Возможны два случая.

Первый: ни один из джентльменов A, B, C не входит ни в какую другую из троек. Тогда выделяем джентльмена A, который подлежит удалению, и отмечаем джентльменов B, C, которых мы хотим оставить.

Второй случай: джентльмен A входит ещё в какую-то тройку. Поскольку у него помимо B и C может быть только один знакомый D, то он входит в тройку с D и одним из B, C. Для определённости пусть это будет тройка ABD. У нас возникло два треугольника ABC и ABD с общим ребром. Согласно условию, C и D не знакомы (поскольку все остальные в четвёрке A, B, C, D знакомы). Легко видеть, что в этом случае никто из четверых не может входить более ни в какую из троек. Для A и B это очевидно, так как трое их знакомых уже налицо, и там дополнительной тройки больше нет. Если C знаком с кем-то третьим помимо A и B, скажем, с E, то он с ним в одну тройку не войдёт, так как E не знаком ни с A, ни с B. Аналогично для D.

Теперь выделяем A, подлежащего удалению, а каждого из B, C, D оставляем. Просматривая все треугольники, мы выделяем одного, и оставляем двух или трёх. Все рассмотренные подмножества (тройки и четвёрки) попарно не пересекаются. Теперь мы можем исключить тех, кого наметили, и это будет не более 1/3 от всех, то есть не более 33. Далее исключим ещё несколько человек, чтобы их стало ровно 33. В оставшемся подмножестве треугольников уже не будет, так как каждому из имевшихся в начале треугольников соответствует одна исключаемая вершина.

ссылка

отвечен 7 Май '14 4:05

благодарю за подробное объяснение.

(7 Май '14 12:25) make78
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×599

задан
6 Май '14 15:18

показан
1002 раза

обновлен
7 Май '14 12:25

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

по почте:

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

по RSS:

Ответы

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

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