Общие знакомы

[logic]

Есть N людей, причём каждые два из них имеет ровно один общей знакомой. Доказать, что хотя бы один человек знаком со всеми остальными.

[Um_nik]

Требую перевод!

[☭-Изделие 20Д]

Требую перевод!

Для н=2 знающих друг друга, один из них с большим самомнением будет уверен, что знает всех и себя в в том числе,для 3 -х самый прстой и удобный случай.
 от с любым другим нечетным числом уже напряг.
Имхо с точки логики решить задачу легче чем от математики

[Валерий]

Есть N людей, причём каждые два из них имеет ровно один общей знакомой. Доказать, что хотя бы один человек знаком со всеми остальными.

Это человек не попал в "помогите решить"

[VVV]

Для н=2 знающих друг друга, один из них с большим самомнением будет уверен, что знает всех и себя в в том числе,для 3 -х самый прстой и удобный случай.
 от с любым другим нечетным числом уже напряг.
Имхо с точки логики решить задачу легче чем от математики

Дело в методе индукции, т.е. для 4-х берем знание о двух + знание о трех, для пяти тоже, но еще и знание о 4-х... ничего сложного - скукотища.

  Естественная индукция здесь не проходит. Задача весьма интересная. Если ничего сложного нет, то, пожалуйста,  предоставьте доказательство. Хотя бы для N=31.

[Ischo]

Для четных неверно.

Пусть есть точка(х₁), соединенная со всеми прочими(x₂....x_(n-1)). Все пары (x_k,x_p), k,p!=1 будут иметь общего знакомого х₁.
Выберем общего знакомого для х₁ и х₂: скажем, не ограничивая общности, что это х₃. Причем, если какой-либо х_q будет знаком с х₂ (х₃), то х₁ и х₂ (х₃) будут иметь двух общих знакомых. Значит, если на некотором шаге останется только одна точка, не имеющая с х₁ общего знакомого (т.е. количество точек четно), то так она и останется, неприкаянная.

[zhekas]

Для четных неверно.

4 - четное число? Вроде да.

Х1 и Х2 знакомы с Х3, значит Х3 и есть общий знакомый. Иначе Х4 и Х2 знакомы с кем-то другим, а это может быть только Х1, что противоречит условию, ибо у Х1 и Х2 может только ОДИН общий знакомый.

при таких условиях X2 вполне может не знать X4, но иметь с ним общих знакомых. Так что противоречия не вижу

[Ischo]

Попробуйте нарисовать - не получится)

Смотрите, то же рассуждение в частном виде для четырех:
Пусть х₁ знаком со всеми остальными. Тогда у каждых двух из х₂, х₃, х₄ общий знакомый есть - х₁. Выберем общего знакомого для х₁ и х₂ - пусть это будет х₃. Тогда у х₁ и х₃ общий знакомый уже есть - это х₂. Единственная оставшаяся пара без общих знакомых - х₄ и х₁. Если "познакомить" х₄ с х₃ или х₂ - возникнет лишний "общий знакомый", с х₁ он уже знаком, значит никакими силами четыре точки предположению задачи не удовлетворяют.

[Лев]

Либо я неверно понял условие, либо "иметь общих знакомых" можно только из круга N людей.

[Лев]

Попробуйте нарисовать - не получится)

Спасибо, дошло. Для четных неверно, Ischo прав 

Могут образовываться только треугольники с одной вершиной

[Ischo]

А, ну теперь доказать совсем просто)
Пусть максимальное количество знакомств в схеме, удовлетворяющей задаче, K<N-1. Предположим тогда, что х₁ - самый социальный человек в мире и имеет K знакомых (х₂ ... х_K+1). Будем сначала искать общих знакомых для пар (х₁, х_p), p<=K+1. Так как х₁ имеет максимально допустимое количество знакомых, то общий знакомый такой пары может быть только среди х₂...х_K+1. Выполняем построение аналогично тому, что в доказательстве выше. Заодно получаем, что K в любом случае четно.
Имеем: K+1 точки, попарно имеющих общих знакомых и N-K-1 точки, пока свободно висящих. Заметим, что ни одна из "свободных точек" не может иметь более одного знакомого из первых K+1 -  иначе какие-то две "несвободных" будут иметь в качестве общего знакомого первую точку и свободную, что противоречит условию.
Рассмотрим х_K+2. Эта точка должна иметь знакомого из "свободных", чтобы иметь общего знакомого с х₁. Пусть это будет х₂. Выберем общего знакомого для х_K+2 и х₂. Это не может быть точка из первых K+1 (т.к. ни одна из "свободных точек" не может иметь более одного знакомого из первых K+1), значит это некоторая "свободная" точка х_K+3. Аналогично общим знакомым х_K+2 и х₄ будет х_K+4 и так далее. Перебирая таким образом все точки до х_K+1, получим два варианта развития событий:
1) Свободных точек не хватит -> Такое построение невозможно
2) Точек хватит, тогда х_K+2 будет иметь K знакомств со свободными точками, взятыми в качестве общих знакомых с х₂...х_K+1 и знакомство с точкой х₂, то есть всего K+1 знакомство, что противоречит исходному предположению о том, что K - максимальное число знакомств на душу населения.

В итоге получаем, что для нечетных N предположение верно, для четных же невозможна такая ситуация вообще.

[VVV]

А, ну теперь доказать совсем просто)
Пусть максимальное количество знакомств в схеме, удовлетворяющей задаче, K<N-1. Предположим тогда, что х₁ - самый социальный человек в мире и имеет K знакомых (х₂ ... х_K+1). Будем сначала искать общих знакомых для пар (х₁, х_p), p<=K+1. Так как х₁ имеет максимально допустимое количество знакомых, то общий знакомый такой пары может быть только среди х₂...х_K+1. Выполняем построение аналогично тому, что в доказательстве выше. Заодно получаем, что K в любом случае четно.
Имеем: K+1 точки, попарно имеющих общих знакомых и N-K-1 точки, пока свободно висящих. Заметим, что ни одна из "свободных точек" не может иметь более одного знакомого из первых K+1 -  иначе какие-то две "несвободных" будут иметь в качестве общего знакомого первую точку и свободную, что противоречит условию.
Рассмотрим х_K+2. Эта точка должна иметь знакомого из "свободных", чтобы иметь общего знакомого с х₁. Пусть это будет х₂. Выберем общего знакомого для х_K+2 и х₂. Это не может быть точка из первых K+1 (т.к. ни одна из "свободных точек" не может иметь более одного знакомого из первых K+1), значит это некоторая "свободная" точка х_K+3. Аналогично общим знакомым х_K+2 и х₄ будет х_K+4 и так далее. Перебирая таким образом все точки до х_K+1, получим два варианта развития событий:
1) Свободных точек не хватит -> Такое построение невозможно
2) Точек хватит, тогда х_K+2 будет иметь K знакомств со свободными точками, взятыми в качестве общих знакомых с х₂...х_K+1 и знакомство с точкой х₂, то есть всего K+1 знакомство, что противоречит исходному предположению о том, что K - максимальное число знакомств на душу населения.

В итоге получаем, что для нечетных N предположение верно, для четных же невозможна такая ситуация вообще.

  К сожалению, это рассуждение не доказывает требуемое утверждение для всех N. Если свободных точек хватит, то степень х_K+2 равна всего лишь К. То есть остается самый интересный случай N=4a²+6a+3, где а --- натуральное число, превосходящее 1.

[Ischo]

Почему K? K со "свободными" и одна с иксплюсвторой, K+1 всего.

[VVV]

 

Почему K? K со "свободными" и одна с иксплюсвторой, K+1 всего.

   x₂ соединена с какой-то из вершин x₃, ..., x_к+1 (x₂ и x₁ имеют общего знакомого). Пусть это будет x₃. Тогда из x_к+2 соединена с x₂, x_к+3 и к-2 вершинами для соединения с x₄, ..., x_к+1. С x₃ она уже соединена через x₂.
 

[Ischo]

Да, лажа, увидел.