В классе учится 15 мальчиков и 15 девочек. В день 8 Марта некоторые мальчики позвонили некоторым девочкам и поздравили их с праздником

Постоянный пользователь нашего ресурса написал нам почту в 2:27 с просьбой предоставить развернутый ответ на его вопрос. Наши эксперты отнесли этот вопрос к разделу Разное. Для ответа был привлечен один из опытных специалистов, который занимается написанием студенческих работ.

Цитируем вопрос ваш вопрос

В классе учится 15 мальчиков и 15 девочек. В день 8 Марта некоторые мальчики позвонили некоторым девочкам и поздравили их с праздником (никакой мальчик не звонил одной и той же девочке дважды). Оказалось, что детей можно единственным образом разбить на 15 пар так, чтобы в каждой паре оказались мальчик с девочкой, которой он звонил. Какое наибольшее число звонков могло быть сделано?

Разбор вопроса и ответ на него

Раздел 'ЕГЭ (школьный)', к которому был отнесён этот вопрос является не простой рубрикой. Для подготовки ответа на вопросы из этой рубрики специалист должен обладать широкими познаниями в различных научных областях. Однако в нашей компании таковые имеются.

Вы спрашивали:

В классе учится 15 мальчиков и 15 девочек. В день 8 Марта некоторые мальчики позвонили некоторым девочкам и поздравили их с праздником (никакой мальчик не звонил одной и той же девочке дважды). Оказалось, что детей можно единственным образом разбить на 15 пар так, чтобы в каждой паре оказались мальчик с девочкой, которой он звонил. Какое наибольшее число звонков могло быть сделано?

Конечно этот ответ может полностью не раскрыть тему вопроса, но мы постарались сделать его максимально полным. Предлагаем ознакомиться с мнением эксперта по этой теме:

Обозначим мальчиков M1, M2, ..., M15, а девочек – D1, D2, ..., D15 так, чтобы  M1-D1, M2-D2, ..., M15-D15  было единственным разбиением на пары из условия задачи. Предположим, что каждый мальчик позвонил хотя бы двум девочкам. Нарисуем стрелку от каждой девочки Di к мальчику Mi, с которым она находится в паре, а от каждого мальчика Mi – к другой (отличной от Di) девочке, которой он звонил. Тогда от каждого ребёнка ведёт по стрелке. Если мы будем двигаться по стрелкам (начав от произвольной девочки), то рано или поздно мы попадём к девочке, которая уже встречалась в строящейся цепочке. Таким образом, в соответствующем графе есть цикл. Объединим в этом цикле каждого мальчика с девочкой, к которой от него ведет стрелка; остальные пары оставим без изменения. Мы получили другое разбиение на пары, что противоречит условию.
Следовательно, найдётся мальчик, который звонил ровно одной девочке. Если отбросить эту пару, число звонков уменьшится не больше, чем на 15 – максимальное возможное количество звонков этой девочке. После этого снова найдется мальчик, сделавший ровно один звонок одной из оставшихся девочек. Отбросив эту пару, уменьшим количество звонков не более, чем на 14, и т. д. Итого, было сделано не более  15 + 14 + ... + 2 + 1 = 120  звонков.
Ровно 120 звонков получается, например, если каждой девочке Di звонили мальчики M1, M2, ..., Mi.
Ответ.120 звонков.

К нам на почту приходит много вопросов. Мы стараемся отвечать на все. Однако вы должны понимать, что большая загруженность увеличивает время ответа. Сейчас среднее время ответа равно 23:53.