Регистрация Спросить otvet5GPT
tzar1
14.05.2021 00:49
Математика
Есть ответ 👍

Вшколе для девочек любые две ученицы либо дружат, либо враждуот между собой. школа называется успешной, если выполняется хотя бы одно из следующих условий: 1) существуют 100 девочек а1, а2,…, а100 таких, что а1 дружит с а2, а2 дружит с а3,…, а99 дружит с а100; 2) существуют 7 девочек в1,…, b7 таких, что в1 враждует с в2, в3 — с в4, а в6 враждует с в5и в7. найдите максимальное количество учениц, при котором школа может не оказаться успешной. !

278
430
Посмотреть ответы 2

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

akozhametova
akozhametova
4,4(91 оценок)
Покажем, что 101 девочки может не хватить. если две их них враждуют со всеми, а остальные 99 дружат друг с другом, легко видеть, что не выполнится ни одно из условий . теперь покажем, что 102 девочек обязательно хватит для выполнения одного из условий. рассмотрим два случая: пусть существует 100 девочек, у каждой из которой есть не более 2 врагов среди других 99. покажем, что их можно расположить так, как требуется в условии 1. выберем произвольную девочку a₁, после этого выберем девочку a₂, которая дружит с a₁. потом выберем девочку a₃, которая дружит с a₂. так будем поступать, пока не выберем девочку a₉₈, которая дружит с a₉₇ (это всегда можно сделать, так как среди 3 оставшихся девочек хотя бы одна дружит с a₉₇). теперь возможна ситуация, когда обе оставшиеся девочки враждуют с a₉₈. это означает, что среди остальных девочек у a₉₈ нет врагов. выберем среди предыдущих 97 девочек одну, которая не враждует с a₉₉  и поменяем её местами с a₉₈. тогда мы сможем добавить девочку a₉₉ в конец цепочки. таким образом, мы доказали, что всегда можно составить цепочку из 99 девочек, в которой каждая последующая дружит с предыдущей. покажем, что туда можно добавить оставшуюся девочку. если девочка a₁₀₀ не враждует ни с a₁, ни с a₉₉, добавим её и условие 1 выполнится. если же она враждует хотя бы с одной из них, найдем среди девочек a₂..a₉₈ какую-то, которая не враждует ни с a₁, ни с a₉₉ (это возможно, поскольку у каждой девочки не более 2 врагов). поменяем её местами с a₁₀₀ и поместим между a₁ и a₉₉, тогда условие 1 выполнится, что и требовалось. осталось рассмотреть случай, когда 100 девочек требуемым образом выбрать нельзя. выберем девочек x и y с наибольшим числом врагов и рассмотрим остальных 100 девочек. по условию, существует девочка z, у которой есть не менее 3 врагов, не с x и y. поскольку у девочки x врагов не меньше, чем у z, существует девочка w, отличная от y и z, которая враждует с x. кроме того, у девочки z  существуют хотя бы два врага u и v, отличные от x, w и y. рассмотрим 97 девочек, не упомянутых выше. если среди них есть пара девочек  p и q, враждующих между собой, то две пары x,w; p,q и тройка z, u, v удовлетворяют условию 2. если же такой пары нет, то все 97 девочек дружат друг с другом. если у девочки y есть враг y', отличный от x,w,z,u,v, то две пары x,w; y,y' и тройка z,u,v удовлетворяют условию 1. если такой пары нет, то у девочки y не более 5 врагов, тогда и у всех девочек, кроме x, не более 5 врагов. добавим девочек z, u, v в группу из 97 дружащих друг с другом девочек. обозначим девочку z за a₁, какую-то из 97 девочек, не враждующую с z и u, за a₂, девочку u за a₃, какую-то из оставшихся 96 девочек, не враждующую с u и v за a₄, девочку v за a₅, среди оставшихся 95 девочек выберем двух, одна из которых не враждует с z, а вторая не враждует с v, обозначим их соответственно за a₁₀₀ и a₆. остальных 93 девочек обозначим за a₇₉₉ произвольным образом. нетрудно видеть, что в этом случае выполняется условие 1, что и требовалось доказать.
ffh5
ffh5
4,6(37 оценок)

ответ: 44

Пошаговое объяснение:

22*2=44 вот и решение

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

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

Популярно: Математика

Caktus Image

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

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

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

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

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

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

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

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

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

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

GTP TOP NEWS