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

Проект МЦНМО
при участии
школы 57
Задача 65073
Темы:    [ Теория графов (прочее) ]
[ Принцип Дирихле (прочее) ]
Сложность: 3+
Классы: 8,9
В корзину
Прислать комментарий

Условие

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


Решение

  Заметим, что у каждого в компании не менее трёх знакомых. Действительно, если бы некто X был знаком менее, чем с тремя, то, исключив из компании одного из его знакомых, мы получили бы пятёрку людей, в которой у X не более одного знакомого, то есть посадить их за круглый стол с соблюдением условия невозможно.
  Возьмём теперь любых пятерых и рассадим их за круглый стол. Шестой человек знаком, по крайней мере, с тремя из них; значит, он знаком с какой-то парой сидящих рядом людей. Осталось посадить шестого между ними.

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

олимпиада
Название Олимпиада имени Леонарда Эйлера (для 8 классов)
год/номер
Номер 2 (2010)
тур
задача
Номер 6

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

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