|
В компании из 2n + 1 человека для любых n человек найдётся отличный от них человек, знакомый с каждым из них. Докажите, что в этой компании есть человек, знающий всех задан 8 Июн '15 22:08 
sapere aude |
|
Рассмотрим граф, соединяя ребром каждую пару не знакомых между собой. Требуется доказать, что найдётся изолированная вершина (человек, знакомый со всеми). Допустим, что это не так. Тогда рассмотрим компоненты связности, и в каждой из них выберем максимальное поддерево. В дереве нет циклов, поэтому его вершины можно правильно раскрасить в два цвета (для этого необходимо и достаточно отсутствие циклов нечётной длины). Поскольку компонент из одной точки нет, в каждой компоненте найдутся вершины разных цветов. Сделаем так, чтобы вершин какого-то определённого цвета (белого) в каждой компоненте было не более половины. Рассмотрим все белые вершины; их не более $%n$%. Покажем, что нет никого, кто знал бы всех обладателей белых вершин. Все белые вершины мы собрали, а любая из оставшихся (чёрная) соединена в своей компоненте хотя бы с одной белой. Таким образом, мы получили компанию не более чем из $%n$% человек, не удовлетворяющую условию, и достаточно их дополнить произвольным образом до $%n$% человек. Каждый из оставшихся не будет знать хотя бы одного из них. отвечен 8 Июн '15 22:42 
falcao |
|
Возьмём любого человека $%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 
EdwardTurJ 1
@EdwardTurJ: я решал "стандартно", а у Вас рассуждение более простое и красивое!
(8 Июн '15 22:46)
falcao
|
|
встретил такую вот задачу, которая практически идентична той, что выше: На прямой имеется 2n+1 отрезок. Любой отрезок пересекается по крайней мере с n другими. Докажите, что существует отрезок, пересекающийся со всеми остальными. сначала показалось что они эквивалентны, но не сложно построить контрпример: рассмотрим граф вершины которого образуют квадрат, потом добавим вершину - центр квадрата - и соединим ее со всеми остальными вершинами. Такой граф нельзя изобразить отрезками, то есть получается что задачи все-таки не те же самые? или можно как-то иначе установить соответствие между людьми и отрезками? Просто задачи с отрезками решается совсем просто и было бы интересно свести графовую к ней (в обратную сторону точно можно) отвечен 13 Июн '15 5:46
sapere aude 1
Поскольку не всякий граф является графом отрезков, вторая задача является ослабленным вариантом первой. Какого-то прямого пути вывести общий факт из частного я здесь не усматриваю.
(13 Июн '15 11:05)
falcao
|
@sapere aude, Если вам дан исчерпывающий ответ, отметьте его как верный (нажмите на галку рядом с выбранным ответом).