В школе для девочек любые две ученицы либо дружат, либо враждуот между собой. Школа называется успешной, если выполняется хотя бы одно из
следующих условий: 1) существуют 100 девочек А1, А2,…, А100 таких, что А1 дружит с А2, А2 дружит с А3,…, А99 дружит с А100; 2) существуют 7 девочек В1,…, B7 таких, что В1 враждует с В2, В3 — с В4, а В6 враждует с В5и В7. Найдите максимальное количество учениц, при котором школа может не оказаться успешной. Помогите пожалуйста!
следующих условий: 1) существуют 100 девочек А1, А2,…, А100 таких, что А1 дружит с А2, А2 дружит с А3,…, А99 дружит с А100; 2) существуют 7 девочек В1,…, B7 таких, что В1 враждует с В2, В3 — с В4, а В6 враждует с В5и В7. Найдите максимальное количество учениц, при котором школа может не оказаться успешной. Помогите пожалуйста!
More Questions From This User See All
Answers & Comments
Теперь покажем, что 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₇,..A₉₉ произвольным образом. Нетрудно видеть, что в этом случае выполняется условие 1, что и требовалось доказать.