ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 115371
Темы:    [ Раскладки и разбиения ]
[ Задачи с ограничениями ]
[ Четность и нечетность ]
[ Степень вершины ]
Сложность: 4-
Классы: 8,9
В корзину
Прислать комментарий

Условие

В компании из семи человек любые шесть могут сесть за круглый стол так, что каждые два соседа окажутся знакомыми.
Докажите, что и всю компанию можно усадить за круглый стол так, что каждые два соседа окажутся знакомыми.


Решение

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

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2009-2010
Этап
Вариант 4
Класс
Класс 9
задача
Номер 06.4.9.7

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .