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

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

Условие

Собрались 2n человек, каждый из которых знаком не менее чем с n присутствующими. Доказать, что можно выбрать из них четырёх человек и рассадить их за круглым столом так, что при этом каждый будет сидеть рядом со своими знакомыми (n$ \ge$2).

Решение

Если все присутствующие знакомы друг с другом, то возможность рассадить таким образом 4-х человек сомнения не вызывает. Пусть теперь A и B незнакомы между собой. Каждый из них имеет среди остальных 2n - 2 присутствующих не менее n знакомых; так как n + n = 2n = (2n - 2) + 2, то у A и B имеется, минимум, два общих знакомых C1 и C2 — и мы можем посадить A и B напротив друг друга, а между ними посадить C1 и C2.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 27
Год 1964
вариант
1
Класс 7
Тур 2
задача
Номер 2

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

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