В секции занимается 30 школьников. Каждые два школьника либо дружат, либо враждуют. (Дружба и вражда взаимна. Например, если A – друг B, то B – друг A.)Оказалось, что каждый школьник враждует ровно с 10 школьниками. Назовем тройку школьников A, B, C согласованной, если все три школьника либо попарно дружат, либо попарно враждуют. Каково наибольшее возможное количество согласованных троек школьников может быть в этой секции? (Две разные согласованные тройки могут иметь общих школьников.)
Пусть у нас есть 30 школьников, и каждый из них враждует с 10 другими школьниками. Значит, каждый ученик имеет 20 друзей. Если два школьника являются друзьями, то они имеют одних и тех же друзей. Но если два школьника враждуют, то они имеют 20 общих друзей.
Для удобства представления, мы можем нарисовать граф, где каждый школьник - вершина, и дружба или вражда - ребра. Итак, у нас есть 30 вершин и каждая из них имеет степень 20 (имеет 20 ребер).
Чтобы максимизировать количество согласованных троек, нам нужно создать как можно больше циклов троек, где каждый школьник в паре с другим школьником является либо друзьями, либо врагами.
Рассмотрим два возможных сценария:
1. Все школьники в секции дружат друг с другом. В этом случае, каждая из троек будет согласованной. Но таких троек будет C(30, 3) = 4,060 троек. Это наибольшее возможное количество согласованных троек.
2. Некоторые школьники враждуют друг с другом. В этом случае, мы должны создать как можно больше троек, где все три школьника в паре друг с другом - друзья или враги.
Для этого, мы можем использовать следующую стратегию: возьмем двух школьников, которые враждуют друг с другом и которые имеют максимально возможное количество общих друзей. Пусть эти два школьника - A и B, и они имеют 20 общих друзей. Далее, мы можем взять следующего школьника C, который также враждует со всеми общими друзьями A и B. Тогда тройка A, B, C будет согласованной тройкой.
В этом случае, каждый из школьников A, B и C должен иметь 20 друзей, так как они должны иметь максимальное количество общих друзей. Также, это означает, что у остальных 27 школьников (включая общих друзей A и B) должно быть по 19 друзей и 11 врагов.
Таким образом, мы можем создать (30 / 3) = 10 согласованных троек используя эту стратегию.
Суммируя результаты двух сценариев, мы получаем, что наибольшее возможное количество согласованных троек школьников в этой секции равно 4,060 + 10 = 4,070 троек.