Комбинаторика на МВ (Финашке): графы, турниры, множества, способы

Каждых двух учеников, которые учатся в разных классах и дружат между собой, назовём смешанной парой. Поскольку каждый из 25 учеников 11 «А» входит ровно в две такие пары, то всего имеется 50 смешанных пар.

Пусть в 11 «Б» учится человек, причем ровно из них имеют ровно по одному другу в 11 «А». Из условия задачи следует, что

Кроме того, в этом классе может найтись не более одного ученика, не имеющий друзей в 11 «А».

Каждый из остальных (если такой ученик один) или (если таких учеников нет) учеников 11 «Б» входит по меньшей мере в две смешанные пары. Значит, общее число смешанных пар больше или равно

Сложив неравенства и получим откуда

С другой стороны, построим пример, показывающий, что равенство возможно. Так как то, подставив в неравенство, найдем ограничение на снизу:

Совмещая с ограничением сверху, получаем, что Возьмем Пусть ученики класса «А» — это а класса «Б» — Тогда распределение следующее:

1.

не дружит ни с кем.

2.

Каждый ученик дружит с одним из соответственно.

3.

Ученики с по (их ровно 12) дружат так: — с и — с и и так далее. А так как в таком распределении останется без второго друга, то просто сделаем и дружественной парой. Тогда у будет три друга, но это не нарушает условие.