Регистрация Спросить otvet5GPT
armanshinaelin
Есть ответ 👍

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

100
269
Посмотреть ответы 2

Ответы на вопрос:

femalewolf1309
femalewolf1309
4,4(4 оценок)
Обозначим мальчиков 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 звонков.
арс90
арс90
4,4(34 оценок)

Памятники Ленину разбросаны по всей России и не только.

Памятники Пушкину (и многим писателям)

Помятники Советским космонавтам и т. д.

Объяснение:

Почти в каждом городке есть памятники

Реши свою проблему, спроси otvet5GPT

  • Быстро
    Мгновенный ответ на твой вопрос
  • Точно
    Бот обладает знаниями во всех сферах
  • Бесплатно
    Задай вопрос и получи ответ бесплатно

Популярно: Другие предметы

Caktus Image

Есть вопросы?

  • Как otvet5GPT работает?

    otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса.

  • Сколько это стоит?

    Проект находиться на стадии тестирования и все услуги бесплатны.

  • Могу ли я использовать otvet5GPT в школе?

    Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое!

  • В чем отличия от ChatGPT?

    otvet5GPT черпает академические источники из собственной базы данных и предназначен специально для студентов. otvet5GPT также адаптируется к вашему стилю письма, предоставляя ряд образовательных инструментов, предназначенных для улучшения обучения.

Подпишись на наш телеграмм канал

GTP TOP NEWS