3. В классе 30 детей. Никакие две девочки не дружат с одинаковым количеством мальчиков. А каждый мальчик дружит ровно с одной девочкой. Сколько максимум девочек может быть в классе?

Пусть девочек в классе g, тогда мальчиков — 30 − g.

Каждая девочка может дружить с числом мальчиков от 0 до 30 − g. Эти количества у девочек должны быть различными. Наименьшая возможная сумма g различных неотрицательных чисел равна 0 + 1 + … + (g − 1) = g(g − 1)/2. Эта сумма не может превышать число мальчиков, потому что каждый мальчик дружит ровно с одной девочкой.

Для 8 девочек наименьшая сумма равна 28, а мальчиков было бы 22, поэтому 8 девочек невозможны. Для 7 девочек можно распределить дружбу так, чтобы у девочек было по 0, 1, 2, 3, 4, 5 и 8 друзей-мальчиков: сумма равна 23, и каждый из 23 мальчиков дружит ровно с одной девочкой.

Ответ: максимум 7 девочек.