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

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

Условие

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


Решение

Предположим, что это не так. Выбрав любых двух человек A и B, среди оставшихся десятерых выберем таких людей C1, C2, ..., Ck, каждый из которых знает ровно одного в этой паре. В силу предположения  k ≥ 6.  Подсчитаем число N троек {A, В, Ci}  двумя способами. Всего имеется  12·11 : 2 = 66  пар  {A, В},  и каждой паре отвечает не менее шести человек Сi, поэтому   N ≥ 6·66 = 396.  С другой стороны, Ci можно фиксировать и искать для него такие пары  {A, В},  в которых он знает ровно одного человека. Если у Сi есть n знакомых, то число искомых пар  {A, В}  равно  n(11 − n) ≤ 30.  Выбрать же Сi можно 12 способами, откуда  N ≤ 5·6·12 = 360.  Противоречие.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 48
Год 1985
вариант
Класс 9
задача
Номер 4

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

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