Круглый стол, знакомства

Автор темы koh 
ОбъявленияПоследний пост
ОбъявлениеПравила и принципы форума «Высшая математика»28.10.2009 15:17
ОбъявлениеТеХнический редактор - LATEX18.01.2020 21:57
ОбъявлениеВ марте в МГУ имени М.В. Ломоносова пройдет II Кубок Москвы по Го среди студентов ВУЗов14.02.2020 11:44
18.11.2019 01:01
Круглый стол, знакомства
Условие

За круглым столом сидят несколько гостей.
Некоторые из них знакомы между собой; знакомство взаимно.
Все знакомые любого гостя (считая его самого) сидят вокруг стола через равные промежутки.
(Для другого человека эти промежутки могут быть другими.)
Известно, что любые двое имеют хотя бы одного общего знакомого.
Верно ли, что на самом деле, все гости знакомы друг с другом (то есть каждый знаком с каждым).


Найдется человек, знакомый со всеми остальными.




Ответ: Да, верно
Заметим, что если у человека есть знакомые, сидящие рядом (в частности, если он знаком со своим соседом), то этот человек знаком со всеми.
Покажем, что такой гость найдется.
Пусть A и B - двое соседей.
Если они не знакомы между собой, то их общий знакомый C знаком со всеми, так как его знакомые сидят без промежутков.
В противном случае знаком со всеми человек A (по той же причине).
Итак, пусть X - гость, знакомый со всеми.
Тогда его соседи тоже знакомы со всеми, так как они знакомы с X (являющимся для них соседом).
Соседи этих соседей также знакомы со всеми, и так далее по кругу в обе стороны.

Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти