В компании из 2n + 1 человека для любых n человек найдётся отличный от них человек, знакомый с каждым из них. Докажите, что в этой компании есть человек, знающий всех

задан 8 Июн '15 22:08

@sapere aude, Если вам дан исчерпывающий ответ, отметьте его как верный (нажмите на галку рядом с выбранным ответом).

(8 Июн '15 22:53) Виталина
10|600 символов нужно символов осталось
2

Рассмотрим граф, соединяя ребром каждую пару не знакомых между собой. Требуется доказать, что найдётся изолированная вершина (человек, знакомый со всеми). Допустим, что это не так. Тогда рассмотрим компоненты связности, и в каждой из них выберем максимальное поддерево. В дереве нет циклов, поэтому его вершины можно правильно раскрасить в два цвета (для этого необходимо и достаточно отсутствие циклов нечётной длины). Поскольку компонент из одной точки нет, в каждой компоненте найдутся вершины разных цветов.

Сделаем так, чтобы вершин какого-то определённого цвета (белого) в каждой компоненте было не более половины. Рассмотрим все белые вершины; их не более $%n$%. Покажем, что нет никого, кто знал бы всех обладателей белых вершин. Все белые вершины мы собрали, а любая из оставшихся (чёрная) соединена в своей компоненте хотя бы с одной белой. Таким образом, мы получили компанию не более чем из $%n$% человек, не удовлетворяющую условию, и достаточно их дополнить произвольным образом до $%n$% человек. Каждый из оставшихся не будет знать хотя бы одного из них.

ссылка

отвечен 8 Июн '15 22:42

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

Возьмём любого человека $%A_1$%. По условию найдётся человек $%A_2$%, знакомый с $%A_1$%. Так же найдётся человек $%A_3,$%, знакомый с $%A_1,A_2$%, ..., найдётся человек $%A_{n+1},$%, знакомый с $%A_1,A_2,...,A_n$%. Тогда в компании $%A_1,A_2,...,A_{n+1}$% все между собой знакомы, а для компании $%A_{n+2},A_{n+3},...,A_{2n+1}$% найдётся человек из первой компании, знакомый с каждым из второй компании. Этот человек знает всех.

ссылка

отвечен 8 Июн '15 22:43

изменен 8 Июн '15 22:45

1

@EdwardTurJ: я решал "стандартно", а у Вас рассуждение более простое и красивое!

(8 Июн '15 22:46) falcao
10|600 символов нужно символов осталось
0

встретил такую вот задачу, которая практически идентична той, что выше: На прямой имеется 2n+1 отрезок. Любой отрезок пересекается по крайней мере с n другими. Докажите, что существует отрезок, пересекающийся со всеми остальными.

сначала показалось что они эквивалентны, но не сложно построить контрпример: рассмотрим граф вершины которого образуют квадрат, потом добавим вершину - центр квадрата - и соединим ее со всеми остальными вершинами. Такой граф нельзя изобразить отрезками, то есть получается что задачи все-таки не те же самые? или можно как-то иначе установить соответствие между людьми и отрезками? Просто задачи с отрезками решается совсем просто и было бы интересно свести графовую к ней (в обратную сторону точно можно)

ссылка

отвечен 13 Июн '15 5:46

1

Поскольку не всякий граф является графом отрезков, вторая задача является ослабленным вариантом первой. Какого-то прямого пути вывести общий факт из частного я здесь не усматриваю.

(13 Июн '15 11:05) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,015
×954
×379

задан
8 Июн '15 22:08

показан
658 раз

обновлен
13 Июн '15 11:05

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

по почте:

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

по RSS:

Ответы

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

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