Считаем рёбра
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
В городе проводилось совещание врачей. От каждой поликлиники на совещание было приглашено по пять врачей. Оказалось, что каждый из приглашенных работал в двух поликлиниках, поэтому на совещании представлял обе поликлиники. Кроме того, для любых двух поликлиник города среди участников совещания найдется врач, который в них работает. Сколько в городе может быть поликлиник и сколько врачей могло принимать участие в совещании?
Обозначим через 
количество поликлиник, через 
— количество врачей. Построим двудольный граф. Вершины первой доли —
поликлиники, вершины второй доли — врачи. Будем соединять ребром врача и поликлинику, если этот врач в ней работает. Сначала
посчитаем количество ребер в этом графе. С одной стороны ребер 
а с другой — 
откуда 
Количество пар поликлиник
равно 
По условию для каждой такой пары найдется свой собственный врач, поэтому врачей не меньше, чем количество пар, то есть
Но тогда 
то есть 
Также заметим, что количество поликлиник должно быть четно, поэтому остались
только 
Легко видеть что все такие случаи возможны и количества врачей для этих вариантов равны 
и 
соответственно.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
