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

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

Условие

25 мальчиков и несколько девочек собрались на вечеринке и обнаружили забавную закономерность. Если выбрать любую группу не меньше чем из 10 мальчиков, а потом добавить к ним всех девочек, знакомых хотя бы с одним из этих мальчиков, то в получившейся группе число мальчиков окажется на 1 меньше, чем число девочек. Докажите, что некоторая девочка знакома не менее чем с 16 мальчиками.


Решение

По условию имеется ровно 26 девочек, знакомых хотя бы с одним мальчиком из 25. Выберем произвольно мальчика M1. Для оставшихся 24 мальчиков ровно 25 девочек знакомы хотя бы с одним из них. Тогда девочка D1, не входящая в эти 25, знакома только с одним мальчиком M1. Аналогично, обозначив остальных мальчиков M2, ..., M25, найдём таких девочек D2, ..., D25, что Di знакома только с Mi. Рассмотрим оставшуюся девочку (отличную от D1, ..., D25). Если она знакома менее чем с 16 мальчиками, то для группы из  k ≥ 10  мальчиков, не знакомых с ней, найдётся ровно k девочек, знакомых хотя бы с одним из них. Противоречие.

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

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

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

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