3
1

В министерстве некоторые из 43 сотрудников объединены в квартеты - преступные сообщества из четырѐх человек, по предварительному сговору занимающиеся махинациями с подведомственными активами и взятками. Любые два различных квартета пересекаются не более, чем по одному общему сотруднику. Доказать, что министр, зная составы квартетов, всегда может составить из сотрудников министерства комиссию по борьбе с коррупцией в количестве 13 человек, не содержащую ни одного квартета целиком.

задан 28 Дек '13 23:47

10|600 символов нужно символов осталось
3

У меня получилось, что даже 14 можно сформировать. Рассуждение такое: пусть $%m$% -- число членов комиссии, которое удаётся набрать. Больше к ним никого нельзя присоединить, и это значит, что для каждого из $%43-m$% оставшихся среди набранных имеются трое, с которыми он образует квартет. Такие $%43-m$% троек назовём отмеченными (среди них не может быть одинаковых). Никакая пара не может входить в две отмеченных тройки сразу: в противном случае два квартета пересекаются более чем по одному сотруднику. В тройку входят 3 пары, то есть мы получили $%3(43-m)$% различных пар. Их не больше, чем число всех пар, формируемых из $%m$% выбранных сотрудников, откуда следует неравенство $%3(43-m)\le m(m-1)/2$%. При $%m=13$% это неравенство не выполняется, и ясно, что для меньших значений оно тем более не выполняется, так как левая часть с уменьшением $%m$% увеличивается, а правая -- наоборот. Значит, $%m\ge14$%.

ссылка

отвечен 29 Дек '13 1:36

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×2,766
×134

задан
28 Дек '13 23:47

показан
818 раз

обновлен
29 Дек '13 1:36

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru