3) В школе для девочек любые две ученицы либо дружат, либо враждуот между собой. Школа называется успешной, если выполняется хотя бы одно из следующих условий:

1) существуют 100 девочек А1, А2, ..., А100 таких, что А1 дружит с А2, А2 дружит с А3, ..., А99 дружит с А100;

2) существуют 7 девочек В1, ..., B7 таких, что В1 враждует с В2, В3 - с В4, а В6 враждует с В5 и В7.

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

(8 класс)

Покажем, что 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₇, ... A₉₉ произвольным образом. Нетрудно видеть, что в этом случае выполняется условие 1, что и требовалось доказать.