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

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

Условие

В классе 20 учеников, причём каждый дружит не менее, чем с 14 другими.
Можно ли утверждать, что найдутся четыре ученика, которые все дружат между собой?


Подсказка

У одного из учеников 14 друзей. Достаточно выбрать из них трёх попарно знакомых.


Решение

Соберём весь класс в одной комнате. Рассмотрим некоторого человека А. Пусть теперь из комнаты выйдут все ученики, которые не дружат с А. По условию таких не более пяти. Поэтому в комнате осталось по крайней мере 15 учеников. Выберем из оставшихся в комнате ученика B, отличного от А. Пусть из комнаты выйдут все ученики, которые не дружат с B. После этого в комнате осталось не меньше 10 учеников. Наконец, выберем из оставшихся в комнате ученика C, отличного от А и от B. Пусть из комнаты выйдут все ученики, которые не дружат с C. После этого в комнате осталось не меньше пяти учеников. Эти пять учеников – это А, B, C и еще два ученика D и E, которые дружат с А, B, C. Искомая четвёрка учеников – это, например, А, B, C, D.


Ответ

Можно.

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

web-сайт
задача

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

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