|
|
 |
Условие
В компании из семи человек любые шесть могут сесть за круглый стол так, что каждые два соседа окажутся знакомыми.
Докажите, что и всю компанию можно усадить за круглый стол так, что каждые два соседа окажутся знакомыми.
Решение
Заметим, что у каждого в компании не менее трёх знакомых. Действительно, если бы некто X был знаком менее чем с тремя, то, исключив из компании одного из его знакомых, мы получили бы шестёрку людей, в которой у X не более одного знакомого, то есть посадить их за круглый стол с выполнением условия невозможно. Так как число вершин нечётной степени графа знакомств чётно (см. задачу 87972), то хотя бы у одной вершины степень чётна, то есть у какого-то человека Y хотя бы четыре знакомых. Рассадим всех, кроме Y, за круглый стол с выполнением условия. Из четырёх его знакомых хотя бы двое сидят рядом. Усадив Y между ними, получим требуемую рассадку.
